Automata on Oddly-Shaped Words 2: Root-to-Leaf Automata

In this video, I provide a possible definition of Deterministic Binary Root-to-Leaf Tree Automata, and show why they're not as expressive as Leaf-to-Root Tree Automata. I also discuss Nondeterministic versions of both types of automata -- they are expressively equivalent to each other and to Deterministic Leaf-to-Root Automata, giving us a really good candidate for a notion of "Regular Language" of Binary Trees
Prerequisites:
AoOSW 1: Deterministic Leaf-to-Root Tree Automata
RLMT 3: Nondeterministic automata
Sources:
I've adapted the result on "decorated paths" and the two-element language not accepted by some deterministic root-to-leaf tree automata from "On the Boolean Closure of Deterministic Top-Down Tree Automata" by Löding & Thomas (2024), arxiv.org/abs/... . Although neither result is new to this paper, the presentation is easier to read than most.
My definition of root-to-leaf automata is adapted from the above, and Comon et. al.'s "Tree Automata Techniques and Applications"
If you have questions or something didn't make sense to you, please help me improve this series by letting me know in the comments below!

[@shift_reset]

For functional programmers, root-to-leaf automata are the same as tree unfolds / anamorphisms, continuing the relationship with recursion schemes.

[@whosmaya666]

great video as always! it's interesting to me how the set {(0,0), (1,1)} that you used for the non-deterministic example resembles a kind of "quantum entanglement" between the left and right subtrees - we determine their relationship without assigning a specific value to either of them. I'm curious if you have something deeper to say about this analogy

[@trkern]

Good insight! The math behind nondeterminism and quantum physics are closely related. In both cases, you're keeping track of a set of states you could "be" "in" through various transitions. If you replace the complex numbers in quantum physics with elements {0,1} of the Boolean semiring (1+1=1), you get exactly the right linear algebraic tool for reasoning about nondeterminism: matrices where M_ij = 1 if there is a possible transition from state i to state j. Here 1 represents "there is at least one way to get into this state", so 1+1=1 represents us not caring if there are multiple ways of getting into a state.
With quantum physics, on the other hand, the complex numbers allow terms to cancel, so if there's one way of getting into state q that gives us a coefficient of a, and another way of getting into state q that gives us a coefficient of -a, they cancel (aq + -aq = 0), which is what happens with quantum interference.
It's also worth noting that if you replace the complex numbers by natural numbers, you get counts of the number of ways of going from one state to another. If you replace them by reals in [0,1], you can get Markov matrices.