Solutions to twisted word equations and equations in virtually free groups

DOI10.1142/S0218196720500198zbMath1481.20118arXiv1701.03297OpenAlexW2995323499MaRDI QIDQ3299596

Volker Diekert, Murray J. 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

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

Related Items (7)

The complexity of solution sets to equations in hyperbolic groups ⋮ Equations in virtually abelian groups: Languages and growth ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ EDT0L solutions to equations in group extensions ⋮ Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups ⋮ Word equations in non-deterministic linear space ⋮ On equations and first-order theory of one-relator monoids

Cites Work

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

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