The hardness of solving simple word equations

DOI10.4230/LIPICS.MFCS.2017.18zbMATH Open1441.68089arXiv1702.07922OpenAlexW2591974499MaRDI QIDQ5111232FDOQ5111232

Florin Manea, Joel D. Day, Dirk Nowotka

Publication date: 26 May 2020

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• One-variable word equations in linear time
• An efficient algorithm for solving word equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Context Unification is in PSPACE
• Automata, Languages and Programming
• Minimal and complete word unification
• Patterns with bounded treewidth
• Finding a homomorphism between two words is NP-complete
• On the parameterised complexity of string morphism problems
• Pattern matching with variables: a multivariate complexity analysis
• Recompression
• Complexity of Makanin's algorithm
• Title not available (Why is that?)
• Equations in Free Groups
• The expressibility of languages and relations by word equations
• Word unification and transformation of generalized equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Document Spanners: From Expressive Power to Decision Problems.
• Title not available (Why is that?)
• On the Solvability Problem for Restricted Classes of Word Equations

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of solution-sets to regular 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)