|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010204,
author = {Joanna J\c{e}drzejowicz},
title = {Undecidability Results for Shuffle Languages},
journal = jalc,
year = 1996,
volume = 1,
number = 2,
pages = {147--159},
keywords = {shuffle, shuffle closure, undecidable problems},
abstract = {We consider shuffle languages which are an extension of
regular languages with two operators, that is shuffle
(sometimes called interleaving) and shuffle closure.
The class of shuffle languages is a proper subset of
context-sensitive languages, incomparable with context-free
ones. For this class we give two undecidability results.
First of all we show that the intersection emptiness problem
for shuffle languages is undecidable and then we prove that
there is no algorithm to determine the shuffle closure
height of shuffle expressions.}
}