Automata with Counters that Recognize Word Problems of Free Products

DOI10.1142/s0129054115500045zbMath1405.68194OpenAlexW1989328735MaRDI QIDQ5250278

Lance L. Ross, Jon Michael Corson

Publication date: 19 May 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054115500045

zbMATH Keywords

word problemcontext-free languagefree productpolycyclic monoid\(G\)-automatonspecial word problem\(M\)-automatonmonoid with right invertible basis

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (max. 100)

Context-sensitive languages and G-automata

Cites Work

• On groups whose word problem is solved by a counter automaton.
• Topology of finite graphs
• Free products with amalgamation of monoids
• Semigroup automata with rational initial and terminal sets
• Word problems recognisable by deterministic blind monoid automata
• ON GROUPS AND COUNTER AUTOMATA
• Formal Languages and Groups as Memory
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• A representation theorem for algebraic and context-free power series in noncommuting variables
• Extended finite automata over groups

This page was built for publication: Automata with Counters that Recognize Word Problems of Free Products