Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals

Abstract

We solve two open problems concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a left ideal or a suffix-closed language with $n$ left quotients (that is, with state complexity $n$) is at most $n^{n-1}+n-1$, and that of a two-sided ideal or a factor-closed language is at most $n^{n-2}+(n-2)2^{n-2}+1$. Since these bounds are known to be reachable, this settles the problems.

15 pages, 7 figures

Cited by in corpus (3)

• A Survey on Operational State Complexity
• Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages
• Syntactic complexity of regular ideals