Séminaire Lotharingien de Combinatoire, B19f (1988).
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 361/S-19, p. 113-115.]

Aldo de Luca

On the Existence of a Finite Base for Systems of Equations of Infinite Words

Abstract. We prove that any set of equations on infinite words in a finite number of indeterminates has, over a countably generated free monoid, a finite equivalent subsystem. From this it follows that any language L of finite and infinite words on a finite alphabet A has a test set for morphisms from A\infty to B\infty. In the case of finite words, the result was proved by M. H. Albert and J. Lawrence.


The paper has been finally published under the title "Test sets for languages of infinite words" in Inform. Process. Lett. 29 (1988), 91-95.