An efficient algorithm for solving word equations
From MaRDI portal
Publication:2931409
DOI10.1145/1132516.1132584zbMath1301.68165OpenAlexW2037286444MaRDI QIDQ2931409
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
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
