← All problems
Unverified

Tree automata with constraints on infinite trees

Fix a finite alphabet AA. Denote by TT the set of AA-labellings of the complete infinite binary tree, i.e. maps {0,1}∗→A\{0,1\}^*\rightarrow A. Let R⊆T×TR \subseteq T \times T be an (equivalence) relation of such trees. A (binary) tree automaton with RR-constraints consists of a finite state set QQ, an initial state q0∈Qq_0 \in Q, and a transition relation Δ⊆(Q×A×{R,¬R})×(Q×Q)\Delta\subseteq (Q \times A\times \{R,\neg R\}) \times (Q \times Q). A run of a tree automaton on a tree labelling λ:{0,1}∗→A\lambda:\{0,1\}^*\rightarrow A is a choice of states q:{0,1}∗→Qq:\{0,1\}^*\rightarrow Q and transitions t:{0,1}∗→Δt:\{0,1\}^*\rightarrow \Delta for each vertex such that q(ϵ)=q0q(\epsilon)=q_0 and t(w)=(q(w),λ(w),X,q(w0),q(w1))t(w)=(q(w),\lambda(w),X,q(w0),q(w1)), where X=RX=R if the left and right subtree of ww are in RR-relation and X=¬RX=\neg R otherwise. A tree automaton accepts a labelling if there is a run for it. This can be extended to different more intricate acceptance conditions (Büchi condition along paths, parity conditions, \ldots{}). The set of labellings accepted by an automaton is called its language. The following questions might depend to some extent on the nature of the relation RR and should be understood as "for your favourite/interesting RR". Question: Is emptiness/universality decidable for these automata? Question: What are the closure properties for these language classes?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu