I believe I have a definition of deterministic root-to-leaf tree automata in the unranked binary case, and would like to check that I have this definition correct. I would also appreciate any sources that approach tree automata from an unranked binary tree perspective, particularly those that present the topic in terms of associating states to nodes instead of transition rules as Comon or https://en.wikipedia.org/wiki/Tree_automaton does.

In short, when determining the state of the children of a node, we can look at:

  • The state of that node
  • The symbol of that node
  • Whether that node has left or right children or both

A deterministic root-to-leaf tree automaton is a tuple $(\Sigma, Q, q_0, \delta_{LR}, \delta_{L}, \delta_{R}, F)$ where

  • $\Sigma$ is a finite alphabet
  • $Q$ is a finite set of states
  • $q_0 \in Q$ is the start state
  • $\delta_{LR}$ is a function from $Q \times \Sigma$ to $Q \times Q$
  • $\delta_{L}$ and $\delta_{R}$ are functions from $Q \times \Sigma$ to $Q$
  • $F$ is a predicate that takes in both an element of $Q$ and an element of $\Sigma$

To run a rooted binary tree with labels from $\Sigma$ through the automaton:

  • First, associate the state $q_0$ to the root.
  • Next, working from the root to the leaves, if a node has state $q$ and symbol $c$:
    • If it has both left and right children, look up their states in $\delta_{LR}(q,c)$
    • If it has just a left child, its state is $\delta_{L}(q,c)$
    • If it has just a right child, its state is $\delta_{R}(q,c)$
  • If all leaves have state-symbol pairs that satisfy $F$, the automaton accepts the tree, otherwise rejects.

This question is 6.1.1(i) in Downey and Fellows' "Parameterized Complexity", which has a nonconventional presentation of tree automata in terms of trees of bounded fanin, but for which there is no relation between node arity and symbol (hence, "unranked" [I believe this is the correct term, but I've seen it more commonly in the case of unbounded fanin]).



Your Answer

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

Browse other questions tagged or ask your own question.