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 等数据库收录! |
|