On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations

DOI10.1007/978-3-642-02737-6_36zbMath1247.68214OpenAlexW1578904750MaRDI QIDQ3637246

Aleksi Saarela

Publication date: 7 July 2009

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (6)

Systems of word equations, polynomials and linear algebra: a new approach ⋮ On the Solution Sets of Entire Systems of Word Equations ⋮ One-Variable Word Equations and Three-Variable Constant-Free Word Equations ⋮ On maximal chains of systems of word equations ⋮ One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of Ehrenfeucht's conjecture
• Equations in free semigroups
• Rational sets in commutative monoids
• ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS
• An Analysis and a Reproof of Hmelevskii’s Theorem
• Satisfiability of word equations with constants is in PSPACE
• On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Compactness of Systems of Equations in Semigroups

This page was built for publication: On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations