Observatorio de I+D+i UPM

Memorias de investigación
Capítulo de libro:
Two Variants of Synchronized Shuffle on Backbones
Año:2014
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
This note proposes a new variant of the synchronized shuffle on backbones. In this variant besides the condition that the letters of the two words being synchronized must adhere to is predefined, forming a word which is called ?backbone?, they have to synchronize with the first occurrence of each letter in the order in which they appear in the backbone. We present some language-theoretic properties of the ordered synchronized shuffle on backbones applied to regular and context-free languages and two algorithms for deciding whether a given word can be obtained by ordered or arbitrary synchronized shuffle on a given backbone from other two given words. Our algorithm runs in O(n2 log n) and O(n3) for the ordered synchronized shuffle and arbitrary synchronized shuffle, respectively. We finally propose a few open problems.
Internacional
Si
DOI
Edición del Libro
Editorial del Libro
Publishing House of the Romanian Academy
ISBN
978-973-27-2470-5
Serie
Título del Libro
Discrete Mathematics and Computer Science
Desde página
77
Hasta página
88
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Henning Bordihn (Universidad de Potsdam, Alemania)
  • Autor: Florin Manea (Universidad de Kiel, Alemania)
  • Autor: Victor Mitrana (UPM)
  • Autor: Daniel Claudian Voinescu (Unversidad de Bucarest, Rumania)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Sistemas Informáticos
S2i 2021 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)