On DOS languages and DOS mappings (Q791326): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1969091720 / rank | |||
Normal rank |
Latest revision as of 11:12, 30 July 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