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 '16 at 15:35
  • $\begingroup$ @usul, I have voted to close for it seems too broad and violates this policy. $\endgroup$ – Kaveh May 13 '16 at 19:49

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

| cite | improve this answer | |

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

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\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$ – Joseph Stack May 13 '16 at 9:18
  • $\begingroup$ Ed Kmett gave an amazing lecture on this recently, youtube.com/watch?v=uA0Z7_4J7u8 Well worth the watch. $\endgroup$ – Chad Brewbaker May 13 '16 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$ – Joseph Stack May 14 '16 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$ – Chad Brewbaker May 15 '16 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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