An effective version of Stallings' theorem in the case of context-free groups

DOI10.1007/3-540-56939-1_96zbMath1422.20010OpenAlexW1541384626MaRDI QIDQ4630285

Géraud Sénizergues

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_96

zbMATH Keywords

complexityCayley graphgraph of groupspushdown automatacontext-free groupsThue-systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Thue and Post systems, etc. (03D03)

Related Items (6)

Automatic graphs and D0L-sequences of finite graphs ⋮ The isomorphism problem for finite extensions of free groups is in PSPACE ⋮ On the rational subsets of the free group ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups and NTS languages
• Groups, the theory of ends, and context-free languages
• The theory of ends, pushdown automata, and second-order logic
• Actions of finite groups of graphs and related automorphisms of free groups
• On torsion-free groups with infinitely many ends
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Groups of cohomological dimension one

This page was built for publication: An effective version of Stallings' theorem in the case of context-free groups