Two-variable word equations

DOI10.1051/ITA:2000126MaRDI QIDQ2729626zbMATH OpenOpenAlexFDO

Authors Lucian Ilie, Wojciech Plandowski

Publication date 23 July 2001

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2000__34_6_467_0/, https://eudml.org/doc/222085

zbMATH Keywords

Sturmian wordsword equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1500512
• On word equations in one variable
• Automata, Languages and Programming
• Efficient solving of the word equations in one variable
• On the complexity of solving restricted word equations

Cites work

• Complexity of Makanin's algorithm
• Decision problems for patterns
• Equations in free semigroups
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3991618 (Why is no real title available?)
• scientific article; zbMATH DE number 1346496 (Why is no real title available?)
• scientific article; zbMATH DE number 5051583 (Why is no real title available?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• On the expressibility of languages by word equations with a bounded number of variables
• Some combinatorial properties of Sturmian words
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Cited in

(12)

• Word equations in the context of string solving
• Standard words and solutions of the word equation \(X_1^2\cdots X_n^2=(X_1\cdots X_n)^2\)
• A logic for document spanners
• On PSPACE generation of a solution set of a word equation and its applications
• Codes of central Sturmian words
• Finding all solutions of equations in free groups and monoids with involution
• Word Equations with One Unknown
• scientific article; zbMATH DE number 1500512 (Why is no real title available?)
• Automata, Languages and Programming
• On word equations in one variable
• Solving one variable word equations in the free group in cubic time
• Farey codes and languages

This page was built for publication: Two-variable word equations

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