On the Decidability Problems of Eco-Grammar Systems
Petr Sosı́k · Journal of automata, languages and combinatorics · 2000
(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)decidabi1ity results of these language families are summarized in two tables.