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

DOI10.1016/J.TCS.2005.07.012zbMATH Open1079.68081OpenAlexW1986741335MaRDI QIDQ2575750FDOQ2575750

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

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

zbMATH Keywords

Fibonacci numbersFibonacci wordWord equationsParametrizability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)