Automata with Counters that Recognize Word Problems of Free Products
Publication:5250278
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
word problemcontext-free languagefree productpolycyclic monoid\(G\)-automatonspecial word problem\(M\)-automatonmonoid with right invertible basis
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)
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