# 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.

##### MSC:
 68Q45 Formal languages and automata
##### Keywords:
regular language; well-quasiorder