On some families of languages related to the Dyck language
Maurice Nivat · 1970
@ by the n relations xixi = 1 i e {1,...,n}. The author convinced himself that many other congruences have the same property [Ni 1], and undertook the task of finding them systematically. Here is presented a part of the results of this undertaking. An important family of congruences is brought to light which have interesting decidability properties: in the constructions leading to these decidability properties we used as a guide line the nice paper of Mac Naughton [McN]. Sufficient conditions are given in order that the equivalence classes (and their complements) of such a congruence be an algebraic language. We do not study in this paper the properties of these languages, this will be done elsewhere [Ni 2].