Discrete Math Seminar: Juhani Karhumaki

Abstract:

One of the fundamental properties of word equations isthe following compactness result: each system of word equation with a fixed finite number of unknowns is equivalent to some of its finite subsystems. Or equivalently there does not exist an infinite independent set of word
equations. However, no bound for the size of the maximal subsystem, even in the case of three unknowns, is known. The first goal of this talk is to give a survey of these results. The second goal deals with the chains of solution sets of word equations. A simplest illustration is as follows. The basic results on words states that any two words satisfying
a nontrivial relation are powers of a common word. It follows easily that one can introduce at most three constrains on two words such that in each step the set of all words satisfying these constrains properly decreases. That is in this case the length of solution chains is at most
three. The above compactness result (and its proof) guarantees that these solution chains are always finite. Again it is open how large they can be, even in the caseof three unknowns. We analyze and report some new results on these chains.