BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T214018Z
UID:Seminar-dept-425@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20161115T130000
DTEND:20161115T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Mahsa Shirmohammadi: Minimal probabilistic automata have to make irrational choices\n\nIn 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. \n\n\n\nWe 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.\n\n\n\nThis talk is based on two papers in ICALP 2016 and SODA 2017.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=425
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR