On the structure of solution-sets to regular word equations

DOI10.1007/s00224-021-10058-5MaRDI QIDQ6614609

Florin Manea, Joel D. Day

Publication date: 7 October 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

NPstring solvingquadratic word equationsregular word equations

Mathematics Subject Classification ID

Theory of computing (68Qxx) General logic (03Bxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding all solutions of equations in free groups and monoids with involution
• The dag-width of directed graphs
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings
• Document spanners: from expressive power to decision problems
• The satisfiability of word equations: decidable and undecidable theories
• A logic for document spanners
• Satisfiability of word equations with constants is in NEXPTIME
• String solving with word equations and transducers: towards a logic for analysing mutation XSS
• Recompression
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The expressibility of languages and relations by word equations
• On the Complexity of Solving Restricted Word Equations
• The hardness of solving simple word equations
• Mathematical Foundations of Computer Science 2004
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• Makanin's algorithm for word equations-two improvements and a generalization

This page was built for publication: On the structure of solution-sets to regular word equations