On DOS languages and DOS mappings (Q791326): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Grzegorz Rozenberg / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gheorghe Păun / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the emptiness of the intersection of two DOS languages problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On basic properties of DOS systems and languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Representation theorems using DOS languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some decidability problems of sentential formst † / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pure grammars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4746787 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On sentential forms of context-free grammars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5678435 / rank | |||
Normal rank | |||
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