Accepting splicing systems with permitting and forbidding words

Arroyo Montoro, Fernando; Castellanos Peñuela, Juan Bautista; Mitrana, Victor; Sánchez Couso, Jose Ramón y Dassow, Jürgen (2013). Accepting splicing systems with permitting and forbidding words. "Acta Informatica", v. 50 (n. 1); pp. 1-14. ISSN 0001-5903. https://doi.org/10.1007/s00236-012-0169-8.

Descripción

Título: Accepting splicing systems with permitting and forbidding words
Autor/es:
  • Arroyo Montoro, Fernando
  • Castellanos Peñuela, Juan Bautista
  • Mitrana, Victor
  • Sánchez Couso, Jose Ramón
  • Dassow, Jürgen
Tipo de Documento: Artículo
Título de Revista/Publicación: Acta Informatica
Fecha: Febrero 2013
Volumen: 50
Materias:
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Lenguajes, Proyectos y Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (763kB) | Vista Previa

Resumen

Abstract: In this paper we propose a generalization of the accepting splicingsystems introduced in Mitrana et al. (Theor Comput Sci 411:2414?2422,2010). More precisely, the input word is accepted as soon as a permittingword is obtained provided that no forbidding word has been obtained sofar, otherwise it is rejected. Note that in the new variant of acceptingsplicing system the input word is rejected if either no permitting word isever generated (like in Mitrana et al. in Theor Comput Sci 411:2414?2422,2010) or a forbidding word has been generated and no permitting wordhad been generated before. We investigate the computational power ofthe new variants of accepting splicing systems and the interrelationshipsamong them. We show that the new condition strictly increases thecomputational power of accepting splicing systems. Although there areregular languages that cannot be accepted by any of the splicing systemsconsidered here, the new variants can accept non-regular and even non-context-free languages, a situation that is not very common in the case of(extended) finite splicing systems without additional restrictions. We alsoshow that the smallest class of languages out of the four classes definedby accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediatelyderived from the proof of this result.

Más información

ID de Registro: 15638
Identificador DC: http://oa.upm.es/15638/
Identificador OAI: oai:oa.upm.es:15638
Identificador DOI: 10.1007/s00236-012-0169-8
URL Oficial: http://link.springer.com/article/10.1007%2Fs00236-012-0169-8
Depositado por: Memoria Investigacion
Depositado el: 06 Jun 2013 16:55
Ultima Modificación: 21 Abr 2016 15:53
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM