2012/03/13 by Janusz Brzozowski, David Liu, Brzozowski, Janusz +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1203.2873
openalex publication_date 2012/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (n-1)! 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 (n-1)!-(n-2)!. We prove that the bound is also (n-1)! for reverse definite languages, but the minimal alphabet size is (n-1)!-2(n-2)!. We show that \lfloor e⋅ (n-1)!\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 \floore ⋅ (n-1)! - \floore ⋅ (n-2)!. We prove the conjecture for n≤ 4.