On DOS languages and DOS mappings (Q791326): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:05, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On DOS languages and DOS mappings |
scientific article |
Statements
On DOS languages and DOS mappings (English)
0 references
1984
0 references
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.
0 references
DOS system
0 references
DOS languages
0 references
subfamilies of context-free languages
0 references
DOS mappings
0 references
algebraic characterization
0 references
APDOS
0 references
equivalence problem
0 references