On dos languages and dos mappings |
| |
| Authors: | Andrzej Ehrenfeucht David Haussler Grzegorz Rozenberg Paul Zeiger |
| |
| Affiliation: | (1) Department of Computer Science, University of Colorado, 80302 Boulder, Colorado;(2) Department of Mathematics and Computer Science, University of Denver Denver, 80208, Colorado;(3) Institute of Applied Math. and Computer Science, University of Leiden, Leiden, The Netherlands |
| |
| Abstract: | Roughly speaking,DOS systems formalize the notion of generatively deterministic context free grammars. We explore the containment relationships among the class of languages generated byDOS systems and other subclasses of the class of context free languages. Leaving the axiom of aDOS system unspecified yields aDOS scheme, which defines a mapping from words to languages over a given alphabet. We explore the algebraic properties ofDOS mappings and obtain an algebraic characterization of a fundamental subclass of theDOS mappings generated byDOS schemes which are propagating (non erasing) and have no cycles of derivability among letters of the alphabet. We apply this characterization to show that the mapping equivalence problem for propagatingDOS schemes is decidable. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
