\texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
DOI10.1016/S0304-3975(98)00225-4zbMATH Open0944.68100MaRDI QIDQ1575552FDOQ1575552
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)
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of some problems from the theory of automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Topology of finite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finite-automaton aperiodicity is PSPACE-complete
- Title not available (Why is that?)
- Title not available (Why is that?)
- FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
- Time/Space Trade-Offs for Reversible Computation
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
- The Nielsen reduction and P-complete problems in free groups
- On the complexity of intersection and conjugacy problems in free groups
- INVERSE MONOIDS OF DOT-DEPTH TWO
- A Problem on Rational Subsets of the Free Group
Cited In (21)
- Graphs, intersections of subgroups of free groups and corank
- A list of applications of Stallings automata
- Statistical properties of subgroups of free groups.
- Graph immersions, inverse monoids and deck transformations
- 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
- Some properties of Ising automata
- Two-letter group codes that preserve aperiodicity of inverse finite automata.
- Relative order and spectrum in free and related groups
- On the rational subset problem for groups.
- READING OFF KUROSH DECOMPOSITIONS
- Statistics of subgroups of the modular group
- Computing subgroup presentations, using the coherence arguments of McCammond and Wise.
- On the complexity of inverse semigroup conjugacy
- On the Generalized Membership Problem in Relatively Hyperbolic Groups
- MALNORMAL SUBGROUPS OF FREE GROUPS
- COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY
- AN APPLICATION OF FIRST-ORDER LOGIC TO THE STUDY OF RECOGNIZABLE LANGUAGES
- Decision problems for reversible and permutation automata
- Title not available (Why is that?)
- STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
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)
