Do rational equivalence relations have regular cross-sections? (English) Zbl 0571.68069

Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 300-309 (1985).
[For the entire collection see Zbl 0563.00018.]
The following classes of rational equivalence relations are shown to have regular cross-sections: deterministic rational equivalence relations, rational equivalence relations over a one letter alphabet, and rational equivalence relations with bounded separability. Although the general case remains open, it is shown to be reducible to that of locally-finite rational equivalence relations over a two letter alphabet. Two particular cross-sections are shown not to be regular: the set of minimum length words and the set of lexicographically minimal words.


68Q45 Formal languages and automata
03E20 Other classical set theory (including functions, relations, and set algebra)
68T50 Natural language processing


Zbl 0563.00018