Special Issue – Descriptional Complexity of Formal Systems (DCFS 2013)No Access
SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
https://doi.org/10.1142/S0129054114400097Cited by:4 (Source: Crossref)
Abstract
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.
This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871 and a Postgraduate Scholarship
