SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
JANUSZ BRZOZOWSKI, BAIYU LI · International Journal of Foundations of Computer Science · 2014
The syntactic complexity of a subclass of the class of regular languages is the maximal cardinality of syntactic semigroups of languages in that class, taken as a function of the state complexity n of these languages. We prove that n! and ⌊e(n − 1)⌋. are tight upper bounds for the syntactic complexity of ℛ- and 𝒥-trivial regular languages, respectively.