\texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata

DOI10.1016/S0304-3975(98)00225-4MaRDI QIDQ1575552zbMATH OpenFDO

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

Publication date 21 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

PSPACE-completenesspure subgroupssubgroups of the free groupinverse automata

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algebraic theory of languages and automata (68Q70) Structure and classification of infinite or finite groups (20E99)

Recommendations

• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• The Nielsen reduction and P-complete problems in free groups
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS

Cites work

• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 194088 (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 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• A Problem on Rational Subsets of the Free Group
• Complexity of some problems from the theory of automata
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• Finite-automaton aperiodicity is PSPACE-complete
• INVERSE MONOIDS OF DOT-DEPTH TWO
• On the complexity of intersection and conjugacy problems in free groups
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• The Nielsen reduction and P-complete problems in free groups
• Time/Space Trade-Offs for Reversible Computation
• Topology of finite graphs

Cited in

(21)

• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• Statistics of subgroups of the modular group
• Relative order and spectrum in free and related groups
• MALNORMAL SUBGROUPS OF FREE GROUPS
• A tribute to John Meakin on the occasion of his 75th birthday
• On the transition monoid of the Stallings automaton of a subgroup of a free group
• AN APPLICATION OF FIRST-ORDER LOGIC TO THE STUDY OF RECOGNIZABLE LANGUAGES
• On the rational subset problem for groups.
• Computing subgroup presentations, using the coherence arguments of McCammond and Wise.
• COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY
• Statistical properties of subgroups of free groups.
• A list of applications of Stallings automata
• On the Generalized Membership Problem in Relatively Hyperbolic Groups
• READING OFF KUROSH DECOMPOSITIONS
• STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
• Graphs, intersections of subgroups of free groups and corank
• Some properties of Ising automata
• scientific article; zbMATH DE number 988810 (Why is no real title available?)
• On the complexity of inverse semigroup conjugacy
• Decision problems for reversible and permutation automata
• Graph immersions, inverse monoids and deck transformations

This page was built for publication: \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata

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