Syntactic complexity of ideal and closed languages

Janusz Brzozowski and Yuli Ye

Abstract. 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 nn − 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 nn − 1 + n − 1, and two-sided ideals and factor-closed languages of syntactic complexity nn − 2 + (n − 2) 2n − 2 + 1.

Comments are closed.