
Computer Science 2010
Syntactic Complexity of Ideal and Closed LanguagesAbstract: 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 worstcase syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n1}$ is a tight upper bound on the complexity of right ideals and prefixclosed languages, and that there exist left ideals and suffixclosed languages of syntactic complexity $n^{n1}+n1$, and twosided ideals and factorclosed languages of syntactic complexity $n^{n2}+(n2)2^{n2}+1$.
