Seminár z teoretickej informatiky - Juraj Šebej (24.3.2017)

v piatok 24.3.2017 o 11:00 hod. v miestnosti M/213

---

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

 
Abstrakt:
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.

web:  http://kedrigern.dcs.fmph.uniba.sk/STI2
rss:  http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

 

 

---