2011 | OriginalPaper | Buchkapitel
Syntactic Complexity of Ideal and Closed Languages
verfasst von : Janusz Brzozowski, Yuli Ye
Erschienen in: Developments in Language Theory
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 state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity
n
of languages in that class. We prove that
n
n
− 1
is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity
n
n
− 1
+
n
− 1, and two-sided ideals and factor-closed languages of syntactic complexity
n
n
− 2
+ (
n
− 2)2
n
− 2
+ 1.