
Computer Science 2012
Syntactic Complexity of Finite/Cofinite, Definite, and Reverse Definite LanguagesAbstract: We study the syntactic complexity of finite/cofinite, definite and reverse definite languages. The syntactic complexity of a class of languages is defined as the maximal size of syntactic semigroups of languages from the class, taken as a function of the state complexity n of the languages. We prove that (n1)! is a tight upper bound for finite/cofinite languages and that it can be reached only if the alphabet size is greater than or equal to (n1)!(n2)!. We prove that the bound is also (n1)! for reverse definite languages, but the minimal alphabet size is (n1)!2(n2)!. We show that \lfloor e\cdot (n1)!\rfloor is a lower bound on the syntactic complexity of definite languages, and conjecture that this is also an upper bound, and that the alphabet size required to meet this bound is \floor{e \cdot (n1)!}  \floor{e \cdot (n2)!}. We prove the conjecture for n\le 4.
