Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only \$99

 Relative Articles On the structure and syntactic complexity of generalized definite languages Syntactic Complexity of Ideal and Closed Languages Syntactic Complexity of Star-Free Languages The Formation of the Definite Article in the Nordic Languages Syntactic Complexity of R- and J-Trivial Regular Languages Syntactic Complexity of Suffix-Free Languages SYNTACTIC STRUCTURE FOR ADHERENCE OF LANGUAGES语言附着的句法结构 Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages Maximal Syntactic Complexity of Regular Languages Implies Maximal Quotient Complexities of Atoms Syntax diagrams as a formalism for representation of syntactic relations of formal languages More...

# Syntactic Complexity of Finite/Cofinite, Definite, and Reverse Definite Languages

 Full-Text   Cite this paper

Abstract:

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\cdot (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 \floor{e \cdot (n-1)!} - \floor{e \cdot (n-2)!}. We prove the conjecture for n\le 4.

Full-Text