Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On Brzozowski’s Conjecture for the Free Burnside Semigroup Satisfying x 2 = x 3
verfasst von : Andrey N. Plyushchenko, Arseny M. Shur
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
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
In this paper we examine Brzozowski’s conjecture for the two-generated free Burnside semigroup satisfying
x
2
=
x
3
. The elements of this semigroup are classes of equivalent words, and the conjecture claims that all elements are regular languages. The case of the identity
x
2
=
x
3
is the only one, for which Brzozowski’s conjecture is neither proved nor disproved. We prove the conjecture for all the elements containing an overlap-free or an “almost” overlap-free word. In addition, we show that all but finitely many of these elements are “big” languages in terms of growth rate.