On groups whose word problem is solved by a counter automaton.

DOI10.1016/j.tcs.2003.09.007zbMath1061.20029OpenAlexW1993619792MaRDI QIDQ596085

Gretchen Ostheimer, Gillian Z. Elston

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.09.007

zbMATH Keywords

subgroups of finite indexfinitely generated groupsword problemfinitely presented groupscontext-free languagesfree monoidsvirtually Abelian groupscounter automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Subgroup theorems; subgroup growth (20E07) Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

The (nested) word problem ⋮ On the rational subset problem for groups. ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ On the group memory complexity of extended finite automata over groups ⋮ A context-free and a 1-counter geodesic language for a Baumslag-Solitar group ⋮ Semigroup automata with rational initial and terminal sets ⋮ ON GROUPS AND COUNTER AUTOMATA ⋮ Word problems recognisable by deterministic blind monoid automata ⋮ Cone types and geodesic languages for lamplighter groups and Thompson's group \(F\). ⋮ Formal Languages and Groups as Memory ⋮ Language classes associated with automata over matrix groups ⋮ Automata with Counters that Recognize Word Problems of Free Products

Cites Work

• Groups, the theory of ends, and context-free languages
• The theory of ends, pushdown automata, and second-order logic
• FINITE AUTOMATA OVER FREE GROUPS
• On a subclass of context-free groups
• Unnamed Item
• Unnamed Item
• Unnamed Item