2011 | OriginalPaper | Chapter
Syntactic Complexity of Ideal and Closed Languages
Authors : Janusz Brzozowski, Yuli Ye
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.