Universal witnesses for descriptional complexity and their (partial) explanation.

Room FC1.029, DMat-FCUP
Friday, 14 March, 2014 - 14:30

When studying descriptional complexity of operations over automata it is not only needed to find an algorithm to perform such operation in the most succinct way, but one also needs to find a witness that reaches that complexity, showing that what was done is the best possible, that the bound is tight. Finding such witnesses for each of the operations studied, is always a major headache, being the witnesses different for each operation. In 2012 Janusz Brzozowski presented a family of languages that surprisingly appear to be witnesses for most of the studied operations. We give, in this talk a good justification why such languages exist, and that, actually, they are not so rare.

Speaker: 

Rogério Reis (DCC-FCUP / CMUP)