Conservative groupoids recognize only regular languages
| Autor: | Mario Latendresse, Danny Dube, Pascal Tesson, Maxime Dubé, Martin Beaudry |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Higher-dimensional algebra Pure mathematics Class (set theory) Hierarchy (mathematics) Mathematics::Operator Algebras Semigroup 0102 computer and information sciences 02 engineering and technology 01 natural sciences Groupoid Computer Science Applications Theoretical Computer Science Computational Theory and Mathematics Regular language 010201 computation theory & mathematics Binary operation Mathematics::Category Theory 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Double groupoid Computer Science::Databases Information Systems Mathematics |
| Zdroj: | Information and Computation. 239:13-28 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2014.08.005 |
| Popis: | 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 L cons of regular languages that can be recognized in this way and explain how it fits within the well-known Straubing-Therien hierarchy. In particular we show that L cons contains depth 1/2 of the hierarchy and is entirely contained in depth 3/2. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect