Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Groupoids That Recognize Only Regular Languages
(Extended Abstract)
verfasst von : Martin Beaudry, François Lemieux, Denis Thérien
Erschienen in: Automata, Languages and Programming
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
Finite semigroups, i.e. finites sets equipped with a binary associative operation, have played a role in theoretical computer science for fifty years. They were first observed to be closely related to finite automata, hence, by the famous theorem of Kleene, to regular languages. It was later understood that this association is very deep and the theory of pseudo-varieties of Schützenberger and Eilenberg [5] became the accepted framework in which to discuss computations realized by finite-state machines. It is today fair to say that semigroups and automata are so tightly intertwined that it makes little sense to study one without the other.