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

DOI10.1016/J.TCS.2005.07.012MaRDI QIDQ2575750zbMATH OpenOpenAlexFDO

Authors 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 numbersFibonacci wordWord equationsParametrizability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Recommendations

• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1186371
• Word equations in non-deterministic linear space
• Towards parametrizing word equations
• Word equations in nondeterministic linear space
• On the system of word equations \(x^ i_ 1 x^ i_ 2\dots x^ i_ m=y^ i_ 1 y^ i_ 2\dots y^ i_ n\) \((i=1,2,\dots)\) in a free monoid
• Satisfiability of word equations with constants is in NEXPTIME
• Parametrizability by regular expressions for equations on words
• The parametrisation of Solutions of the equation x–1y–1xyz–1v–1zv=1 in a free group
• scientific article; zbMATH DE number 1234888

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 4072416 (Why is no real title available?)
• scientific article; zbMATH DE number 4083904 (Why is no real title available?)
• scientific article; zbMATH DE number 88856 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3805807 (Why is no real title available?)
• scientific article; zbMATH DE number 3350192 (Why is no real title available?)
• scientific article; zbMATH DE number 3407957 (Why is no real title available?)
• scientific article; zbMATH DE number 3198887 (Why is no real title available?)
• scientific article; zbMATH DE number 3090158 (Why is no real title available?)
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Equations in Free Groups
• Equations in free semigroups
• Mathematical Foundations of Computer Science 2004
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• ON THE PARAMETERIZATION OF SOLUTIONS FOR EQUATIONS IN FREE GROUPS
• On cube-free \(\omega\)-words generated by binary morphisms
• One-Variable Equations in Free Groups
• Repetitions in the Fibonacci infinite word
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of word equations with constants is in PSPACE
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Word equation \(ABC=CDA\), \(B\neq D\).

Cited in

(8)

• Equations on partial words
• An Analysis and a Reproof of Hmelevskii’s Theorem
• Word equations in the context of string solving
• Multiple constraints on three and four words
• A logic for document spanners
• Intricacies of simple word equations: an example
• Mathematical Foundations of Computer Science 2004
• ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS

This page was built for publication: The non-parametrizability of the word equation \(xyz=zvx\): a short proof

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