Repositorio de producción científica de la Universidad de Sevilla

Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems

Opened Access Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Paun, Gheorghe
Pérez Jiménez, Mario de Jesús
Yokomori, Takashi
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2008
Publicado en: International Journal of Foundations of Computer Science, 19 (4), 859-871.
Tipo de documento: Artículo
Resumen: Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability were obtained in this framework. In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Schützenberger representation of context-free languages, i.e., in the form L = h(L( ) ∩D), where is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages – this time using inse...
[Ver más]
Cita: Paun, G., Pérez Jiménez, M.d.J. y Yokomori, T. (2008). Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems. International Journal of Foundations of Computer Science, 19 (4), 859-871.
Tamaño: 244.0Kb
Formato: PDF

URI: http://hdl.handle.net/11441/68007

DOI: 10.1142/S0129054108006005

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones