<p>Here is a short list of authors that work on the connections between tree automata, logic and databases. For each author, I will just give one paper, but many more can be found on the respective web pages of these authors.</p>

<p>[1] <a href="http://www.lsv.ens-cachan.fr/~segoufin/Papers/index.html">Luc Segoufin</a></p>

<p><a href="http://www.lsv.ens-cachan.fr/~segoufin/Papers/Mypapers/tdafo.pdf">FO2(+1,&lt;.~) on data trees, data tree automata and branching vector addition systems</a></p>

<p>[2] <a href="http://www.tks.informatik.uni-frankfurt.de/publications?lang=en&amp;style=byyear&amp;member=schweika">Nicole Schweikardt</a></p>

<p><a href="http://www.tks.informatik.uni-frankfurt.de/data/doc/1310.1316.pdf">A note on monadic datalog on unranked trees</a></p>

<p>[3] <a href="http://www.mimuw.edu.pl/~bojan/">Mikołaj Bojańczyk</a></p>

<p><a href="http://www.mimuw.edu.pl/~bojan/upload/confrtaBojanczyk10.pdf">Automata for Data Words and Data Trees.</a></p>

<p>You may also check Georg Gottlob's work</p>

CC BY-SA 3.0
2016-05-14T20:33:26.580Z
2016-05-14T20:33:26.580Z
J.-E. Pin
<p>I would focus your research in the "devops" space until you find a hard problem that could lead to a good theory question. Many configuration files out there need property checkers over tree structures.</p>

<p>Pay particular attention to the Curry/Uncurry in the the third chapter of Drewes lecture notes. I think that is the kernel of an idea to make Tree Automata much more useful.</p>

<p>$B^{A}$ counts functions from an $A$ set to a $B$ set.</p>

<p>$C^{AB} = C^{A}C^{B}$ is an algebraic identity you learn in Jr. High. For functions it means you can pass in a touple of arguments, or pass a touple of functions each taking one argument. Simple, but very useful in refactoring software.</p>

<p>Space is another issue. Succinct representations of trees is very efficient, but rarely used in databases. You easily get 20x speedup by using succinct trees.</p>

<p>Also anything in Celko's book. Worst SQL project I ever had was dealing with a DAG in a database. Lots of open research questions on how to add tree operations to databases.</p>

<p><a href="http://arxiv.org/pdf/math/9405205v1.pdf" rel="nofollow">Blass (1994), Seven Trees in One</a></p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.2549&amp;rep=rep1&amp;type=pdf" rel="nofollow">Fiore (2004), Isomorphisms of Generic Recursive Polynomial Types</a></p>

<p><a href="https://www8.cs.umu.se/kurser/5DV023/VT09/final.pdf" rel="nofollow">Drewes (2009), Lecture Notes on Tree Automata</a></p>

<p><a href="http://rads.stackoverflow.com/amzn/click/B006Y8MKUU" rel="nofollow">Celko 2012, Trees and Hierarchies in SQL for Smarties</a> </p>

<p><a href="http://www-erato.ist.hokudai.ac.jp/alsip2011/ALSIP2011_sadakane.pdf" rel="nofollow">Sadakane 2011, Succinct Trees: Theory and Practice</a></p>

CC BY-SA 3.0
2016-05-11T14:56:39.183Z
2016-05-11T15:19:28.660Z
2016-05-11T15:19:28.660Z
Chad Brewbaker
<p>-Expressivity of particular classes (complexity of deciding if a language is definable in some class, separability, etc).</p>

<p>-Refining the complexity bounds for traditional problems (ex: intersection).</p>

<p>-Tree transducers (almost half of Drewes' book mentioned by Chad deal with them. There is also a transducer paper in FOCS'15).</p>

<p>-Extending the traditional regular tree languages with operations on 'data values' (comparisons).</p>

<p>More generally, I would advise looking at ICALP, STACS, MFCS, LATA, CIAA (and perhaps DLT). There is even a workshop -- TTATT --  dedicated to tree automata.</p>

CC BY-SA 3.0
2016-05-13T09:18:49.510Z
Regarding the connection with databases, this is more 'subjective', but I have a feeling that tree automata are not very popular for processing data in traditional databases. Most applications of tree automata I have witnessed are either for reasoning about data (checking properties) or XML-related query language formalisms.
Joseph Stack
CC BY-SA 3.0
2016-05-13T18:37:49.737Z
Ed Kmett gave an amazing lecture on this recently, https://www.youtube.com/watch?v=uA0Z7_4J7u8 Well worth the watch.
Chad Brewbaker
CC BY-SA 3.0
2016-05-14T14:45:29.110Z
Unless I'm mistaken the lecture about succinct data structures has connections to tree(XML) processing but little (nothing) to do with tree automata.
Joseph Stack
CC BY-SA 3.0
2016-05-15T13:33:29.657Z
Correct. Just data structures. Bahr has a Tree Automata package but I haven't played with it, https://github.com/pa-ba/compdata-automata
Chad Brewbaker
CC BY-SA 3.0
2016-05-13T09:13:48.630Z
2016-05-13T09:20:28.823Z
2016-05-13T09:20:28.823Z
Joseph Stack
<p>What are current research topics connected with tree automata?<br>
I'm particularly interested with connection between automatas, logics and databases.<br>
Kind regards,<br>
XYZ</p>

