From ceb5db06b50bc3bd43b48d886338d578e6d91f9c Mon Sep 17 00:00:00 2001 From: Nathaniel Wesley Filardo Date: Tue, 2 Feb 2016 17:43:03 -0500 Subject: [PATCH] Minor improvements to tree zoo --- main.tex | 2 +- tree-sepex.tex | 43 +++++++++++++------ treeautintro.tex | 105 +++++++++++++++++++++++++++++++-------------- zoo-tree/awcbb.tex | 3 +- zoo-tree/awedc.tex | 4 +- zoo-tree/ra.tex | 57 +++++++++++++++--------- zoo-tree/rta.tex | 34 --------------- zoo-tree/taec.tex | 66 ++++++++++++++++++++++++++++ zoo-tree/taged.tex | 65 ++++++++++++++++++++++++++-- zoo-tree/tahom.tex | 63 +++++++++++++++++++++++++-- 10 files changed, 330 insertions(+), 112 deletions(-) delete mode 100644 zoo-tree/rta.tex create mode 100644 zoo-tree/taec.tex diff --git a/main.tex b/main.tex index 810afb2..816fceb 100644 --- a/main.tex +++ b/main.tex @@ -264,9 +264,9 @@ or \url{http://www.gnu.org/licenses/agpl-3.0.txt}) or any later version.}} \maininclude{(Dis)Equality-Constrained Tree Automata}{zoo-tree/awedc} \maininclude{Constraints Between Brothers}{zoo-tree/awcbb} \maininclude{Reduction Automata}{zoo-tree/ra} +\maininclude{Tree Automata with Equational Constraints}{zoo-tree/taec} \maininclude{Homomorphism-Equality Automata}{zoo-tree/tahom} \maininclude{Tree Automata with Global Equality and Disequality}{zoo-tree/taged} -\maininclude{Rigid Tree Automata}{zoo-tree/rta} \maininclude{Simple Separating Examples}{tree-sepex} %\part{Infinite Trees} diff --git a/tree-sepex.tex b/tree-sepex.tex index ec74cac..44f12f9 100644 --- a/tree-sepex.tex +++ b/tree-sepex.tex @@ -5,12 +5,14 @@ such examples here. \subsection{Equalities Vs. Recursion} \subsubsection{All-equal lists} +\label{sec:tree-sepex:allequallist} Not all classes of automata permit free interaction of recursion and equality constraints; as such, these classes may not be able to describe the language of all-equal lists: $\set{ [], [A], [A,A], [A,A,A], \ldots }$ for any $A$. Note, however, that for a fixed, regular tree $A$, the set of -all-equal lists of $A$ is a regular tree language. The difficulty emerges +all-equal lists of $A$ is a regular tree language, and therefore the set of +all-equal lists from a finite vocabulary is expressible . The difficulty emerges when we wish to describe all-equal lists over an unbounded number of possible elements. @@ -18,32 +20,47 @@ possible elements. A generalization of the above, consider the language of lists composed of regions of size at least two whose elements are equal, for example: -$[A,A,B,B,B]$ or $[A,A,A,B,B,C,C,D,D,D,D]$. Rigid tree automata will not be -able to describe such a class due to the need for unboundedly many -equivalence classes. +$[A,A,B,B,B]$ or $[A,A,A,B,B,C,C,D,D,D,D]$. TAGED and its subclasses +(\autoref{sec:zoo-tree/taged}) will not be able to describe such a language +due to the need for unboundedly many equivalence classes. -\subsection{Opacity} +\subsubsection{Equal-Leaved Full N-Ary Trees} + +Suppose we have an {\em infinite} tree language $\mathcal{L}$. There is a +language $\mathcal{L}'$ which consists of (\texttt{f}-labeled) full binary +trees whose leaves are from $\mathcal{L}$; it is the smallest fixed point of +the equation $\mathcal{L}' = \mathcal{L} \cup \set{ \mathtt{f}(l,\ldots,l) +\middle\vert l \in \mathcal{L}'}$. This language is {\em not} regular; it +is recognizable by many, but not all, classes of automata with local +equality constraints. Such examples are bread-and-butter for the families +with global constraints. + +It is important for this example that $\mathcal{L}$ be infinite: if it were +finite, then we could encode the leaf subtree into the state label of an +ordinary TA and equality constraints would not enter into consideration. + +\subsection{Opacity vs. Intersection} Consider the sets of trees described by % \begin{center}\begin{tabular}{cc} - $\set{ f(g(X,Y),g(Z,X)) \middle\vert X,Y,Z \in \mathcal{T}(\Sigma)}$ - & $\set{ f(W,g(A,B)) \middle\vert A,B,W \in \mathcal{T}(\Sigma) \wedge A\vert_1 = B\vert_2 }$ + $\set{ f(g(X,Y),g(Z,X)) \middle\vert X,Y,Z \in \mathcal{T}(\alphabet)}$ + & $\set{ f(W,g(A,B)) \middle\vert A,B,W \in \mathcal{T}(\alphabet) \wedge A\vert_1 = B\vert_2 }$ \\ \begin{tikzpicture} \Tree [.f [.g X Y ] [.g Z X ] ] \end{tikzpicture} & \begin{tikzpicture} - \Tree [.f W [.g$_{11=21}$ A B ] ] + \Tree [.f W [.g$_{11=22}$ A B ] ] \end{tikzpicture} \end{tabular}\end{center} % These descriptions are clearly (given their comprehension form) amenable to classification by Opaque constraints. Their intersection is $\set{ -f(g(A,B),g(C,A)) \middle\vert A,B,C \in \mathcal{T}(\Sigma) \wedge C\vert_1 +f(g(A,B),g(C,A)) \middle\vert A,B,C \in \mathcal{T}(\alphabet) \wedge C\vert_1 = A\vert_2 }$, which can be made amenable to Opaque classification only if -we are able to unfold $\mathcal{T}(\Sigma)$ for $A$ and $C$. While we can -do this for regular trees over finite $\Sigma$, in general what we are +we are able to unfold $\mathcal{T}(\alphabet)$ for $A$ and $C$. While we can +do this for regular trees over finite $\alphabet$, in general what we are calling here $A$ will actually be trees accepted by a particular state, so we can only describe this intersection with Opaque constraints if we are able to unfold the description of that state. In general, that unfolding @@ -71,7 +88,7 @@ this structure is amenable to Opaque description, as shown. \label{sec:tree-sepex:twocm} Many classes admit machines which, when intersected, yield the two-counter -example of \cite{tata}.% +example of \cite{tata} (also \autoref{sec:zoo-tree/ra:ndempty}).% % \footnote{\Note{Somewhere, possibly here, more should be said about this excellent example. A concise summary of how it does what it does is that @@ -138,7 +155,7 @@ intersection}. \begin{lrbox}{\tempboxb} \begin{minipage}{3cm} \begin{align*} - h(q_g, q_\forall) &\rightarrow{12=2} q_f \\ + h(q_g, q_\forall) &\xrightarrow{12=2} q_f \\ g(q_\forall, q_\forall) &\rightarrow q_g \end{align*} \end{minipage} diff --git a/treeautintro.tex b/treeautintro.tex index c413551..3ac4f4a 100644 --- a/treeautintro.tex +++ b/treeautintro.tex @@ -1,6 +1,6 @@ Just as string automata describe sets of strings over some alphabet of characters, tree automata describe sets of trees whose nodes are labeled -with elements of some set $\Sigma$. We focus initially on {\em ranked} tree +with elements of some set $\alphabet$. We focus initially on {\em ranked} tree automata. \subsection{Notation for Trees} @@ -8,14 +8,14 @@ automata. \Note{Positions} \Note{subterm-at-position} -$\Sigma_n \defeq \set{ \sigma \in \Sigma \middle\vert \mbox{ar}(\sigma) = n}$ -and $\Sigma_+ \defeq \Sigma\setminus\Sigma_0$. +$\alphabet_n \defeq \set{ \sigma \in \alphabet \middle\vert \mbox{ar}(\sigma) = n}$ +and $\alphabet_+ \defeq \alphabet\setminus\alphabet_0$. \subsection{Execution of Automata} As with the string case, there will be configurations $\config$, and a -privileged subset $\config_F$. However, transition functions are -quite different, and in fact split into two sub-classes of tree automata:% +privileged subset $\config_F$. However, transition functions are quite +different, and in fact split into two sub-classes of tree automata:% % \footnote{The transition functions presented here are for {\em deterministic} automata. See \autoref{xxx} for details of non-deterministic @@ -23,41 +23,67 @@ automata.} % \begin{itemize} % - \item $\delta^{op} : \config \to \mathcal{T}(\Sigma \sqcup \config)$ defines a - \defn{top-down} automaton, which can be thought of generating a tree - root-first; the positions in the output which are configurations are - recursively expanded into trees. + \item $\delta^{op} : \Pi_{t \in \mathcal{T}(\alphabet \sqcup \set{\star})} +. \config \times t \to (1 + (P_{t,\star} \to \config))$, where $P_{t,\star} = +\set{ \pi \mid t\downharpoonleft_\pi = \star}$, defines a \defn{top-down} +automaton, which matches a tree root-first. It is given a configuration +$\config$ and a tree with some leaves being the symbol $\star$ and either +fails or returns a map from paths to $\star$ nodes to configurations. % - \item $\delta : \mathcal{T}(\Sigma \sqcup \config) \to (1 + \config)$ defines a - \defn{bottom-up} automaton, which can be thought of as consuming a tree - leaves-first. Note that we allow, in general, the automata to refuse to - label a node (the $1$ return value), but certain classes of automata will - not avail themselves of this option. + \item $\delta : \mathcal{T}(\alphabet \sqcup \config) \to (1 + \config)$ +defines a \defn{bottom-up} automaton, which can be thought of as consuming a +tree leaves-first; the transition function will be presented with a subtree +with some subtrees replaced by configurations $\config$. The automaton +considers smaller such subtrees first. Note that we allow, in general, the +automata to refuse to label a node (the $1$ return value), but certain +classes of automata will not avail themselves of this option. % \end{itemize} -A \defn{run} of a tree automaton to be a tree in $\mathcal{T}\paren{\Sigma -\times (1 + \mathcal{T}(\Sigma \sqcup \config) \times \config)}$: an +A \defn{run} of a tree automaton to be a tree in $\mathcal{T}\paren{\alphabet +\times (1 + \mathcal{T}(\alphabet \sqcup \config) \times \config)}$: an augmented tree where each node is additionally, optionally, labeled by input and output of $\delta$. For each node $\sigma \times \mbox{inr}(t \times c)$, $\delta t = c$ (or $\delta^{op} c = t$), and all positions of $t$ which -are in $\Sigma$ must agree with the first projection of the run itself, and +are in $\alphabet$ must agree with the first projection of the run itself, and all positions of $t$ which are in $\config$ must be so-labeled by the run. \Note{That's not very clear, but I think it's right.} For a run $r$, we define $\tr{r|_p}$ to be the function which returns the -$\Sigma$ of the original tree at position $p$. -Similarly, we define -$\lab{r|_p}$ as the (partial) function which returns -the output configuration at position $p$. +$\alphabet$ of the original tree at position $p$. Similarly, we define +$\lab{r|_p}$ as the (partial) function which returns the output +configuration at position $p$. \subsection{Nondeterminism} +\Note{...} + +Generalizing the {\em deterministic} transition functions above, we can +define +% +\begin{itemize} +% + \item +% + \item $\delta : \mathcal{T}(\alphabet \sqcup \config) \to \mathcal{P}\config$ +defines a \defn{non-deterministic bottom-up} automaton. If a subtree is +labeled by $C \subseteq \config$, then the execution will consider each $c +\in C$ when applying $\delta$ at higher positions in the tree. +% +\end{itemize} + \subsection{Plies} -An important subclass of tree automata are the \defn{single-ply} automata, -where $\delta$ is restricted to manipulation of trees of the form -$\mathcal{T}(\Sigma_+ \sqcup \config)$. +An important subclass of tree automata are the \defn{single-ply} automata. +Here, $\delta$ is restricted to manipulation of trees of the form +$\bigcup_{n} \alphabet_n \config^n$. Dually, $\delta^{op}$ will be called +only on $t \in \Pi_{n \in \mathbb{N}} . \alphabet_n \star^n$ and will be +obligated to return successfully. Note that, in this case, $(P_{t,\star} +\to \config) \simeq (\set{1,\ldots,n} \to \config) \simeq \config^n$, so the +single-ply $\delta^{op}$ has type $\Pi_{n \in \mathbb{N}} . \config \times +\alphabet_n \star^n \to \config^n$, which is (more) readily seen to be the +type of functions which are given a configuration and a symbol (of arity +$n$) and return $n$ configurations. % \subsection{New Operations: Cylindrification and Projection} % @@ -70,14 +96,14 @@ $\mathcal{T}(\Sigma_+ \sqcup \config)$. A natural novelty of tree automata is one of {\em constraints} between positions in a (sub)tree. One way of inducing such constraints is to augment the transition function, inducing {\em local} tests in the tree; one -can think of this as including $\mathcal{T}(\Sigma)$ as a projection of +can think of this as including $\mathcal{T}(\alphabet)$ as a projection of $\config$, though with restricted handling within the transition function,\eg only comparison for (dis)equality. We view a locally constrained automaton as a transition function which performs a series of tests as part of its transition function {\em after pattern matching}, meaning that it may be expressed as a (possibly infinite) -union of transitions of the form $\mathcal{T}(\Sigma \sqcup \config) +union of transitions of the form $\mathcal{T}(\alphabet \sqcup \config) \stackrel{c}{\longrightarrow} \config$, where $c$ is a set of constraints between positions below the node under study. These positions are indicated by paths, and we often use the term \defn{constraint path} to refer to paths @@ -129,7 +155,7 @@ constraint path may cross this position. %} \paragraph{Reduction} There exists a partial order on $\config$ such that -$\forall_{t \in \mathcal{T}(\Sigma \sqcup \config), c \in \config}$, $t$ and +$\forall_{t \in \mathcal{T}(\alphabet \sqcup \config), c \in \config}$, $t$ and $c$ being related by transition implies that $\forall_{c' \in t} . c' \le c$, strictly if the transition between $t$ and $c$ induces any constraints. @@ -141,10 +167,11 @@ $\config$. \subparagraph{$f$-Same-Stated} All positions mutually constrained must be labeled (as above) and further the $f$-image of these configurations must be -identical. (That is, the pattern of $\mathcal{T}(\Sigma \sqcup \config)$ +identical. (That is, the pattern of $\mathcal{T}(\alphabet \sqcup \config)$ matched by a transition must be sufficient to ensure that all constraint -paths end in equal-$f$-image nodes of the run.) When $f$ is the identity -function or otherwise clear from context, we may simply say ``Same-Stated''. +paths end in equal-$f$-image nodes of the run.) When $f$ is the identity +function or otherwise clear from context, we may simply say +``Same-Stated''. \subsubsection{Interrelation of Metaconstraints} @@ -158,9 +185,21 @@ Contained and Stated together imply Opaque. Non-Overlapping also implies Opaque (but the reverse is not true: see \autoref{sec:tree-sepex:necessaryoverlap}). -In a deterministic automaton, satisfiable equality constraints referencing -labeled nodes are necessarily $f$-Same-Stated (for all $f$) as equal trees -produce equal runs. +\subsubsection{Same-Stated vs. Determinism} + +In general, equality constraints with paths terminating in different states +is implicitly asking for a tree which is in the {\em intersection} of the +languages of trees accepted by that state in addition to any other +constraints imposed by other constraints above the two constraint paths' +termini. Same-Stated does not eliminate these additional constraints, but +prevents the automata from performing these particular intersection tests at +runtime. + +In a fully deterministic automaton, then, all satisfiable equality +constraints referencing at least one labeled node are necessarily +Same-Stated as equal trees produce equal runs; any constraint which referred +to nodes in different states would, therefore, be restricting to the +intersection of two disjoint sets of trees, \ie the empty set. \subsection{Transducers} diff --git a/zoo-tree/awcbb.tex b/zoo-tree/awcbb.tex index afc3cad..d5b7dae 100644 --- a/zoo-tree/awcbb.tex +++ b/zoo-tree/awcbb.tex @@ -1,6 +1,7 @@ AWCBB is a sub-class of AWEDC wherein all transitions are single-ply and all (dis)equalities adhere to the Brother and Contained metaconstraints (by -implication, they are also Opaque and Stated). See \cite[Sec 4.3]{tata}. +implication, they are also Opaque and Stated; Available is trivially +satisfied by well-formed automata of this class). See \cite[Sec 4.3]{tata}. \autinfo{ member={}, diff --git a/zoo-tree/awedc.tex b/zoo-tree/awedc.tex index 0998cd6..d8f6acc 100644 --- a/zoo-tree/awedc.tex +++ b/zoo-tree/awedc.tex @@ -2,8 +2,8 @@ Also called ``Automata With Equality and Disequality Constraints'' (AWEDC), this class of automata augments regular tree automata with the ability to require (dis)equality of positions in accepted trees, using local constraints. In general, the configuration space of these machines is -$\config = \mathcal{Q} \times \mathcal{T}(\Sigma)$ for states $\mathcal{Q}$ -and input alphabet $\Sigma$; however, $\delta$ is constrained as outlined in +$\config = \mathcal{Q} \times \mathcal{T}(\alphabet)$ for states $\mathcal{Q}$ +and input alphabet $\alphabet$; however, $\delta$ is constrained as outlined in \autoref{sec:treeaut:con:loc} to only perform comparisons within the tree structure; it may not compare against external trees. The automata is accepting when the root node of a run is labeled by a configuration whose diff --git a/zoo-tree/ra.tex b/zoo-tree/ra.tex index f6e1e9e..bef0a55 100644 --- a/zoo-tree/ra.tex +++ b/zoo-tree/ra.tex @@ -6,7 +6,13 @@ implication, Stated).} \Note{\cite[p133]{tata} discusses the relaxation of RA to permit AWCBB-style constraints freely; what I've called ``Deep-Reduction'' above. This class has decidable emptyness testing.} +\subsection{Proof of Decidable Emptiness of Deterministic RA} + +\cite[\S 4.1]{dauchet:reduction} offers an interesting proof that emptiness +testing for deterministic RAs is decidable. \Note{...} + \subsection{Proof of Non-deterministic RA Undecidable Emptiness Testing} +\label{sec:zoo-tree/ra:ndempty} \cite[Thm 4.4.7]{tata} contains a proof% % @@ -19,18 +25,20 @@ non-deterministic case as well.} that emptiness is not decidable for the class of nondeterminstic RAs. (This proof generalizes to a large class of tree automata; see \autoref{sec:tree-sepex:twocm}.) We feel that a few words said about this -proof here may help to de-mystify it. +proof here may help to de-mystify it. A decomposition if this machine into +simpler automata whose intersection is this machine may be found in +\ref{sec:tree-sepex:twocm}. \begin{wrapfigure}{r}{3.5in}\centering\begin{tikzpicture} \Tree [.h$_n$ - [.q $C_n$ - [.h$_{n-1}$ [.q $C_{n-1}$ [.h$_{n-2}$ \edge[roof];$\cdots$ ] ] + [.g $C_n$ + [.h$_{n-1}$ [.g $C_{n-1}$ [.h$_{n-2}$ \edge[roof];$\cdots$ ] ] [.h$_{n-2}$ \edge[roof];$\cdots$ ] ] ] [.h$_{n-1}$ - [.q \edge[roof];$\cdots$ ] + [.g \edge[roof];$\cdots$ ] [.h$_{n-2}$ - [.q \edge[roof];$\cdots$ ] - [.$\cdots$ $\cdots$ [.h$_{1}$ [.q \edge[roof];$C_1$ \# ] \# ] ] + [.g \edge[roof];$\cdots$ ] + [.$\cdots$ $\cdots$ [.h$_{1}$ [.g \edge[roof];$C_1$ \# ] \# ] ] ] ] ] @@ -39,18 +47,25 @@ proof here may help to de-mystify it. The overall structure of the trees accepted by this construction was not immediately obvious to at least one author of this zoo, so a schematic view is given here. Each h$_i$ represents the apex of {\em the same tree} -everywhere it occurs. (\cite{tata} sometimes labels the root of the tree -``k'' and sometimes ``h$'$''; this does not appear essential to the -construction and so we simply use ``h'' pervasively.) Every h$_i$ node -carries the trace of the first $i$ steps of execution on its right; its left -child can be thought of as the pair of the $i$-th state of the machine's -execution, denoted $C_i$, and h$_{i-1}$. The equality constraints are -introduced only at the top and at ``q'' nodes in the tree; the state labels -are carefully constructed so that only three ranks are required to satisfy -the Reduction metaconstraint: a base rank, which includes all labels in the -$C_i$ trees is $\le$ a ``q''-state rank which includes the labels of all -``q'' and ``h'' nodes in the tree except the apex; the accepting state at -the root is the sole member of the third rank. There will be $2^{n-i+1}$ -copies of $h_i$ (or $C_i$) in a tree encoding $n$ steps. This machine is -{\em deeply} dependent on the fact that non-determinism allows equal trees -to have several distinct runs. +everywhere it occurs; the subscript is {\em not} part of the functor symbol, +which is just h at each of these positions.% +% +\footnote{\cite{tata} sometimes labels the root of the tree ``k'' and +sometimes ``h$'$''; this does not appear essential to the construction and +so we simply use ``h'' for the entire right spine; the only requirement +imposed by the Reduction metaconstraint is that root {\em state} have rank +greater than the state label used for the right spine and for the top-left q +node; this does not require that the root {\em symbol} itself be different.} +% +Every h$_i$ node carries the trace of the first $i$ steps of execution on +its right; its left child can be thought of as the pair of the $i$-th state +of the machine's execution, denoted $C_i$, and h$_{i-1}$. The equality +constraints are introduced only at the top and at ``g'' nodes in the tree; +the state labels are carefully constructed so that only three ranks are +required to satisfy the Reduction metaconstraint: a base rank, which +includes all labels in the $C_i$ trees is $\le$ a ``g''-state rank which +includes the labels of all ``g'' and ``h'' nodes in the tree except the +apex; the accepting state at the root is the sole member of the third rank. +There will be $2^{n-i}$ copies of $h_i$ (or $C_i$) in a tree encoding $n$ +steps. This construction is {\em deeply} dependent on the fact that +non-determinism allows equal trees to have several distinct runs. diff --git a/zoo-tree/rta.tex b/zoo-tree/rta.tex deleted file mode 100644 index 8e4a5da..0000000 --- a/zoo-tree/rta.tex +++ /dev/null @@ -1,34 +0,0 @@ -Rigid Tree Automata (RTA) are introduced by \cite{jacquemard:rta}. - -An RTA has a distinguished set of configurations, $R \subseteq \config$, and -imposes the global constraint (Def. 2) that $\forall_{p_1,p_2} . \brak{ -r(p_1) = r(p_2) \in R } \Rightarrow t\vert_{p_1} = t\vert_{p_2}$. (That is, -for each configuration $r \in R$, all nodes in the run labeled with $r$ must -root equal sub-trees.) - - -\subsection{Relation to other classes} -RTA are a strict sub-class of TAGED (\autoref{sec:zoo-tree/taged}; -\cite[Sec. 3.1]{jacquemard:rta}) but are a super-class of TAGED+ (at -possible exponential complexity; see Prop. 2 and \cite{filiot:tagc}). - -\Note{Other classes also discussed in Sec. 3: TAC, DAG automata, TA1M, -ACRV.} - -Deterministic RTA are a strict sub-class of RTA (Thm. 4) but strictly -include TA without constraints (Thm. 5). - -\autinfo{ - empty={Linear time; Sec. 6.1}, - member={NP-complete; Sec. 6.2}, - univ={No; Sec. 6.4}, - finite={PTIME; Sec 6.6}, -% - compl={No; Sec. 4.2}, - determinize={No; Sec. 5.1}, -% - equiv={No; Sec. 6.5}, -% - union={Linear time and space; Sec. 4.1}, - intersect={Exponential time and space; Sec. 4.1}, -} diff --git a/zoo-tree/taec.tex b/zoo-tree/taec.tex new file mode 100644 index 0000000..56e6829 --- /dev/null +++ b/zoo-tree/taec.tex @@ -0,0 +1,66 @@ +Tree Automata with Equational Constraints are introduced in +\cite{jacquemard:tamodeq}. The key innovations over Reduction Automata +(\autoref{sec:zoo-tree/ra}) are +% +\begin{itemize} +% + \item A generalization of equality constraints to ``equational + constraints'' + \item A strengthening of the Reduction metaconstraint. +% +\end{itemize} + +TAECs permit two form of clauses (names and syntax from +\cite{jacquemard:tamodeq}). +% +\begin{itemize} +% + \item[(t)] Written ``$Q_1(x_1),\ldots,Q_n(x_n) \Rightarrow + Q(f(x_1,\ldots,x_n))$, this form is a typical transition as might be found + in a TA: $Q$ and the $Q_i$ are configurations of the machine, $x_i$ are + subtrees. We might also express this rule as $f(Q_1,\ldots,Q_n) \to Q$ in + the notation of other works. +% + \item[(d)] Written $Q_1(x_1),\ldots,Q_n(x_n),u_1 = v_1,\ldots,u_k = v_k + \Rightarrow Q(x)$, the novel $u_i$ and $v_i$ are trees over the alphabet + of the automaton {\em and} $x$ and the $x_i$s (interpreted as nullary + symbols). This transition fires only when the equations hold. Note that + the target of the rule is not required to have the $x_i$s as subtrees! +% +\end{itemize} + +The configuration space is partitioned into (partially ordered) ranks; +configurations in any rank other than the (unique) lowest are called ``test +predicates''. These ranks are used in metaconstraints imposed on clauses. +(Note the similarity to Reduction.) +% +\begin{itemize} +% + \item[(t)] Either + % + \begin{itemize} + % + \item $Q$ and all $Q_i$ are at the lowest rank (\ie are not test + predicates) + % + \item $Q$ is a test predicate (not at the lowest rank) + and {\em at most one} $Q_i$ is equal to + $Q$ and all others are {\em not} test predicates. + % + \end{itemize} + % + \item[(d)] $Q$ is a test predicate and all $Q_i$ are either not test + predicates or test predicates of lower rank than $Q$. +% +\end{itemize} + +These constraints permit constructions like the all equal list and markovian +equal lists but do not permit the rules that would be necessary for +equal-leaved full N-ary trees, as the recursive rule produces a test +predicate (because it compares its children) but recurses to $N \ge 2$ +occurrences of that same state. + +\paragraph{Equational Constraints} Whereas equality constraints require +that the subtrees at two positions are equal in order for the rule to fire, +equational constraints gate the rule by a series of equalities between trees +which contain variables. diff --git a/zoo-tree/taged.tex b/zoo-tree/taged.tex index 854c67a..ca561e7 100644 --- a/zoo-tree/taged.tex +++ b/zoo-tree/taged.tex @@ -6,6 +6,10 @@ state set $\sts$) together with two relations: \item $=_A \subset \sts^2$ reflexive and symmetric, \item $\neq_A \subseteq \sts^2$ irreflexive and symmetric. \end{itemize} +% +(Note that these relations need not be total: there may exist two states $p$ +and $q$ for which neither $p =_A q$ nor $p \neq_A q$ holds.) +% A run $r$ of a TAGED automaton is a run of the underlying regular automaton which additionally satisfies, for all positions $p$ and $p'$ in the run, \begin{itemize} @@ -13,10 +17,16 @@ which additionally satisfies, for all positions $p$ and $p'$ in the run, \item $\lab{r|_p} \neq_A \lab{r|_{p'}} \Rightarrow \tr{r|_p} \neq \tr{r|_{p'}}$. \end{itemize} -\paragraph{Sub-classes} Polarized forms (``positive'' and ``negative'') are -also defined as TAGED automata without disequalities (resp. equalities). A -``vertically bounded'' TAGED is an automaton in which there is a static -bound on the number of globally-disequal states on each root-to-leaf path. +\paragraph{Sub-classes} +\begin{itemize} +% + \item Polarized forms are defined and denoted $TAGED+$ (for which $\neq_A = \emptyset$) and $TAGED-$ ($=_A = \emptyset$). +% + \item A ``vertically bounded'' TAGED is an automaton in which +there is a static bound on the number of globally-disequal states on each +root-to-leaf path. +% +\end{itemize} Unless otherwise indicated, references in this table are to \cite{filiot:tagc}. @@ -31,3 +41,50 @@ Unless otherwise indicated, references in this table are to compl={No; Prop 4}, determinize={No; Prop 3}, } + +\subsection{Rigid Tree Automata} +\label{sec:zoo-tree/rta} + +Rigid Tree Automata (RTA) are introduced by \cite{jacquemard:rta}. Like +TAGED, a RTA is defined by a regular tree automaton (with state set $\sts$) +and a distinguished set of configurations, $R \subseteq \sts$, and +imposes the global constraint (Def. 2) that $\forall_{p_1,p_2} . \brak{ +r(p_1) = r(p_2) \in R } \Rightarrow t\vert_{p_1} = t\vert_{p_2}$. + +\subsubsection{Relation to other classes} + +RTAs are \dots +% +\begin{itemize} +% + \item easily seen to be a sub-class of TAGED+ (\cite[Sec. +3.1]{jacquemard:rta}), with the injection trivial. +% + \item a super-class of TAGED+, at possible exponential space complexity; +see \cite[Prop. 2]{jacquemard:rta} and \cite{filiot:tagc}). +% +\end{itemize} + +\Note{Other classes also discussed in Sec. 3: TAC, DAG automata, TA1M, +ACRV.} + +Deterministic RTA are a strict sub-class of RTA (Thm. 4) but strictly +include TA without constraints (Thm. 5). + +Unless otherwise indicated, references in this table are to +\cite{jacquemard:rta}. +\autinfo{ + empty={Linear time; Sec. 6.1}, + member={NP-complete; Sec. 6.2}, + univ={No, reduction of PCP; Sec. 6.4}, + finite={PTIME; Sec. 6.6}, +% + compl={No; Sec. 4.2}, + determinize={No; Sec. 5.1}, +% + equiv={No, by implication of universality; Sec. 6.5}, + subset={No, by implication of universality; Sec 6.5}, +% + union={Linear time and space; Sec. 4.1}, + intersect={Exponential time and space; Sec. 4.1}, +} diff --git a/zoo-tree/tahom.tex b/zoo-tree/tahom.tex index e81313b..18f1568 100644 --- a/zoo-tree/tahom.tex +++ b/zoo-tree/tahom.tex @@ -1,5 +1,62 @@ \Note{Various classes are introduced by \cite{godoy:hom}. -$TA_{\text{hom},\neq}$ is multi-ply AWEDC subject to Contained and Same-Stated -(and, by implication, Opaque) only for equality constraints; disequality -constraints are without metaconstraints. } + +Introduced by \cite[Definition 4.1]{godoy:hom}, $TA_{\text{hom}}$ is the +class of positive, multi-ply AWEDCs (\autoref{sec:zoo-tree/awedc}) whose +equality constraints are subject to Contained and Same-Stated (and, by +implication, Opaque). + +Notably, $TA_{\text{hom}}$ is sufficient to capture the family of languages +which are tree-homomorphic images of positive AWEDCs (\ie $TA_{=}$). +\cite[Proposition 4.6]{godoy:hom}. + +Also introduced by \cite[Definition 4.1]{godoy:hom}, $TA_{\neq,\text{hom}}$ +is similar to $TA_{\text{hom}}$ with the addition of arbitrary disequality +constraints. + +For $TA_{\neq,\text{hom}}$, we have: +\autinfo{ + empty={Yes; pumping construction \cite[Corollary 5.11]{godoy:hom}.}, + intersect={No; see below.}, +} + +\subsection{Intersection Non-closure of $TA_{\text{hom}}$} + +\begin{wrapfigure}{l}{3.75in}\centering\begin{tabular}{cc} + {$\!\begin{aligned} + \text{nil} &\xrightarrow{\phantom{1=21}} q_f \\ + \text{cons}(q_e, \text{cons}(q_e,q_l)) &\xrightarrow{1=21} q_f \\ + \text{a} &\xrightarrow{\phantom{1=21}} q_e \\ + \text{f}(q_e,q_e) &\xrightarrow{\phantom{1=21}} q_e \\ + \end{aligned}$} +& + {$\!\begin{aligned} + \text{cons}(q_e, \text{nil}) &\xrightarrow{\phantom{1=21}} q_l \\ + \text{cons}(q_e, \text{cons}(q_e,q_l)) &\xrightarrow{1=21} q_l \\ + \text{cons}(q_e, q_l) &\xrightarrow{\phantom{1=21}} q_f \\ + \text{a} &\xrightarrow{\phantom{1=21}} q_e \\ + \text{f}(q_e,q_e) &\xrightarrow{\phantom{1=21}} q_e \\ + \end{aligned}$} +\end{tabular} +\caption{$TA_{\text{hom}}$ to exhibit failure of intersection +closure.} +\label{fig:zoo-tree/tahom:icf} +\end{wrapfigure} + +The proof sketch here relies on the all-equal separating example of +\autoref{sec:tree-sepex:allequallist}. We can exhibit $TA_{\text{hom}}$ +automata for the set of lists of even length whose elements are from the +infinite set $\mathcal{T}\set{f/2, a/0}$, and whose consecutive elements are +equal (\eg $[A,A,B,B,\ldots,Y,Y,Z,Z]$), as on the left of +\autoref{fig:zoo-tree/tahom:icf}, and for the related set of lists which +have ``one more'' element on the beginning and end (\eg +$[A,B,B,C,C,\ldots,Y,Y,Z]$), as on the right. In both cases, $q_f$ is the +sole accepting state of the machine. Note that the former machine is {\em +deterministic} while the latter is top-down deterministic but only bottom-up +deterministic given one symbol of lookahead. Their intersection would be +the set of non-empty, even-length, all-equal lists $[A,A,A,\ldots,A]$, which +would require an infinite collection of $TA_{\text{hom}}$ transitions, one +for each length. + +\Note{This leaves open the question of the intersection closure of +bidirectionally determinstic $TA_{\text{hom}}$.} -- 2.50.1