dc.creator | Paun, Gheorghe | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Yokomori, Takashi | es |
dc.date.accessioned | 2017-12-26T11:55:04Z | |
dc.date.available | 2017-12-26T11:55:04Z | |
dc.date.issued | 2008 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 0129-0541 | es |
dc.identifier.uri | http://hdl.handle.net/11441/68007 | |
dc.description.abstract | 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 insertion systems of weight (3, 0) and star languages. | es |
dc.description.sponsorship | Ministerio de Educación y Ciencia TIN2006-13425 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | World Scientific | es |
dc.relation.ispartof | International Journal of Foundations of Computer Science, 19 (4), 859-871. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Insertion-deletion systems | es |
dc.subject | Recursively enumerable languages | es |
dc.subject | Context-free languages | es |
dc.subject | Regular languages | es |
dc.title | Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems | es |
dc.type | info:eu-repo/semantics/article | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | TIN2006-13425 | es |
dc.relation.publisherversion | http://www.worldscientific.com/doi/abs/10.1142/S0129054108006005 | es |
dc.identifier.doi | 10.1142/S0129054108006005 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 12 | es |
dc.journaltitle | International Journal of Foundations of Computer Science | es |
dc.publication.volumen | 19 | es |
dc.publication.issue | 4 | es |
dc.publication.initialPage | 859 | es |
dc.publication.endPage | 871 | es |
dc.identifier.sisius | 6679290 | es |
dc.contributor.funder | Ministerio de Educación y Ciencia (MEC). España | |