PSPACE-completeness of certain algorithmic problems on the subgroups of free groups

DOI10.1007/3-540-58201-0_75MaRDI QIDQ4632433zbMATH OpenOpenAlexFDO

Authors J.-C. Birget, S. W. Margolis, J. C. Meakin, Pascal Weil

Publication date 29 April 2019

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

Full work available at URL https://doi.org/10.1007/3-540-58201-0_75

zbMATH Keywords

algorithmic problemfinite automatonfinite indexstart stateTuring machine

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• On the complexity of intersection and conjugacy problems in free groups
• The Nielsen reduction and P-complete problems in free groups
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Complete problems for symmetric logspace involving free groups

Cites work

• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Complexity of some problems from the theory of automata
• Finite-automaton aperiodicity is PSPACE-complete
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• scientific article; zbMATH DE number 3869616 (Why is no real title available?)
• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3575812 (Why is no real title available?)
• Time/Space Trade-Offs for Reversible Computation
• Topology of finite graphs

Cited in

(9)

• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• On the rational subsets of the free group
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• On groups presented by inverse-closed finite confluent length-reducing rewriting systems
• scientific article; zbMATH DE number 988810 (Why is no real title available?)
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• The isomorphism problem for finite extensions of free groups is in PSPACE
• The Nielsen reduction and P-complete problems in free groups
• Groups with identities

This page was built for publication: PSPACE-completeness of certain algorithmic problems on the subgroups of free groups

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