Solutions to twisted word equations and equations in virtually free groups

DOI10.1142/S0218196720500198zbMATH Open1481.20118arXiv1701.03297OpenAlexW2995323499MaRDI QIDQ3299596FDOQ3299596

Murray Elder, Volker Diekert

Publication date: 24 July 2020

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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 $mathsfPSPACE$. 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 $mathsfPSPACE$ 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 $mathsfNSPACE(n^{2}logn)$, 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.

Full work available at URL: https://arxiv.org/abs/1701.03297

Recommendations

• scientific article; zbMATH DE number 7204548
• Solution sets for equations over free groups are EDT0L languages
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups.
• The generalized conjugacy problem for virtually free groups.
• scientific article; zbMATH DE number 1941341

zbMATH Keywords

\textsf{PSPACE}EDT0L languageequation in a virtually free grouptwisted equation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Cites Work

• Title not available (Why is that?)
• A taxonomy of complexity classes of functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discrete algebraic methods. Arithmetic, cryptography, automata and groups
• The Complexity of Verbal Languages over Groups
• Satisfiability of word equations with constants is in PSPACE
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Elementary theory of free non-abelian groups.
• Algorithmics on SLP-compressed strings: a survey
• Efficient randomized pattern-matching algorithms
• Finite and infinite cyclic extensions of free groups
• Diophantine geometry over groups. VIII: Stability.
• The accessibility of finitely presented groups
• Canonical representatives and equations in hyperbolic groups
• Solution sets for equations over free groups are EDT0L languages
• Recompression
• Satisfiability of equations in free groups is in PSPACE
• Finding all solutions of equations in free groups and monoids with involution
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups
• Theories of HNN-Extensions and Amalgamated Products
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantitative Relativizations of Complexity Classes
• Logical aspects of Cayley-graphs: the group case
• Groups, the theory of ends, and context-free languages
• Context-Free Groups and Bass–Serre Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the rational subsets of the free group
• Title not available (Why is that?)
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• The structure of some subgroups of the modular group
• Pregroups and Bass-Serre theory
• The isomorphism problem for finite extensions of free groups is in PSPACE
• Controlled iteration grammars and full hyper-AFL's
• Kleene quotient theorems
• Title not available (Why is that?)
• A characterisation of virtually free groups.
• The Compressed Word Problem for Groups
• Title not available (Why is that?)
• Membership Problem for the Modular Group
• Word-mappings of level 2
• Title not available (Why is that?)
• Title not available (Why is that?)
• Specular sets

Cited In (11)

• On equations and first-order theory of one-relator monoids
• Groups with context-free Diophantine problem
• Equations in virtually class \(2\) nilpotent groups
• Title not available (Why is that?)
• The complexity of solution sets to equations in hyperbolic groups
• Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups
• MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
• EDT0L solutions to equations in group extensions
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices
• Word equations in non-deterministic linear space
• Equations in virtually abelian groups: Languages and growth

This page was built for publication: Solutions to twisted word equations and equations in virtually free groups

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