diff options
| -rw-r--r-- | mgr.tex | 12 |
1 files changed, 11 insertions, 1 deletions
@@ -131,7 +131,15 @@ with the elements of $Q$ such that \end{itemize} A run is \definedterm{accepting} if $T$'s root gets relabeled to an accepting -state, that is a state $q \in F$. +state, that is a state $q \in F$. The set of all trees accepted by an automaton +$A$ is called the \definedterm{language recognized by $A$}, notated $L(A)$. We +call the class of all languages recognized by tree automata \definedterm{regular +tree languages}, analogously to regular languages recognized by finite state +automata. + +We note that the expressive power of deterministic bottom-up tree automata is +the same as that of nondeterministic (either bottom-up or top-down) tree +automata. \subsection{Monadic Second Order (MSO) Logic} % def of MSO @@ -167,6 +175,8 @@ f \chapter{Branch Infix Regular Queries}\label{r:branchinfix} +In this chapter we will present a solution to the following query problem: + \queryproblem[% regular language $L$ over alphabet $\Sigma$. ]{Branch Infix Regular Queries}{% |