Citation
Beaudry, M., Dube, D., Dube, M., Latendresse, M., & Tesson, P. (2014). Conservative groupoids recognize only regular languages. Information and Computation, 239, 13-28.
Abstract
The notion of recognition of a language by a finite semigroup can be generalized to recognition by finite groupoids, i.e. sets equipped with a binary operation ‘⋅’ which is not necessarily associative. It is well known that L can be recognized by a groupoid iff L is context-free. However it is also known that some subclasses of groupoids can only recognize regular languages.
A groupoid H is said to be conservative if a⋅b∈{a,b} for all a,b∈H. The first result of this paper is that conservative groupoids can only recognize regular languages. This class of groupoids is incomparable with the ones identified so far which share this property, so we are exhibiting a new way in which a groupoid can be too weak to recognize non-regular languages.
We also study the class Lcons of regular languages that can be recognized in this way and explain how it fits within the well-known Straubing–Thérien hierarchy. In particular we show that Lcons contains depth 1/2 of the hierarchy and is entirely contained in depth 3/2.
Keywords: Groupoid, Conservative algebra, Algebraic automata theory.
