Memorias de investigación
Artículos en revistas:
Accepting splicing systems with permitting and forbidding words
Año:2012
Áreas de investigación
  • Ingenierías,
  • Ciencias de la computación y tecnología informática
Datos
Descripción
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.
Internacional
Si
JCR del ISI
Si
Título de la revista
Acta Informatica
ISSN
0001-5903
Factor de impacto JCR
0,809
Información de impacto
Datos JCR del año 2010
Volumen
DOI
10.1007/s00236-012-0169-8
Número de revista
Desde la página
1
Hasta la página
14
Mes
SIN MES
Ranking
SCImago Journa & Contry Rank Q2, SJR 0,85, Cites 0,93
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Computación Natural
  • Departamento: Lenguajes, Proyectos y Sistemas Informáticos
  • Departamento: Inteligencia Artificial