Languages recognized by finite aperiodic groupoids
| Autor: | Martin Beaudry |
|---|---|
| Rok vydání: | 1998 |
| Předmět: |
Monoid
General Computer Science Context-free language Syntactic monoid Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Algebra Regular language 010201 computation theory & mathematics Mathematics::Category Theory Formal language 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Homomorphism Nondeterministic finite automaton Variety (universal algebra) Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 209(1-2):299-317 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(97)00119-9 |
| Popis: | We study the context-free languages recognized by a groupoid G in terms of the algebraic properties of the multiplication monoid ω(G) of G. Concentrating on the case where ω(G) is group-free, we show that all regular languages can be recognized by groupoids for which M(G) is -trivial of threshold 2 and that all groupoids for which ω(G) belongs to the larger variety DA recognize only regular languages. Further, we give an example of a groupoid such that ω(G) is in the smallest variety outside of DA, and which recognizes all context-free languages not containing the empty word. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect