Efficient solving of the word equations in one variable

DOI10.1007/3-540-58338-6_80MaRDI QIDQ5096891zbMATH OpenOpenAlexFDO

Authors

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58338-6_80

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• scientific article; zbMATH DE number 1929939
• Word Equations with One Unknown
• On word equations in one variable
• Automata, Languages and Programming
• Makanin's algorithm for word equations-two improvements and a generalization

Cites work

• Algorithme quadratique de calcul de la solution générale d'équations en mots à une variable
• An optimal algorithm for computing the repetitions in a word
• Complexity of Makanin's algorithm
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1346496 (Why is no real title available?)
• scientific article; zbMATH DE number 3355024 (Why is no real title available?)
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Cited in

(20)

• One-variable word equations in linear time
• Two-variable word equations
• An efficient algorithm for solving word equations
• scientific article; zbMATH DE number 6678923 (Why is no real title available?)
• Word equations with one unknown
• scientific article; zbMATH DE number 17526 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1346493 (Why is no real title available?)
• scientific article; zbMATH DE number 1500512 (Why is no real title available?)
• On the complexity of solving restricted word equations
• One-variable word equations and three-variable constant-free word equations
• Studying word equations by a method of weighted frequencies
• scientific article; zbMATH DE number 1929939 (Why is no real title available?)
• 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
• Mathematical Foundations of Computer Science 2003
• Automata, Languages and Programming
• On word equations in one variable
• Solving one variable word equations in the free group in cubic time

This page was built for publication: Efficient solving of the word equations in one variable

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