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

complexityCayley graphgraph of groupspushdown automatacontext-free groupsThue-systems

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)