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


Some remarks on non-algebraic adherences
Authors:Sorin Istrail
Affiliation:Department of Mathematics and Computer Center, University “Al.I.Cuza” Ia?i, 6600 Ia?i, Romania
Abstract:We present some properties of non-algebraic adherences of languages, which can be consistently called context-sensitive adherences, because it is proved that in the Chomsky hierarchy of adherences, context-sensitive and recursive-enumerable adherences coincide. Concerning the center-mapping the traversing from algebraic to non-algebraic takes simple recursive to not necessarily recursive-enumerable. Except for the last equality, the Chomsky hierarchy of adherences is proper: RAdh ? CFAdh ? CSAdh = REAdh and moreover, it can be refined in the non-algebraic case by considering the McNaughton-Nivat adherences.Regarding the programming context, adherences occur when we consider the set of divergent computations ‘shapes’ of a program or a program scheme. In this respect, the ‘interpretation’ is powerful enough to translate RAdh to CSAdh.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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