On DOS languages and DOS mappings (Q791326)

A deterministic 0-context sequential rewriting system (a DOS system) is a triple \(G=(V,h,w)\) where V is a finite alphabet, \(h:V \to V^*\) and \(w\in V^*\). Such a system identifies a language (the set of all strings derivable from \(w\) by successive -- sequential -- applications of \(h)\) and a mapping (by leaving the axiom \(w\) unspecified). The paper investigates the relationships among the family of DOS languages, certain variants of them and certain subfamilies of context-free languages; then one investigates the DOS mappings. A complete algebraic characterization is obtained for propagating acyclic DOS schemes (APDOS, for short). As a consequence, the equivalence problem is shown to be decidable for APDOS mappings.