An efficient algorithm for solving word equations

DOI10.1145/1132516.1132584MaRDI QIDQ2931409zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On PSPACE generation of a solution set of a word equation and its applications
• On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
• Efficient solving of the word equations in one variable
• Solving word equations
• Satisfiability of word equations with constants is in NEXPTIME

Cited in

(28)

• Solution sets for equations over free groups are EDT0L languages
• The expressibility of languages and relations by word equations
• One-variable word equations in linear time
• scientific article; zbMATH DE number 6678923 (Why is no real title available?)
• An SMT solver for regular expressions and linear arithmetic over string length
• On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
• The hardness of solving simple word equations
• On the Solvability Problem for Restricted Classes of Word Equations
• Solving String Theories Involving Regular Membership Predicates Using SAT
• Solution sets for equations over free groups are EDT0L languages
• A solver for arrays with concatenation
• Equations in words: An algorithmic contribution
• Symbolic automata for representing big code
• Word-mappings of level 2
• On solving word equations using SAT
• On the complexity of solving restricted word equations
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Word equations in the context of string solving
• Finding all solutions of equations in free groups and monoids with involution
• Satisfiability of word equations with constants is in NEXPTIME
• Z3str2: an efficient solver for strings, regular expressions, and length constraints
• Automata, Languages and Programming
• Program specialization as a tool for solving word equations
• On the satisfiability of context-free string constraints with subword-ordering
• The expressibility of languages and relations by word equations
• Makanin's algorithm for word equations-two improvements and a generalization
• Unification modulo lists with reverse relation with certain word equations
• Chain-free string constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931409)