Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
tree_automata [2010/05/27 18:10] vkuncak |
tree_automata [2012/05/15 15:48] vkuncak |
||
---|---|---|---|
Line 37: | Line 37: | ||
Example: | Example: | ||
- | * bottom up tree automaton checking the parity of the number of nodes in the tree | + | * bottom up tree automaton accepting trees with an even number of nodes in the tree, in alphabet with constant 'a', binary function 'f'. |
+ | * bottom up tree automaton accepting expressions with complement, union, intersection; accepting only expressions that are monotonic in each variable | ||
Non-deterministic top-down tree automaton: reverse a bottom-up tree automaton | Non-deterministic top-down tree automaton: reverse a bottom-up tree automaton | ||
Deterministic top-down tree automaton: more restrictive. Is there deterministic automaton to check the parity of the number of nodes? | Deterministic top-down tree automaton: more restrictive. Is there deterministic automaton to check the parity of the number of nodes? | ||
- | |||
- | |||
- | |||
===== Closure Properties of Tree Automata ====== | ===== Closure Properties of Tree Automata ====== |