Conservative groupoids recognize only regular languages

DOI10.1016/j.ic.2014.08.005zbMath1309.68132OpenAlexW1997591489MaRDI QIDQ476161

Pascal Tesson, Mario Latendresse, Danny Dubé, Maxime Dubé, Martin Beaudry

Publication date: 28 November 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.08.005

zbMATH Keywords

groupoidalgebraic automata theoryconservative algebra

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order logic and star-free sets
• Classifying regular events in symbolic logic
• General context-free recognition in less than cubic time
• Languages recognized by finite aperiodic groupoids
• Polynomial closure and unambiguous product
• Representation of undirected graphs by anticommutative conservative groupoids
• Finite loops recognize exactly the regular open languages
• Algebraic automata and context-free sets
• Automata, Languages and Programming