|
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 |