Solutions to twisted word equations and equations in virtually free groups

DOI10.1142/S0218196720500198MaRDI QIDQ3299596zbMATHOpenAlexFDO

Authors Volker Diekert, Murray Elder

Publication date 24 July 2020

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1820023 (Why is no real title available?)
• scientific article; zbMATH DE number 3974304 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 3589737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 848041 (Why is no real title available?)
• scientific article; zbMATH DE number 848090 (Why is no real title available?)
• scientific article; zbMATH DE number 7561603 (Why is no real title available?)
• scientific article; zbMATH DE number 7204548 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• A characterisation of virtually free groups.
• A taxonomy of complexity classes of functions
• Algorithmics on SLP-compressed strings: a survey
• Canonical representatives and equations in hyperbolic groups
• Context-Free Groups and Bass–Serre Theory
• Controlled iteration grammars and full hyper-AFL's
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Diophantine geometry over groups. VIII: Stability.
• Discrete algebraic methods. Arithmetic, cryptography, automata and groups
• Efficient randomized pattern-matching algorithms
• Elementary theory of free non-abelian groups.
• Finding all solutions of equations in free groups and monoids with involution
• Finite and infinite cyclic extensions of free groups
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups.
• Groups, the theory of ends, and context-free languages
• Kleene quotient theorems
• Logical aspects of Cayley-graphs: the group case
• Membership Problem for the Modular Group
• On the rational subsets of the free group
• Pregroups and Bass-Serre theory
• Quantitative Relativizations of Complexity Classes
• Recompression: a simple and powerful technique for word equations
• Satisfiability of equations in free groups is in \(\mathsf{PSPACE}\)
• Satisfiability of word equations with constants is in PSPACE
• Solution sets for equations over free groups are EDT0L languages
• Specular sets
• The Compressed Word Problem for Groups
• The accessibility of finitely presented groups
• The complexity of verbal languages over groups
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• The isomorphism problem for finite extensions of free groups is in PSPACE
• The structure of some subgroups of the modular group
• Theories of HNN-Extensions and Amalgamated Products
• Word equations in nondeterministic linear space
• Word-mappings of level 2

Cited in

(15)

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

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)