%0 Journal Article
%T Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
%A Janusz Brzozowski
%A Marek SzykuŁża
%J Computer Science
%D 2014
%I arXiv
%X 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.
%U http://arxiv.org/abs/1403.2090v2