TTATT 2013

2nd International Workshop on
Trends in Tree Automata and Tree Transducers

October 19, 2013, Hanoi, Vietnam

Colocated with ATVA 2013 (October 15-18)

News: Post-proceedings published as EPTCS 134

Tree Automata and Transducers have a long history within computer science of more than 40 years. Over the last decade, automata theory has experience a huge revival. This is due to its connections to other areas such as bioinformatics, computer networks, databases, linguistics, and verification. A particular demand lies in automata for tree structured data. For this reason the TTATT workshop was initiated in 2012 and its first edition was held in Nagoya (Japan) in conjunction with RTA 2012. This is the second edition of the workshop. As opposed to the first workshop, this second edition has official proceedings in EPTCS. These will be post-proceedings to appear shortly after the workshop.

Topics and Goals

Recently, tree automata and transducers have been combined and applied to various areas in computer science, including rewrite systems, static analysis of software, program transformation, XML document processing, and computational linguistics. This workshop aims to provide an opportunity for researchers from different areas to exchange ideas on the theory and practice of tree automata and tree transducers. The topics of the workshop include, but are not limited to:

Important Dates

Submission:July 16
Notification:August 6
Final version:August 20

Invited Talks

Tomáš Vojnar (Brno University of Technology)
Andreas Reuß (Technical University Munich)


Extended abstracts of at most 6 pages are solicited. The work may be in a preliminary stage, or may be a short version of recently published articles or papers submitted elsewhere. Accepted papers will be made available electronically before the workshop. Original papers will be considered for inclusion in a volume to appear in EPTCS. Authors of such papers will have additional time of one month after the workshop to submit an updated version of their paper to be included in EPTCS. Papers should be formatted according to EasyChair style and will be submitted electronically via an EasyChair submission page.

Go to submission site

Program Committee

Registration Fee

There is no registration fee . TTATT'2013 is open to anyone interested. Participants will be responsible for buying their own coffee and lunch etc; more info on that in the next section.


University Campus
Vietnam National University
141 Xuan Thuy st.
Cau Giay district
See it on google maps
About 20-30min by taxi from the ATVA conference site (ca. 100,000VDN)
This is a map of the precise location. TTATT is in room 212 in the E3 building.


9:00 - 10:00blah Invited Talk (chair: S. Maneth)
Tomáš Vojnar
Fully Automated Shape Analysis Based on Forest Automata
10:00 - 10:30 Coffee
10:30 - 12:00 Session Tree Automata and Transducer Theory (chair: S. Maneth)
Naoki Nishida, Masahiko Sakai, and Yasuhiro Nakano
On Constructing Constrained Tree Automata Recognizing Ground Instances of Constrained Terms Paper Slides
Thomas Hanneforth, Andreas Maletti, and Daniel Quernheim
Random Generation of Nondeterministic Tree Automata Paper Slides
Mathieu Caralp, Emmanuel Filiot, Pierre-Alain Reynier, Frédéric Servais, and Jean-Marc Talbot
Expressiveness of Visibly Pushdown Transducers Paper Slides
12:00 - 14:00 Lunch Break
14:00 - 15:00 Invited Talk (chair: T. Vojnar)
Andreas Reuß
Disequalities in Horn Clause Representations of Finite Tree Automata Abstract Slides
15:00 - 15:30 Coffee
15:30 - 17:00 Session Applications to Querying and Security (chair: E. Filiot)
Kazuki Miyahara, Kenji Hashimoto, and Hiroyuki Seki
Node Query Preservation for Deterministic Linear Top-Down Tree Transducers Paper Slides
Sebastian Maneth and Tom Sebastian
XPath Node Selection over Grammar-Compressed Trees Paper Slides
Ryo Iwase, Yasunori Ishihara, and Toru Fujiwara
Toward Security Verification against Inference Attacks on Data Trees Paper Slides
17:00 Workshop Closing