14:00
15:00

A nondeterministic finite automaton (without initial and final states) is called unambiguous (or diamond-free) if for every two states p, q and every word w there is at most one path from p to q labelled by w. Such automata naturally appear in the context of variable-length codes, unambiguous monoids of relations and weighted automata. An NFA (again, without initial and final states) is called complete if every word labels some path in it. I will discuss how to decide if an unambiguous finite automaton is complete and how to estimate the length of a shortest word violating completeness.
I will then move to the setting of matrix semigroups, in which unambiguous automata are nothing more than semigroups of matrices whose entries are only zero and one, and incompleteness is just matrix mortality ("does the zero matrix belong to a matrix semigroup?"). This (predictable) plot twist will allow me to generalise the setting of unambiguous automata to the case of finite semigroups of matrices with rational entries, and to state some bold conjectures.

sale 178