Iterierte Substitutionen bei regulären Baumsprachen

Abstract

Wir zeigen, dass das Beschränktheitsproblem für eine Verallgemeinerung der automata with coloring nach Bala bzw. desert automata nach Kirsten mit mehreren priorisierten Zählern und auf Bäumen in PSPACE ist. Dieses Ergebnis nutzen wir, um zu zeigen, dass in doppelt exponentieller Zeit auf einer nichtdeterministischen Turingmaschine entschieden werden kann, ob eine endliche lineare Substitution σ mit σ(L)=R für gegebene reguläre Baumsprachen L und R existiert.