A4 Article in conference proceedings

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




List of Authors: Dirk Nowotka, Aleksi Saarela

Conference name: International Conference on Developments in Language Theory

Publication year: 2016

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

Title of series: Lecture Notes in Computer Science

Number in series: 9840

Volume number: 9840

Number of pages: 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


Abstract

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.


Downloadable publication

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