Bounded automata groups are co-ET0L

DOI10.1007/978-3-030-13435-8_6MaRDI QIDQ2278264zbMATH OpenOpenAlexFDO

Authors Alex Bishop, Murray Elder

Publication date 4 December 2019

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

zbMATH Keywords

bounded automata groupcheck-stack pushdown automatonco-word problemET0L languageformal language theory

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic theory of languages and automata (68Q70)

Abstract: Holt and R"over proved that finitely generated bounded automata groups have indexed co-word problem. Here we sharpen this result to show they are in fact co-ET0L.

Cited in

(10)

• The complexity of solution sets to equations in hyperbolic groups
• EDT0L solutions to equations in group extensions
• On elementary amenable bounded automata groups
• Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE
• Herzog–Schönheim conjecture, vanishing sums of roots of Unity and convex polygons
• The word problem for finitary automaton groups
• Quadratic Diophantine equations, the Heisenberg group and formal languages
• Decision problems concerning L systems
• On the ET0L subgroup membership problem in bounded automata groups
• On groups with EDT0L word problem

This page was built for publication: Bounded automata groups are co-ET0L

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278264)