Department Seminar Series
Minimal probabilistic automata have to make irrational choices
15th November 2016, 13:00
Ashton Lecture Theater
Dr. Mahsa Shirmohammadi
University of Oxford
Wolfson Building,
Parks Road,
Oxford OX1 3QD
Abstract
In this talk, we answer the question of whether, given a probabilistic automaton (PA) with rational transition probabilities, there always exists a minimal equivalent PA that also has rational transition probabilities. The PA and its minimal equivalent PA accept all finite words with equal probabilities.
We approach this problem by exhibiting a connection with a longstanding open question concerning nonnegative matrix factorization (NMF). NMF is the problem of decomposing a given nonnegative n*m matrix M into a product of a nonnegative n*d matrix W and a nonnegative d*m matrix H. In 1993 Cohen and Rothblum posed the problem of whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries. As a corollary we obtain a negative answer to the question on rationality of minimal probabilistic automata.
This talk is based on two papers in ICALP 2016 and SODA 2017.
Maintained by Othon Michail