Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages
verfasst von : Janusz Brzozowski, Baiyu Li, Yuli Ye
Erschienen in: Descriptional Complexity of Formal Systems
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
The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity
n
of these languages. We study the syntactic complexity of prefix-, suffix-, and bifix-free regular languages. We prove that
n
n
− 2
is a tight upper bound for prefix-free regular languages. We present properties of the syntactic semigroups of suffix- and bifix-free regular languages, and conjecture tight upper bounds on their size.