The non-parametrizability of the word equation \(xyz=zvx\): a short proof

DOI10.1016/j.tcs.2005.07.012zbMath1079.68081MaRDI QIDQ2575750

Elena Czeizler

Publication date: 6 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.012

zbMATH Keywords

Fibonacci numbers; Fibonacci word; Word equations; Parametrizability

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

Related Items

Word equations in the context of string solving, A logic for document spanners, Multiple constraints on three and four words, ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS, Equations on partial words

Cites Work

• Equations in free semigroups
• On cube-free \(\omega\)-words generated by binary morphisms
• Word equation \(ABC=CDA\), \(B\neq D\).
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of word equations with constants is in PSPACE
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• Equations in Free Groups
• Repetitions in the Fibonacci infinite word
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• ON THE PARAMETERIZATION OF SOLUTIONS FOR EQUATIONS IN FREE GROUPS
• Mathematical Foundations of Computer Science 2004
• One-Variable Equations in Free Groups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item