Tero Harju and Dirk Nowotka
On the Independence of Equations in Three Variables


Theoretical Computer Science, 307(1):139-172, 2003.

Abstract

We prove that an independent system of equations in three variables with a nonperiodic solution and at least two equations consists of balanced equations only. For that, we show that the intersection of two different entire systems contains only balanced equations, where an entire system is the set of all equations solved by a given morphism. Furthermore, we establish that two equations which have a common nonperiodic solution have the same set of periodic solutions or are not independent.

Keywords: combinatorics on words, systems of equations, independence

Full paper: [ps - 336 KB] [ps.gz - 111 KB] [pdf - 241 KB].
(Some misprints have been corrected in this version of the paper thanks to the careful reading of Mike Müller. - Oktober 2010)