Back to Search
Start Over
Solutions to twisted word equations and equations in virtually free groups
- Source :
- International Journal of Algebra and Computation. 30:731-819
- Publication Year :
- 2020
- Publisher :
- World Scientific Pub Co Pte Lt, 2020.
-
Abstract
- It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or "small enough") finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and S\'enizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.<br />Comment: 72 pages, 14 figures. Small edits to the exposition in Section 15. An extended abstract of a preliminary version of this paper was presented at ICALP 2017
- Subjects :
- FOS: Computer and information sciences
Computer Science - Logic in Computer Science
Formal Languages and Automata Theory (cs.FL)
General Mathematics
010102 general mathematics
Computer Science - Formal Languages and Automata Theory
Group Theory (math.GR)
0102 computer and information sciences
Computational Complexity (cs.CC)
01 natural sciences
Logic in Computer Science (cs.LO)
Algebra
Computer Science - Computational Complexity
010201 computation theory & mathematics
FOS: Mathematics
0101 mathematics
Mathematics - Group Theory
03D05, 20F65, 20F70, 68Q25, 68Q45
Word (computer architecture)
Mathematics
PSPACE
Equation solving
Subjects
Details
- ISSN :
- 17936500 and 02181967
- Volume :
- 30
- Database :
- OpenAIRE
- Journal :
- International Journal of Algebra and Computation
- Accession number :
- edsair.doi.dedup.....d60209fbb6577badc42974142976e56b