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

DOI10.1007/3-540-58201-0_75zbMath1418.68098OpenAlexW1596663438MaRDI QIDQ4632433

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

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

finite automatonTuring machinefinite indexalgorithmic problemstart state

Mathematics Subject Classification ID

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

Related Items (1)

On the rational subsets of the free group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Time/Space Trade-Offs for Reversible Computation
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS

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