|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050104,
author = {Sos\'{\i}k, Petr},
title = {On the Decidability Problems of Eco-Grammar Systems},
journal = jalc,
year = 2000,
volume = 5,
number = 1,
pages = {45--58},
keywords = {formal languages, eco-grammar systems, tiling problem,
finiteness problem, emptiness problem},
abstract = {(Un)decidability of the finiteness and emptiness problem
of some (extended) conditional tabled eco-grammar (CTEG)
system language families is shown. The tiling problem is
used as a tool for the undecidability proof in the case of
non-extended eco-grammar systems. It is shown that forbidding
CTEG systems with a forbidding context of length $2$ can
generate all possible tilings of the plane by Wang tiles
(dominoes). The known (un)decidability results of these
language families are summarized in two tables.}
}