Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Accepting splicing systems with permitting and forbidding words
Year:2012
Research Areas
  • Engineering,
  • Information technology and adata processing
Information
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.
International
Si
JCR
Si
Title
Acta Informatica
ISBN
0001-5903
Impact factor JCR
0,809
Impact info
Datos JCR del año 2010
Volume
10.1007/s00236-012-0169-8
Journal number
From page
1
To page
14
Month
SIN MES
Ranking
SCImago Journa & Contry Rank Q2, SJR 0,85, Cites 0,93
Participants
  • Autor: Fernando Arroyo Montoro (UPM)
  • Autor: Juan Bautista Castellanos Peñuela (UPM)
  • Autor: Jürgen Dassow
  • Autor: Victor Mitrana (UPM)
  • Autor: Jose Ramon Sanchez Couso (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Computación Natural
  • Departamento: Lenguajes, Proyectos y Sistemas Informáticos
  • Departamento: Inteligencia Artificial
S2i 2019 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)