The expressibility of languages and relations by word equations

Reviewer: Francois Aribaud

A language L is expressible by a word equation e (in which a variable X is singled out) if L coincides with the values of X in all the solutions of e . It is known that such a language is recursive. The aim of this paper is to show that the class of these languages is somewhat limited and is not comparable to the other classical families of languages (D0L, regular, and context-free languages). It is easy to show that the class of expressible languages is closed under concatenation, cyclic closure, Kleene star of a single word, and taking the reverses of words. Closures by finite intersections and finite unions are finer results: the authors give a procedure for the reduction of a Boolean formula of equations to a single equation with extra variables. But, as always in language theory, the more elaborate results are negative: the family of expressible languages is not closed under the operations of complementation, morphic image, inverse morphic image, and shuffle. What is most interesting about this work is the elaboration of tools that lead to counterexamples. Using a sophisticated scheme of factorization of a word, the authors prove variants of pumping lemmas: for a general word w in an expressible language, one may find a pattern p X , that is, a word written with the letters of the alphabet A and an extra variable X , such that w is p u for some sequence u of letters of A , and such that p v is in L for any sequence v of letters of A .