On the form equivalence of L-forms |
| |
Authors: | H Maurer Th Ottmann A Salomaa |
| |
Affiliation: | Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Karlsruhe, W-Germany;Department of Mathematics, University of Turku, Turku, Finland |
| |
Abstract: | In 5] the notion of an L form F defining a family d(F) of languages by means of X-interpretations has been introduced. Here X is one of a number of possible variations of the notion of interpretation originally used in 1] for grammar forms. In this paper it is shown that the questions whether for L forms F and F1 is decidable, if deterministic interpretations of PDOL systems are considered, where L(F) and L(F1) contain at most one word of length n for any n ? 0, and it is shown that same question is undecidable, if full or uniform interpretations are chosen. In contrast to this, no such results are known for grammar forms at this point. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|