Скачать или смотреть Automata on Oddly-Shaped Words 4: Tree Regular Expressions and the Pumping Lemma

In this video I cover the pumping lemma for trees. Just as in the word automata case, the pumping lemma motivates the Kleene star, which I use to define a notion of regular expression for trees. I also give the ideas of how to convert deterministic tree automata to tree regular expressions.

Prerequisites:
RLMT 1: Deterministic Word Automata
RLMT 4: Kleene Star, Regular Expression
AoOSW 1: Deterministic Tree Automata

Sources:
Comon et al.'s "Tree Automata Techniques and Applications" has the pumping lemma and definitions for tree regular expressions. Includes a different proof of the equivalence of tree regular expressions and tree automata.

The deterministic tree automaton to regular expression construction in the video is based on:
Doupal, Jakub. Finite tree automaton to tree regular expression conversion.
Master’s thesis. Czech Technical University in Prague, Faculty of Information
Technology, 2019


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!