首页 | 本学科首页   官方微博 | 高级检索  
     


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 Ld(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 Ld(F) = Ld(F1) 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号