CC BY-SA 3.0
2016-05-12T15:35:55.030Z
Can downvoters explain whay is wrong with the question or offer suggestions to improve the question?
usul
CC BY-SA 3.0
2016-05-13T19:49:08.157Z
@usul, I have voted to close for it seems too broad and violates [this policy](http://meta.cstheory.stackexchange.com/q/802).
Kaveh
<fl.formal-languages><automata-theory><project-topic>
Current research topics in tree automata
John Malick
# Current research topics in tree automata

(Asked by: username_0 on 2016-05-10)

What are current research topics connected with tree automata?  
I'm particularly interested with connection between automatas, logics and databases.  
Kind regards,  
XYZ

**Tags:** fl.formal-languages, automata-theory, project-topic

> **Comments:**
> **username_1**: Can downvoters explain whay is wrong with the question or offer suggestions to improve the question?  
> **username_2**: @username_1, I have voted to close for it seems too broad and violates [this policy](http://meta.cstheory.stackexchange.com/q/802).  

---

## 3 answers

### Answer by username_3 on 2016-05-14. Score: 5

Here is a short list of authors that work on the connections between tree automata, logic and databases. For each author, I will just give one paper, but many more can be found on the respective web pages of these authors.

[1] [Luc Segoufin](http://www.lsv.ens-cachan.fr/~segoufin/Papers/index.html)

[FO2(+1,<.~) on data trees, data tree automata and branching vector addition systems](http://www.lsv.ens-cachan.fr/~segoufin/Papers/Mypapers/tdafo.pdf)

[2] [Nicole Schweikardt](http://www.tks.informatik.uni-frankfurt.de/publications?lang=en&style=byyear&member=schweika)

[A note on monadic datalog on unranked trees](http://www.tks.informatik.uni-frankfurt.de/data/doc/1310.1316.pdf)

[3] [Mikołaj Bojańczyk](http://www.mimuw.edu.pl/~bojan/)

[Automata for Data Words and Data Trees.](http://www.mimuw.edu.pl/~bojan/upload/confrtaBojanczyk10.pdf)

You may also check Georg Gottlob's work


---

### Answer by username_4 on 2016-05-11. Score: 0

I would focus your research in the "devops" space until you find a hard problem that could lead to a good theory question. Many configuration files out there need property checkers over tree structures.

Pay particular attention to the Curry/Uncurry in the the third chapter of Drewes lecture notes. I think that is the kernel of an idea to make Tree Automata much more useful.

$B^{A}$ counts functions from an $A$ set to a $B$ set.

$C^{AB} = C^{A}C^{B}$ is an algebraic identity you learn in Jr. High. For functions it means you can pass in a touple of arguments, or pass a touple of functions each taking one argument. Simple, but very useful in refactoring software.

Space is another issue. Succinct representations of trees is very efficient, but rarely used in databases. You easily get 20x speedup by using succinct trees.

Also anything in Celko's book. Worst SQL project I ever had was dealing with a DAG in a database. Lots of open research questions on how to add tree operations to databases.

[Blass (1994), Seven Trees in One](http://arxiv.org/pdf/math/9405205v1.pdf)

[Fiore (2004), Isomorphisms of Generic Recursive Polynomial Types](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.2549&rep=rep1&type=pdf)

[Drewes (2009), Lecture Notes on Tree Automata](https://www8.cs.umu.se/kurser/5DV023/VT09/final.pdf)

[Celko 2012, Trees and Hierarchies in SQL for Smarties](http://rads.stackoverflow.com/amzn/click/B006Y8MKUU)

[Sadakane 2011, Succinct Trees: Theory and Practice](http://www-erato.ist.hokudai.ac.jp/alsip2011/ALSIP2011_sadakane.pdf)


---

### Answer by username_5 on 2016-05-13. Score: 0

-Expressivity of particular classes (complexity of deciding if a language is definable in some class, separability, etc).

-Refining the complexity bounds for traditional problems (ex: intersection).

-Tree transducers (almost half of Drewes' book mentioned by Chad deal with them. There is also a transducer paper in FOCS'15).

-Extending the traditional regular tree languages with operations on 'data values' (comparisons).

More generally, I would advise looking at ICALP, STACS, MFCS, LATA, CIAA (and perhaps DLT). There is even a workshop -- TTATT -- dedicated to tree automata.

> **Comments:**
> **username_5**: Regarding the connection with databases, this is more 'subjective', but I have a feeling that tree automata are not very popular for processing data in traditional databases. Most applications of tree automata I have witnessed are either for reasoning about data (checking properties) or XML-related query language formalisms.  
> **username_4**: Ed Kmett gave an amazing lecture on this recently, https://www.youtube.com/watch?v=uA0Z7_4J7u8 Well worth the watch.  
> **username_5**: Unless I'm mistaken the lecture about succinct data structures has connections to tree(XML) processing but little (nothing) to do with tree automata.  
> **username_4**: Correct. Just data structures. Bahr has a Tree Automata package but I haven't played with it, https://github.com/pa-ba/compdata-automata  

---

