One-variable word equations in linear time

DOI10.1007/S00453-014-9931-3MaRDI QIDQ261339zbMATHOpenAlexWikidataFDO

Authors Artur Jeż

Publication date 23 March 2016

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

one-variable equationsstring unificationword equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is O(n + #_X log n), where #_X is the number of appearances of the variable in the equation. This matches the previously-best algorithm due to Dk{a}browski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis the running time is lowered to O(n) in RAM model. Unfortunately no new properties of solutions are shown.

Recommendations

• One-variable word equations in linear time
• scientific article; zbMATH DE number 1929939
• Recompression: word equations and beyond
• On word equations in one variable
• Efficient solving of the word equations in one variable

Cites work

• scientific article; zbMATH DE number 6678923 (Why is no real title available?)
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1346496 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• A fully linear-time approximation algorithm for grammar-based compression
• An efficient algorithm for solving word equations
• Approximation of Grammar-Based Compression via Recompression
• Approximation of smallest linear tree grammar
• Automata, Languages and Programming
• Compressed membership in automata with compressed labels
• Context unification is in PSPACE
• Efficient solving of the word equations in one variable
• Linear work suffix array construction
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On word equations in one variable
• Recursive Star-Tree Parallel Data Structure
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of word equations with constants is in PSPACE
• The complexity of compressed membership problems for finite automata
• Word equations with one unknown

Cited in

(12)

• scientific article; zbMATH DE number 1929939 (Why is no real title available?)
• On word equations in one variable
• One-variable word equations and three-variable constant-free word equations
• Word equations in the context of string solving
• Approximation of smallest linear tree grammar
• The hardness of solving simple word equations
• One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations
• An optimal bound on the solution sets of one-variable word equations and its consequences
• An optimal bound on the solution sets of one-variable word equations and its consequences
• One-variable word equations in linear time
• On the Solvability Problem for Restricted Classes of Word Equations
• On the complexity of solving restricted word equations

This page was built for publication: One-variable word equations in linear time

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