2007/10/19 by Elaine Render, Render, Elaine, Mark Kambites +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #20M35 #68Q70 #Advanced Algebra and Logic #Chemical Synthesis and Analysis #FOS: Mathematics #Rings and Algebras (math.RA) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0710.3711
openalex publication_date 2007/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the classes of languages defined by valence automata with rational target sets (or equivalently, regular valence grammars with rational target sets), where the valence monoid is drawn from the important class of polycyclic monoids. We show that for polycyclic monoids of rank 2 or more, such automata accept exactly the context-free languages. For the polycyclic monoid of rank 1 (that is, the bicyclic monoid), they accept a class of languages strictly including the partially blind one-counter languages. Key to the proof is a description of the rational subsets of polycyclic and bicyclic monoids, other consequences of which include the decidability of the rational subset membership problem for these monoids, and the closure of the class of rational subsets under intersection and complement.