Finding all solutions of equations in free groups and monoids with involution

DOI10.1016/j.ic.2016.09.009zbMath1382.68347OpenAlexW2963645376MaRDI QIDQ342722

Artur Jeż, Wojciech Plandowski, Volker Diekert

Publication date: 18 November 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.09.009

zbMATH Keywords

word equationsstring unificationequations in free groupsequations in free monoids with involutionregular constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semigroups in automata theory, linguistics, etc. (20M35) Algorithms on strings (68W32) Algebraic geometry over groups; equations over groups (20F70)

Related Items (12)

The Diophantine problem in the classical matrix groups ⋮ The complexity of solution sets to equations in hyperbolic groups ⋮ Word equations in the context of string solving ⋮ Relative order and spectrum in free and related groups ⋮ Post's Correspondence Problem for hyperbolic and virtually nilpotent groups ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Word equations in non-deterministic linear space ⋮ Unnamed Item ⋮ Orientable quadratic equations in free metabelian groups ⋮ Unification modulo lists with reverse relation with certain word equations ⋮ Deterministic regular expressions with back-references ⋮ On PSPACE generation of a solution set of a word equation and its applications

Cites Work

• Elementary theory of free non-abelian groups.
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups
• Canonical representatives and equations in hyperbolic groups
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Diophantine geometry over groups. VIII: Stability.
• Solving word equations modulo partial commutations
• Two-variable word equations
• Satisfiability of word equations with constants is in NEXPTIME
• Solution sets for equations over free groups are EDT0L languages
• An efficient algorithm for solving word equations
• Recompression
• Satisfiability of equations in free groups is in PSPACE
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• WORD EQUATIONS OVER GRAPH PRODUCTS
• 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
• Complexity of Makanin's algorithm
• Makanin's algorithm for word equations-two improvements and a generalization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding all solutions of equations in free groups and monoids with involution