Accepting splicing systems with permitting and forbidding words

Arroyo Montoro, Fernando and Castellanos Peñuela, Juan Bautista and Mitrana, Victor and Sánchez Couso, Jose Ramón and 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.

Description

Title: Accepting splicing systems with permitting and forbidding words
Author/s:
  • Arroyo Montoro, Fernando
  • Castellanos Peñuela, Juan Bautista
  • Mitrana, Victor
  • Sánchez Couso, Jose Ramón
  • Dassow, Jürgen
Item Type: Article
Título de Revista/Publicación: Acta Informatica
Date: February 2013
ISSN: 0001-5903
Volume: 50
Subjects:
Faculty: E.U. de Informática (UPM)
Department: Lenguajes, Proyectos y Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (763kB) | Preview

Abstract

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.

More information

Item ID: 15638
DC Identifier: http://oa.upm.es/15638/
OAI Identifier: oai:oa.upm.es:15638
DOI: 10.1007/s00236-012-0169-8
Official URL: http://link.springer.com/article/10.1007%2Fs00236-012-0169-8
Deposited by: Memoria Investigacion
Deposited on: 06 Jun 2013 16:55
Last Modified: 21 Apr 2016 15:53
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM