Relations over Words and Logic: A Chronology.
Christian Choffrut · 2006
The purpose of this short note is to give credit to the right people who produced original work on the connection between rational relations and logic. Indeed, my experience is that some authors seem to partially ignore the literature or at least neglect to cite it correctly. It is probably due to the fact that language theory and logic, though having largely filled the original gap which separated them, still have different backgrounds. I hope that recalling the chronology might be of some help. If I had some doubt about the necessity of this reminder, a recent experience proved it was justified. Indeed, I posted an early version of the present work on my web page. Kamal Lodaya from the University of Chennai happened to come across it, got interested and posed a few questions. Doing some bibliographical search he found that the relations which after Läuchli and Savioz I had called “special”, had in fact been introduced three years earlier by D. Angluin and D. N. Hoover as “regular prefix relations”. Now we come to the point. Given n finite, nonempty alphabets Σi, i = 1,..., n, I’m interested in the class of subsets, also called relations, of the direct product Σ ∗ 1 × · · · × Σ∗n which are rational (known as regular in the anglo-saxon literature). A simple example: the relation which is the graph of the operation of concatenation of two words and which consists of all triples of the form (u, v, uv) where u, v ∈ Σ ∗ , is defined by the rational expression ∆ ∗ 1 ∆∗ 2 where ∆1 = � a∈Σ(a, 1, a) and ∆2 = � a∈Σ(1, a, a). These relations are also defined via an extension of the finite automata operating on tuples of words rather than on words, introduced by Rabin and Scott in the late fifties, [8]. They were studied by Elgot and Mezei who proved most of their general properties, [6]. The main decision issues were settled by Fischer and Rosenberg, [7]. It just happens that this class does not form a Boolean algebra unless n = 1 or all alphabets Σi’s are reduced to a single symbol. Until the mid eighties, only two subclasses of the rational relations were known to be closed under the Boolean operations, to wit the recognizable and the synchronous relations which are therefore natural candidates for logical definability. A new