Formal Languages and Groups as Memory

DOI10.1080/00927870802243580zbMath1163.68029arXivmath/0601061OpenAlexW1983966862MaRDI QIDQ3618533

Mark Kambites

Publication date: 2 April 2009

Published in: Communications in Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0601061

zbMATH Keywords

word problemcontext-free languagegroupmonoidautomatonrational transduction

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (27)

Unnamed Item ⋮ The inclusion structure of partially lossy queue monoids and their trace submonoids ⋮ The transformation monoid of a partially lossy queue ⋮ The emptiness problem for valence automata over graph monoids ⋮ On strong affine representations of the polycyclic monoids ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ The monoid of queue actions ⋮ Knapsack in graph groups ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Homing vector automata ⋮ Unnamed Item ⋮ Context-sensitive languages and G-automata ⋮ Polycyclic and Bicyclic Valence Automata ⋮ On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids ⋮ Languages Accepted by Weighted Restarting Automata* ⋮ Counter machines and crystallographic structures ⋮ Semigroup automata with rational initial and terminal sets ⋮ Unnamed Item ⋮ The algebraic theory of Parikh automata ⋮ Weighted automata with storage ⋮ New Results on Vector and Homing Vector Automata ⋮ Language classes associated with automata over matrix groups ⋮ Principal abstract families of weighted tree languages ⋮ Rational subsets of polycyclic monoids and valence automata ⋮ Automata with Counters that Recognize Word Problems of Free Products ⋮ Rational subsets and submonoids of wreath products.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On groups whose word problem is solved by a counter automaton.
• Groups, the theory of ends, and context-free languages
• On the rational subset problem for groups.
• The accessibility of finitely presented groups
• Finite automata with multiplication
• Remarks on blind and partially blind one-way multicounter machines
• Sequential grammars and automata with valences
• Word problems recognisable by deterministic blind monoid automata
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• Extended finite automata over groups

This page was built for publication: Formal Languages and Groups as Memory