On the expressibility of languages by word equations with a bounded number of variables
Juhani Karhumäki, Filippo Mignosi, Wojciech Plandowski · Bulletin of the Belgian Mathematical Society - Simon Stevin · 2001
A language (resp.a relation) is expressible by a word equation e if it is defined as the set of all values of an unknown (resp.a set of unknowns) over all solutions of the equation e.We first present some tools for proving that languages or relations are not expressibles unless a certain number of auxiliary variables enter into the equation.As a consequence an infinite hierarchybased on the number of auxiliary unknowns -of expressible language is established.Also the necessary number of auxiliary unknowns to encode a boolean combination of word equations into a single equation or inequality is considered.Finally, we present two new tools for establishing the nonexpressibility in general, and, as a consequence, we obtain a gap theorem for expressible languages. RésuméUn langage (resp.une relation) est définissable par une équation sur les mots e s'il est l'ensemble de toutes les valeurs prise par une variable (resp.un n-uplet de variables) quand on parcourt les solutions de e.On donne des méthodes pour prouver la non-définissabilité de langages ou relations par des equations qui utilisent un nombre fixé de variables auxiliaires.On obtient, comme conséquence, une hierarchie infinie de languages définissable, hierarchie basée sur le nombre de variables auxliaires.On étudie le nombre de variables auxiliaires qui sont necessaires pour coder une combinaison booléenne d'équations sur les mots en une unique equation.On introduit deux nouveaux outils pour prouver la non-définissabilité en géneral.Ces derniers permettent d'établir un "gap theorem" pour les languages définissables.