Show simple item record

dc.creatorPaun, Gheorghees
dc.creatorPérez Jiménez, Mario de Jesúses
dc.creatorYokomori, Takashies
dc.date.accessioned2017-12-26T11:55:04Z
dc.date.available2017-12-26T11:55:04Z
dc.date.issued2008
dc.identifier.citationPaun, 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.issn0129-0541es
dc.identifier.urihttp://hdl.handle.net/11441/68007
dc.description.abstractInsertion-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.sponsorshipMinisterio de Educación y Ciencia TIN2006-13425es
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherWorld Scientifices
dc.relation.ispartofInternational Journal of Foundations of Computer Science, 19 (4), 859-871.
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectInsertion-deletion systemses
dc.subjectRecursively enumerable languageses
dc.subjectContext-free languageses
dc.subjectRegular languageses
dc.titleRepresentations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systemses
dc.typeinfo:eu-repo/semantics/articlees
dc.type.versioninfo:eu-repo/semantics/submittedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificiales
dc.relation.projectIDTIN2006-13425es
dc.relation.publisherversionhttp://www.worldscientific.com/doi/abs/10.1142/S0129054108006005es
dc.identifier.doi10.1142/S0129054108006005es
dc.contributor.groupUniversidad de Sevilla. TIC193: Computación Naturales
idus.format.extent12es
dc.journaltitleInternational Journal of Foundations of Computer Sciencees
dc.publication.volumen19es
dc.publication.issue4es
dc.publication.initialPage859es
dc.publication.endPage871es
dc.identifier.sisius6679290es
dc.contributor.funderMinisterio de Educación y Ciencia (MEC). España

FilesSizeFormatViewDescription
be6d6e6ebdb6290c7782c491f743d4 ...244.0KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional