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

DOI10.1007/3-540-56939-1_96MaRDI QIDQ4630285zbMATH OpenOpenAlexFDO

Authors 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

Cayley graphcomplexitycontext-free groupsgraph of groupspushdown automataThue-systems

Mathematics Subject Classification ID

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

Recommendations

• The isomorphism problem for finite extensions of free groups is in PSPACE
• Context-Free Groups and Bass–Serre Theory
• STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
• Groups, the theory of ends, and context-free languages
• Prefix-rewriting on context-free groups

Cites work

• Actions of finite groups of graphs and related automorphisms of free groups
• Groups and NTS languages
• Groups of cohomological dimension one
• Groups, the theory of ends, and context-free languages
• scientific article; zbMATH DE number 3912630 (Why is no real title available?)
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 44695 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 848090 (Why is no real title available?)
• scientific article; zbMATH DE number 3381862 (Why is no real title available?)
• On torsion-free groups with infinitely many ends
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The theory of ends, pushdown automata, and second-order logic

Cited in

(9)

• Automatic graphs and D0L-sequences of finite graphs
• On the rational subsets of the free group
• On groups presented by inverse-closed finite confluent length-reducing rewriting systems
• Context-Free Groups and Bass–Serre Theory
• READING OFF KUROSH DECOMPOSITIONS
• Groups, graphs, languages, automata, games and second-order monadic logic
• The isomorphism problem for finite extensions of free groups is in PSPACE
• The big-O problem
• Logical aspects of Cayley-graphs: the group case

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

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