From 7b9fd7410899bf0b2dae29f1f38fde1d78da98a5 Mon Sep 17 00:00:00 2001 From: Nathaniel Wesley Filardo Date: Thu, 27 Mar 2014 17:35:37 -0400 Subject: [PATCH] Small scattered changes --- main.tex | 7 +++++++ treeautintro.tex | 15 +++++++++++---- zoo-str/pda.tex | 2 ++ zoo-tree/awcbb.tex | 15 +++++++++++++-- zoo-tree/awedc.tex | 20 ++++++++++++++++++++ zoo-tree/regular.tex | 10 +++++++++- 6 files changed, 62 insertions(+), 7 deletions(-) diff --git a/main.tex b/main.tex index 301e37a..85f6226 100644 --- a/main.tex +++ b/main.tex @@ -130,6 +130,9 @@ or \url{http://www.gnu.org/licenses/agpl-3.0.txt}) or any later version.}} \define@key{autinfo}{reginter} {\def\autabsregi{#1}} % trio \define@key{autinfo}{hom} {\def\autabshom {#1}} % full trio +\define@key{autinfo}{cylind} {\def\autcylind {#1}} +\define@key{autinfo}{proj} {\def\autproj {#1}} + \define@key{autinfo}{regops} {\def\autregintr{#1} % all regops at once \def\autregun {#1} \def\autregkstr{#1}} @@ -163,6 +166,8 @@ or \url{http://www.gnu.org/licenses/agpl-3.0.txt}) or any later version.}} \def\autabsmoh {} \def\autabsregi{} \def\autabshom {} + \def\autcylind {} + \def\autproj {} \setkeys{autinfo}{#2} {\centering @@ -187,6 +192,8 @@ or \url{http://www.gnu.org/licenses/agpl-3.0.txt}) or any later version.}} \ifdefempty{\autabshom} {}{Arbitrary Hom. & \autabshom \\ \hline} \ifdefempty{\autabsehom}{}{$\epsilon$-free Hom. & \autabsehom \\ \hline} \ifdefempty{\autabsregi}{}{Intersect reg. lang. & \autabsregi \\ \hline} + \ifdefempty{\autcylind }{}{Cylindrification & \autcylind \\ \hline} + \ifdefempty{\autproj }{}{Projection & \autproj \\ \hline} \textbf{Automata Operations} & \\ \hline \ifdefempty{\autmiscdet}{}{Determinizable & \autmiscdet \\ \hline} \ifdefempty{\autmiscmin}{}{Minimizable & \autmiscmin \\ \hline} diff --git a/treeautintro.tex b/treeautintro.tex index a486d36..38a0eb8 100644 --- a/treeautintro.tex +++ b/treeautintro.tex @@ -61,6 +61,11 @@ 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)$. +% \subsection{New Operations: Cylindrification and Projection} +% +% Originally defined for automata operating on tuples of trees \cite[Sec +% 3.2.4]{tata} + \subsection{Local Constraints} \label{sec:treeaut:con:loc} @@ -82,16 +87,18 @@ constrained positions. \subsubsection{Metaconstraints} -In general, tree automata with arbitrary constraints have very poor closure -properties (see \autoref{xxx}). A variety of restrictions have been -developed throughout the literature and are summarized here. +In general, tree automata with arbitrary local constraints have undecidable +decision procedures (see \autoref{sec:zoo-tree/awedc}). A variety of +restrictions have been developed throughout the literature and are +summarized here. \paragraph{Brothers} The transition function may only mutually constrain positions which differ only in the last index. \paragraph{Contained} All positions tested for equality must be within the fragment of the tree being labeled (or generated); that is, constraint paths -may not involve a $\config$-labeled run node other than at their apex. +may not involve a $\config$-labeled run node other than at their apex and +endpoints. \paragraph{Opaque} If a position is constrained by a transition, no other constraint path may cross this position. diff --git a/zoo-str/pda.tex b/zoo-str/pda.tex index 19583fe..c033708 100644 --- a/zoo-str/pda.tex +++ b/zoo-str/pda.tex @@ -44,6 +44,7 @@ configurations for PDAs: } \subsection{Non-deterministic PDAs} +\label{sec:zoo-str/pda-nd} Non-deterministic PDAs' recognition corresponds exactly to context free languages. Deterministic PDAs can recognize the subset of context-free languages, @@ -59,5 +60,6 @@ or \cite[Ch. 2]{sipser:theorycomp} for thourough introductions. \hyperref[sec:zoo-str/tm]{TM}. \cite{xxx}}, equiv={Undecidable; $\Sigma^*$ is recognizable, but universality is undecidable.}, + intersect={Undecidable; reduction from Post Correspondance \cite{xxx}}, } diff --git a/zoo-tree/awcbb.tex b/zoo-tree/awcbb.tex index da56efc..afc3cad 100644 --- a/zoo-tree/awcbb.tex +++ b/zoo-tree/awcbb.tex @@ -1,2 +1,13 @@ -\Note{AWCBB is single-ply AWEDC subject to Brother and Contained -metaconstraints (and, by implication, Opaque and Stated).} +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}. + +\autinfo{ + member={}, + empty={Yes; EXPTIME \cite[Thm 4.3.5]{tata}; PTIME for det case \cite[Thm 4.3.6]{tata}}, + union={Yes, as with AWEDC; \cite[Prop 4.3.2]{tata}}, + intersect={Yes, as with AWEDC; \cite[Prop 4.3.2]{tata}}, + compl={Yes, as with AWEDC; \cite[Prop 4.3.2]{tata}}, + cylind={No; \cite[Sec 4.3.4]{tata}}, + proj={No; \cite[Sec 4.3.4]{tata}}, +} diff --git a/zoo-tree/awedc.tex b/zoo-tree/awedc.tex index e69de29..0998cd6 100644 --- a/zoo-tree/awedc.tex +++ b/zoo-tree/awedc.tex @@ -0,0 +1,20 @@ +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 +\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 +first component is in a set of accepting states, $\mathcal{Q}_f$. See +\cite[Sec 4.2]{tata} for details. + +\autinfo{ + member={Yes; PTIME (linear for deterministic) \cite[Prop 4.2.9]{tata}}, + empty={Undecidable by reduction of PCP; \cite[Thm 4.2.10]{tata}}, + compl={Yes; \cite[Prop 4.2.8]{tata}}, + union={Yes; linear time and space \cite[Prop 4.2.8]{tata}}, + intersect={Yes; quadratic time and space \cite[Prop 4.2.8]{tata}}, + determinize={Yes; exponential space cost \cite[Prop 4.2.6]{tata}} +} diff --git a/zoo-tree/regular.tex b/zoo-tree/regular.tex index d7bac68..cd3b9fc 100644 --- a/zoo-tree/regular.tex +++ b/zoo-tree/regular.tex @@ -6,7 +6,15 @@ single-ply automaton, and the reverse direction is clearly trivial. Given a family of trees accepted by a regular tree automata, the set of strings formed by labels along paths in this set is a regular finite string -language. The same is true of accepting runs. +language. The same is true of accepting runs. The set of strings formed by +leaves of a regular tree automata (its ``leaf language'') is a context-free +language; dually, every context-free language is the leaf language of some +regular tree automaton.% +% +\footnote{While intersection of two context free language is undecidable +(see \autoref{sec:zoo-str/pda-nd}), the intersection of regular tree languages +is decidable: the leaf language of the intersection of two regular tree +languages is a {\em subset} of the intersection of their leaf languages.} For bottom-up automata, we have: \autinfo{ -- 2.50.1