Observatorio de I+D+i UPM

Memorias de investigación
Book chapters:
Two Variants of Synchronized Shuffle on Backbones
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
Book Edition
Book Publishing
Publishing House of the Romanian Academy
ISBN
978-973-27-2470-5
Series
Book title
Discrete Mathematics and Computer Science
From page
77
To page
88
Participants
  • 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)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Sistemas Informáticos
S2i 2020 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)