On word equations in one variable

DOI10.1007/S00453-009-9375-3zbMath1216.68125OpenAlexW2041189577MaRDI QIDQ547296

Robert Dąbrowski, Wojciech Plandowski

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9375-3

zbMATH Keywords

computational complexityword equationalgorithm analysis and designequation in free semigroup

Mathematics Subject Classification ID

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

Related Items (8)

What Is Essential Unification? ⋮ On the Complexity of Solving Restricted Word Equations ⋮ One-Variable Word Equations and Three-Variable Constant-Free Word Equations ⋮ One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations ⋮ Unification modulo lists with reverse relation with certain word equations ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences ⋮ An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences ⋮ One-variable word equations in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equations in words: An algorithmic contribution
• Two-variable word equations
• Satisfiability of word equations with constants is in NEXPTIME
• Complexity of Makanin's algorithm

This page was built for publication: On word equations in one variable