2014 | OriginalPaper | Buchkapitel
Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
verfasst von : Janusz Brzozowski, Marek Szykuła
Erschienen in: Developments in Language Theory
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.