<p>A Buchi automaton is non-empty iff it accepts an infinite word of the form <span class="math-container">$uv^\omega$</span> (here <span class="math-container">$u,v$</span> are finite words). In other words, if <span class="math-container">$\{w\}$</span> is an <span class="math-container">$\omega$</span>-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 <span class="math-container">$v$</span>) and a path from the initial state to that cycle (which gives one <span class="math-container">$u$</span>).</p>
<p>This extends to infinite trees as well. A tree automata accepting infinite trees is non-empty iff it accepts a regular tree <em>i.e.</em> an infinite tree with finitely many subtrees. (Safra)</p>
<p>Push-down automata on infinite words are exactly the <span class="math-container">$\omega$</span>-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 <span class="math-container">$uv^{\omega}$</span>.</p>
<p>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].</p>
<p>However, we can still ask if given an tree <span class="math-container">$T$</span> if there is a push-down tree automata on infinite trees that accepts exactly <span class="math-container">$\{T\}$</span>. We just know that <span class="math-container">$T$</span> being regular would guarantee anything. I was wondering if we could formulate a necessary and sufficient condition.</p>
<ol>
<li><p><em>Saoudi, A.</em>, <a href="http://dx.doi.org/10.1142/S0129054192000048" rel="nofollow noreferrer"><strong>Pushdown automata on infinite trees and nondeterministic context-free programs</strong></a>, Int. J. Found. Comput. Sci. 3, No. 1, 21-39 (199</p>
</li>
<li><p><em>Cohen, Rina S.; Gold, Arie Y.</em>, <a href="http://dx.doi.org/10.1016/S0022-0000(77)80004-4" rel="nofollow noreferrer"><strong>Theory of (\omega)-languages. I: Characterizations of (\omega)-context- free languages</strong></a>, J. Comput. Syst. Sci. 15, 169-184 (1977). <a href="https://zbmath.org/?q=an:0363.68113" rel="nofollow noreferrer">ZBL0363.68113</a>.</p>
</li>
<li><p><em>Linna, M.</em>, <a href="http://dx.doi.org/10.1016/S0019-9958(76)90415-0" rel="nofollow noreferrer"><strong>On (\omega)-sets associated with context-free languages</strong></a>, Inform. and Control 31, 272-293 (1976). <a href="https://zbmath.org/?q=an:0329.68066" rel="nofollow noreferrer">ZBL0329.68066</a>.2). <a href="https://zbmath.org/?q=an:0769.68099" rel="nofollow noreferrer">ZBL0769.68099</a>.</p>
</li>
</ol>

CC BY-SA 4.0
2021-03-28T19:50:24.683Z
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.
Shaull
CC BY-SA 4.0
2021-03-29T01:45:22.687Z
@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.
Faustus
<fl.formal-languages><automata-theory><regular-language><context-free><omega-language>
Necessary and sufficient condition for an infinite tree to be context-free
Faustus
# Necessary and sufficient condition for an infinite tree to be context-free

(Asked by: username_0 on 2021-03-28)

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**](http://dx.doi.org/10.1142/S0129054192000048), 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**](http://dx.doi.org/10.1016/S0022-0000(77)80004-4), J. Comput. Syst. Sci. 15, 169-184 (1977). [ZBL0363.68113](https://zbmath.org/?q=an:0363.68113).
3. *Linna, M.*, [**On (\omega)-sets associated with context-free languages**](http://dx.doi.org/10.1016/S0019-9958(76)90415-0), Inform. and Control 31, 272-293 (1976). [ZBL0329.68066](https://zbmath.org/?q=an:0329.68066).2). [ZBL0769.68099](https://zbmath.org/?q=an:0769.68099).

**Tags:** fl.formal-languages, automata-theory, regular-language, context-free, omega-language
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 0 answers

