An efficient algorithm for solving word equations

DOI10.1145/1132516.1132584zbMath1301.68165OpenAlexW2037286444MaRDI QIDQ2931409

Wojciech Plandowski

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132584

zbMATH Keywords

word equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (17)

An SMT solver for regular expressions and linear arithmetic over string length ⋮ Solution Sets for Equations over Free Groups are EDT0L Languages ⋮ Symbolic automata for representing big code ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Word equations in the context of string solving ⋮ A solver for arrays with concatenation ⋮ Word-mappings of level 2 ⋮ Chain-Free String Constraints ⋮ Z3str2: an efficient solver for strings, regular expressions, and length constraints ⋮ Unnamed Item ⋮ On the Complexity of Solving Restricted Word Equations ⋮ On the Solvability Problem for Restricted Classes of Word Equations ⋮ Unification modulo lists with reverse relation with certain word equations ⋮ Solution sets for equations over free groups are EDT0L languages ⋮ The hardness of solving simple word equations ⋮ On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note) ⋮ One-variable word equations in linear time

This page was built for publication: An efficient algorithm for solving word equations