Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Basic Operations on Binary Suffix-Free Languages
verfasst von : Roland Cmorik, Galina Jirásková
Erschienen in: Mathematical and Engineering Methods in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give a characterization of nondeterministic automata accepting suffix-free languages, and a sufficient condition on deterministic automata to accept suffix-free languages. Then we investigate the state complexity of basic operations on binary suffix-free regular languages. In particular, we show that the upper bounds on the state complexity of all the boolean operations as well as of Kleene star are tight in the binary case. On the other hand, we prove that the bound for reversal cannot be met by binary languages. This solves several open questions stated by Han and Salomaa (Theoret. Comput. Sci. 410, 2537-2548, 2009).