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

  • $\begingroup$ Can downvoters explain whay is wrong with the question or offer suggestions to improve the question? $\endgroup$
    – usul
    May 12, 2016 at 15:35
  • $\begingroup$ @usul, I have voted to close for it seems too broad and violates this policy. $\endgroup$
    – Kaveh
    May 13, 2016 at 19:49

3 Answers 3


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

FO2(+1,<.~) on data trees, data tree automata and branching vector addition systems

[2] Nicole Schweikardt

A note on monadic datalog on unranked trees

[3] Mikołaj Bojańczyk

Automata for Data Words and Data Trees.

You may also check Georg Gottlob's work


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

Fiore (2004), Isomorphisms of Generic Recursive Polynomial Types

Drewes (2009), Lecture Notes on Tree Automata

Celko 2012, Trees and Hierarchies in SQL for Smarties

Sadakane 2011, Succinct Trees: Theory and Practice


-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.

  • $\begingroup$ 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. $\endgroup$ May 13, 2016 at 9:18
  • $\begingroup$ Ed Kmett gave an amazing lecture on this recently, youtube.com/watch?v=uA0Z7_4J7u8 Well worth the watch. $\endgroup$ May 13, 2016 at 18:37
  • $\begingroup$ Unless I'm mistaken the lecture about succinct data structures has connections to tree(XML) processing but little (nothing) to do with tree automata. $\endgroup$ May 14, 2016 at 14:45
  • $\begingroup$ Correct. Just data structures. Bahr has a Tree Automata package but I haven't played with it, github.com/pa-ba/compdata-automata $\endgroup$ May 15, 2016 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.