|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050205,
author = {W\"{a}tjen, Dietmar},
title = {Undecidability Results for Uniformly $k$-Limited 0L Systems},
journal = jalc,
year = 2000,
volume = 5,
number = 2,
pages = {159--167},
keywords = {formal languages, $k$-limited 0L systems,
uniformly $k$-limited 0L systems, decision questions},
abstract = {In this paper we shall prove that it is undecidable
whether the intersection of two uniformly $k$-limited
0L languages is empty, finite, regular, context-free, a
$k$-limited or a uniformly $k$-limited language, whether the
language generated by a context-free grammar is a uniformly
$k$-limited 0L language or whether a uniformly $k$-limited
T0L language can be generated by a context-free grammar.
Furthermore, it is undecidable whether the union of two
uniformly $k$-limited 0L languages is such a language again.}
}