A4 Artikkeli konferenssijulkaisussa

One-unknown word equations and three-unknown constant-free word equations




Julkaisun tekijät: Dirk Nowotka, Aleksi Saarela

Konferenssin vakiintunut nimi: International Conference on Developments in Language Theory

Julkaisuvuosi: 2016

Kirjan nimi *: Developments in Language Theory: 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings

Sarjan nimi: Lecture Notes in Computer Science

Numero sarjassa: 9840

Volyymi: 9840

Sivujen määrä: 12

ISBN: 978-3-662-53131-0

eISBN: 978-3-662-53132-7

ISSN: 0302-9743

DOI: http://dx.doi.org/10.1007/978-3-662-53132-7_27


Tiivistelmä

We prove connections between one-unknown word equations and
three-unknown constant-free word equations, and use them to prove that
the number of equations in an independent system of three-unknown
constant-free equations is at most logarithmic with respect to the
length of the shortest equation in the system. We also study two
well-known conjectures. The first conjecture claims that there is a
constant c such that every one-unknown equation has either infinitely many solutions or at most c. The second conjecture claims that there is a constant c such that every independent system of three-unknown constant-free equations with a nonperiodic solution is of size at most c. We prove that the first conjecture implies the second one, possibly for a different constant.


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Last updated on 2021-24-06 at 11:35