From deb38a4cd50477870d536ee56564a6f0501dabdd Mon Sep 17 00:00:00 2001
From: Nathaniel Wesley Filardo <nwf@cs.jhu.edu>
Date: Wed, 5 Mar 2014 15:02:02 -0500
Subject: [PATCH] Add section for Rigid Tree Automata

---
 biblio.bib       | 32 ++++++++++++++++++++++++++++++++
 main.tex         |  1 +
 zoo-tree/rta.tex | 34 ++++++++++++++++++++++++++++++++++
 3 files changed, 67 insertions(+)
 create mode 100644 zoo-tree/rta.tex

diff --git a/biblio.bib b/biblio.bib
index a44602e..6d2aaf0 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -120,3 +120,35 @@ mechanism. We combine the above constructions adequately to provide an algorithm
 	year = {2010},
 	pages = {158–174},
 }
+
+@article{jacquemard:rta,
+	title = {Rigid tree automata and applications},
+	volume = {209},
+	issn = {08905401},
+	url = {http://linkinghub.elsevier.com/retrieve/pii/S0890540110002014},
+	doi = {10.1016/j.ic.2010.11.015},
+	pages = {486-512},
+	number = {3},
+	journaltitle = {Information and Computation},
+	author = {Jacquemard, Florent and Klay, Francis and Vacher, Camille},
+	urldate = {2014-03-05},
+	date = {2011-03},
+}
+
+@incollection{filiot:tagc,
+	title = {Tree Automata with Global Constraints},
+	rights = {©2008 Springer-Verlag Berlin Heidelberg},
+	isbn = {978-3-540-85779-2, 978-3-540-85780-8},
+	url = {http://link.springer.com/chapter/10.1007/978-3-540-85780-8_25},
+	series = {Lecture Notes in Computer Science},
+	abstract = {A tree automaton with global tree equality and disequality constraints, {TAGED} for short, is an automaton on trees which allows to test (dis)equalities between subtrees which may be arbitrarily faraway. In particular, it is equipped with an (dis)equality relation on states, so that whenever two subtrees t and t′ evaluate (in an accepting run) to two states which are in the (dis)equality relation, they must be (dis)equal. We study several properties of {TAGEDs}, and prove decidability of emptiness of several classes. We give two applications of {TAGEDs:} decidability of an extension of Monadic Second Order Logic with tree isomorphism tests and of unification with membership constraints. These results significantly improve the results of [10].},
+	pages = {314-326},
+	number = {5257},
+	booktitle = {Developments in Language Theory},
+	publisher = {Springer Berlin Heidelberg},
+	author = {Filiot, Emmanuel and Talbot, Jean-Marc and Tison, Sophie},
+	editor = {Ito, Masami and Toyama, Masafumi},
+	urldate = {2014-03-05},
+	date = {2008},
+	keywords = {Algorithm Analysis and Problem Complexity, Computation by Abstract Devices, Discrete Mathematics in Computer Science, Mathematical Logic and Formal Languages, Symbolic and Algebraic Manipulation}
+}
diff --git a/main.tex b/main.tex
index 16e434c..2d55300 100644
--- a/main.tex
+++ b/main.tex
@@ -244,6 +244,7 @@ or \url{http://www.gnu.org/licenses/agpl-3.0.txt}) or any later version.}}
 \maininclude{Constraints Between Brothers}{zoo-tree/awcbb}
 \maininclude{Reduction Automata}{zoo-tree/ra}
 \maininclude{Homomorphism-Equality Automata}{zoo-tree/tahom}
+\maininclude{Rigid Tree Automata}{zoo-tree/rta}
 
 %\part{Infinite Trees}
 
diff --git a/zoo-tree/rta.tex b/zoo-tree/rta.tex
new file mode 100644
index 0000000..317dcee
--- /dev/null
+++ b/zoo-tree/rta.tex
@@ -0,0 +1,34 @@
+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}; Sec. 3.1) 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},
+}
-- 
2.50.1