ON GROUPS AND COUNTER AUTOMATA

DOI10.1142/S0218196708004901zbMath1171.20021arXivmath/0611188OpenAlexW3099805887MaRDI QIDQ3601328

Mark Kambites, Gretchen Ostheimer, Murray J. Elder

Publication date: 10 February 2009

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

finitely generated groupsword problemgrowth of groupscounter languagesgroup automatablind counter automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (12)

The word problem of \(\mathbb{Z}^n\) is a multiple context-free language ⋮ Geodesic growth in virtually abelian groups ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ The loop problem for Rees matrix semigroups. ⋮ Counter machines and crystallographic structures ⋮ Language classes associated with automata over matrix groups ⋮ THE IDEMPOTENT PROBLEM FOR AN INVERSE MONOID ⋮ Automatic presentations for semigroups. ⋮ Groups Whose Word Problem is a Petri Net Language ⋮ Anisimov's Theorem for inverse semigroups ⋮ Automata with Counters that Recognize Word Problems of Free Products

Cites Work

• 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.
• An effective bound for groups of linear growth
• The accessibility of finitely presented groups
• Group presentations, formal languages and characterizations of one- counter groups
• Remarks on the complexity of nondeterministic counter languages
• Remarks on blind and partially blind one-way multicounter machines
• Word problems recognisable by deterministic blind monoid automata
• On torsion-free groups with infinitely many ends
• Subgroups of finitely presented groups
• An algebraic characterization of groups with soluble word problem
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• On Context-Free Languages

This page was built for publication: ON GROUPS AND COUNTER AUTOMATA