Narrow Results

In this paper we consider the extension of Nerode theorem to infinite trees. Unfortunately, we prove that this extension is not possible. We give some characterizations of recognizable and rational ω-tree sets in terms of ω-tree automata. We consider some complexity measures of recognizable and rational ω-tree sets and prove that these measures define infinite hierarchies.

We introduce various types of top-down pushdown infinite tree automata. We extend the Landweber-Staiger-Wagner hierarchy to pushdown infinite tree automata. We prove that the extension of Kleene’s theorem to pushdown infinite tree automata is not possible. We characterize recognizable (i.e. regular) infinite trees and extend Eilenberg’s theorem to ω-tree pushdown automata. We give some characterizations of infinite computations of nondeterministic context-free program schemes. We show that the equivalence problem for nondeterministic context-free program schemes is unsolvable.