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

DOI10.1016/S0304-3975(98)00225-4zbMath0944.68100MaRDI QIDQ1575552

John C. Meakin, Stuart W. Margolis, Jean-Camille Birget, Pascal Weil

Publication date: 21 August 2000

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

zbMATH Keywords

pure subgroupsinverse automataPSPACE-completenesssubgroups of the free group

Mathematics Subject Classification ID

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

Related Items

COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY, MALNORMAL SUBGROUPS OF FREE GROUPS, Some properties of Ising automata, On the Generalized Membership Problem in Relatively Hyperbolic Groups, On the rational subset problem for groups., STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS, On the complexity of inverse semigroup conjugacy, On the transition monoid of the Stallings automaton of a subgroup of a free group, Relative order and spectrum in free and related groups, READING OFF KUROSH DECOMPOSITIONS, A tribute to John Meakin on the occasion of his 75th birthday, Two-letter group codes that preserve aperiodicity of inverse finite automata., AN APPLICATION OF FIRST-ORDER LOGIC TO THE STUDY OF RECOGNIZABLE LANGUAGES, Statistical properties of subgroups of free groups, A list of applications of Stallings automata, Computing subgroup presentations, using the coherence arguments of McCammond and Wise., GRAPH IMMERSIONS, INVERSE MONOIDS AND DECK TRANSFORMATIONS, Graphs, intersections of subgroups of free groups and corank, Statistics of subgroups of the modular group

Cites Work

• The Nielsen reduction and P-complete problems in free groups
• On the complexity of intersection and conjugacy problems in free groups
• Finite-automaton aperiodicity is PSPACE-complete
• Topology of finite graphs
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Complexity of some problems from the theory of automata
• A Problem on Rational Subsets of the Free Group
• Time/Space Trade-Offs for Reversible Computation
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• INVERSE MONOIDS OF DOT-DEPTH TWO
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item