The hardness of solving simple word equations

DOI10.4230/LIPICS.MFCS.2017.18MaRDI QIDQ5111232zbMATH OpenOpenAlexFDO

Authors Joel D. Day, Florin Manea, Dirk Nowotka

Publication date 26 May 2020

Full work available at URL https://arxiv.org/abs/1702.07922

zbMATH Keywords

word equationsregular constraintsregular patterns

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Abstract: We investigate the class of regular-ordered word equations. In such equations, each variable occurs at most once in each side and the order of the variables occurring in both sides is the preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, we obtain that solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the minimal solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. Finally, we also show that a related class of simple word equations, that generalises one-variable equations, is in P.

Recommendations

• On the Solvability Problem for Restricted Classes of Word Equations
• On the complexity of solving restricted word equations
• scientific article; zbMATH DE number 1304322
• scientific article; zbMATH DE number 1408356
• Equations in words: An algorithmic contribution

Cites work

• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1304322 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A logic for document spanners
• An efficient algorithm for solving word equations
• Automata, Languages and Programming
• Complexity of Makanin's algorithm
• Context unification is in PSPACE
• Document Spanners: From Expressive Power to Decision Problems.
• Equations in Free Groups
• Finding a homomorphism between two words is NP-complete
• Minimal and complete word unification
• On the Solvability Problem for Restricted Classes of Word Equations
• On the parameterised complexity of string morphism problems
• One-variable word equations in linear time
• Pattern matching with variables: a multivariate complexity analysis
• Pattern matching with variables: fast algorithms and new hardness results
• Patterns with bounded treewidth
• Recompression: a simple and powerful technique for word equations
• Solutions of word equations over partially commutative structures
• The expressibility of languages and relations by word equations
• Word unification and transformation of generalized equations

Cited in

(10)

• scientific article; zbMATH DE number 1408356 (Why is no real title available?)
• scientific article; zbMATH DE number 7561688 (Why is no real title available?)
• Intricacies of simple word equations: an example
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• On the structure of solution-sets to regular word equations
• On the complexity of solving restricted word equations
• Word equations in the context of string solving
• Languages generated by conjunctive query fragments of FC[REG]
• Program specialization as a tool for solving word equations
• Languages generated by conjunctive query fragments of FC[REG]

This page was built for publication: The hardness of solving simple word equations

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