Seminár z teoretickej informatiky - Juraj Šebej (24.3.2017)
v piatok 24.3.2017 o 11:00 hod. v miestnosti M/213
Od: Rastislav Královič
Prednášajúci: Juraj Šebej (UPJŠ Košice)
Názov: Descriptional Complexity of Operations on Formal Languages
Termín: 24.3.2017, 11:00 hod., M/213
We study the state complexity of operations on regular languages. For reversal, we provide a binary worst-case example with a unique final state. Next we prove attainability of all possible values in the range from $log n $ to $2^n$ by the state complexity of the reversal of languages over an alphabet of size $2n$. We also get a segment of a quadratic size of possible values for reversal on languages over a binary alphabet. Then we study the reversal operation on binary prefix-free languages, and provide a lower bound that is smaller than the upper bound just by a constant factor. For star and concatenation, we show attainability of all possible values up to the known upper bounds for languages over an alphabet of size $2n$. We provide the exact complexity of the combined operation of star-complement-star on prefix-free languages over an arbitrary alphabet. Finally, we study Kuratowski algebras generated by prefix-free languages under the operations of star and complementation. We show which of 12 possible algebras can or cannot be generated by prefix-free languages. For algebras generated by a prefix-free language, we also study the state complexities of all generated languages, and we always find a generator that maximizes these complexities.