19 citations · 121 across the 33 of their papers we have counts for
Showing 2014 · cs.FLShow all
3 papers · 2 filters
cs.FL2014
Syntactic Complexity of Suffix-Free Languages
Janusz Brzozowski, Marek Szykuła
We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with left quotients (that is, with…
cs.FL2014★ 7 cited
Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
Janusz Brzozowski, Marek Szykuła
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 left quoti…
cs.FL2014★ 1 cited
Large Aperiodic Semigroups
Janusz Brzozowski, Marek Szykuła
The syntactic complexity of a regular language is the size of its syntactic semigroup. This semigroup is isomorphic to the transition semigroup of the minimal deterministic finite…