zbMATH — the first resource for mathematics

On total regulators generated by derivation relations. (English) Zbl 0571.68056
Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 71-79 (1985).
[For the entire collection see Zbl 0563.00018.]
A derivation relation is a total regulator on \(\Sigma^*\) if for every language \(L\subseteq \Sigma^*\), the set of all words derivable from L is a regular language. We show that for a wide class of derivation relations \(\Rightarrow^{*}_{P}\), \(\Rightarrow^{*}_{P}\) is a total regulator on \(\Sigma^*\) if and only if it is a well-quasiorder (wqo) on \(\Sigma^*\). Using wqo theory, we give a characterization of all non- erasing pure context-free (OS) derivation relations which are total regulators.

68Q45 Formal languages and automata