2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Mar 28, 2021 at 19:50
  • 1
    $\begingroup$ @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. $\endgroup$
    – Faustus
    Commented Mar 29, 2021 at 1:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.