Word problems recognisable by deterministic blind monoid automata

DOI10.1016/j.tcs.2006.06.026zbMath1100.68051arXivmath/0506137OpenAlexW1972774698MaRDI QIDQ2508978

Mark Kambites

Publication date: 20 October 2006

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

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

zbMATH Keywords

word problemgroupmonoidautomatonfinite index subgroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (11)

\(\mathcal C\)-graph automatic groups. ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ Unnamed Item ⋮ On the group memory complexity of extended finite automata over groups ⋮ The loop problem for Rees matrix semigroups. ⋮ Semigroup automata with rational initial and terminal sets ⋮ ON GROUPS AND COUNTER AUTOMATA ⋮ Formal Languages and Groups as Memory ⋮ Anisimov's Theorem for inverse semigroups ⋮ Automata with Counters that Recognize Word Problems of Free Products

Cites Work

• 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
• Finite automata with multiplication
• Remarks on blind and partially blind one-way multicounter machines
• FINITE AUTOMATA OVER FREE GROUPS
• Extended finite automata over groups

This page was built for publication: Word problems recognisable by deterministic blind monoid automata