# Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $$uv^\omega$$ (here $$u,v$$ are finite words). In other words, if $$\{w\}$$ is an $$\omega$$-regular language, then it is of that form. This is folklore; to prove this just take a cycle in the Buchi automata containing a final state (which gives one $$v$$) and a path from the initial state to that cycle (which gives one $$u$$).

This extends to infinite trees as well. A tree automata accepting infinite trees is non-empty iff it accepts a regular tree i.e. an infinite tree with finitely many subtrees. (Safra)

Push-down automata on infinite words are exactly the $$\omega$$-Kleene closure of context-free languages over finite words [2,3]. Hence, any push-down automata on infinite words contains a word of the form $$uv^{\omega}$$.

But, push-down tree automata for infinite trees do not enjoy this characterization. In fact, there exists pushdown tree automata which do not accept any regular trees [1].

However, we can still ask if given an tree $$T$$ if there is a push-down tree automata on infinite trees that accepts exactly $$\{T\}$$. We just know that $$T$$ being regular would guarantee anything. I was wondering if we could formulate a necessary and sufficient condition.

1. Saoudi, A., Pushdown automata on infinite trees and nondeterministic context-free programs, Int. J. Found. Comput. Sci. 3, No. 1, 21-39 (199

2. Cohen, Rina S.; Gold, Arie Y., Theory of (\omega)-languages. I: Characterizations of (\omega)-context- free languages, J. Comput. Syst. Sci. 15, 169-184 (1977). ZBL0363.68113.

3. Linna, M., On (\omega)-sets associated with context-free languages, Inform. and Control 31, 272-293 (1976). ZBL0329.68066.2). ZBL0769.68099.

• How would you represent the given tree? I think an algorithmic answer to your question would depend on the model (e.g, if it's given by a Turing machine, or even by a push-down automaton, it would probably be undecidable). I don't believe you will find a clean algebraic condition, just like we don't have a good algebraic characterization of context-free languages. Mar 28 at 19:50
• @Shaull I do not pose this as an algorithmic question. I get your intuition behind why even an algebraic solution might be impossible, however, my meta level idea is: gIven an infinite tree, if there exists a context-free language containing exactly that tree then that tree is finitely presentable, the push-down automata itself being the finite presentation. So I was hoping one could figure out by looking at the tree that it was finitely presentable. I was thinking something along the lines of caucal graphs could be connected but that's a wild stone throw in the dark. Mar 29 at 1:45