×

zbMATH — the first resource for mathematics

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.

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