On DOS languages and DOS mappings
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.
- scientific article; zbMATH DE number 3902061
- Some decision problems about controlled rewriting systems
- scientific article; zbMATH DE number 3917717
- A characterisation of deterministic context-free languages by means of right-congruences
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3802813 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- On basic properties of DOS systems and languages
- On sentential forms of context-free grammars
- On the emptiness of the intersection of two DOS languages problem
- Pure grammars
- Representation theorems using DOS languages
- Some decidability problems of sentential formst †
This page was built for publication: On DOS languages and DOS mappings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q791326)
