The existential theory of equations with rational constraints in free groups is PSPACE-complete

DOI10.1016/j.ic.2005.04.002zbMath1101.68649arXivcs/0103018OpenAlexW2039800792MaRDI QIDQ2573633

Volker Diekert, Christian Hagenah, Claudio Gutierrez

Publication date: 22 November 2005

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

LINEAR ESTIMATES FOR SOLUTIONS OF QUADRATIC EQUATIONS IN FREE GROUPS ⋮ Random equations in free groups ⋮ Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ On equations in free semigroups with certain constraints on their solutions. ⋮ Word equations in the context of string solving ⋮ Submonoids and rational subsets of groups with infinitely many ends. ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ On equations in free monoids and semigroups with restrictions on solutions ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ EQUATIONS IN FREE INVERSE MONOIDS ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Constrained synchronization and commutativity ⋮ The generalized conjugacy problem for virtually free groups ⋮ Word equations in non-deterministic linear space ⋮ AUTOMORPHIC ORBITS IN FREE GROUPS: WORDS VERSUS SUBGROUPS ⋮ Equations in groups that are virtually direct products ⋮ Solving one-variable equations in free groups ⋮ Graph Logics with Rational Relations ⋮ On systems of equations over free partially commutative groups ⋮ The isomorphism problem for toral relatively hyperbolic groups. ⋮ SLP compression for solutions of equations with constraints in free and hyperbolic groups ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Existential and positive theories of equations in graph products
• Makanin's algorithm is not primitive recursive
• Bounds on the index and period of a binary relation on a finite set
• Solving word equations modulo partial commutations
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of equations in free groups is in PSPACE
• Satisfiability of word equations with constants is in PSPACE
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Complexity of Makanin's algorithm
• The expressibility of languages and relations by word equations
• Monadic simultaneous rigid E-unification and related problems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item