Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Upper Bound on Syntactic Complexity of Suffix-Free Languages
verfasst von : Janusz Brzozowski, Marek Szykuła
Erschienen in: Descriptional Complexity of Formal Systems
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
Abstract
We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with \(n\) left quotients (that is, with state complexity \(n\)) is at most \((n-1)^{n-2}+n-2\) for \(n\geqslant 7\). Since this bound is known to be reachable, this settles the problem. We also reduce the alphabet of the witness languages reaching this bound to five letters instead of \(n+2\), and show that it cannot be any smaller. Finally, we prove that the transition semigroup of a minimal deterministic automaton accepting such a witness language is unique for each \(n\geqslant 7\).