4th Int. Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016)

July 18, 2016 — Seoul, South Korea

(co-located with CIAA 2016)

ProceedingsProgramAccepted papersTopicsImportant datesProgram committeeVenue

Tree automata and tree transducers have recently received increased attention due to their applications in verification, natural language processing, and XML. The workshop provides an opportunity for researchers and practitioners from the different areas to discuss recent developments and ideas. The workshop also welcomes participants working on string automata and string transducers.


The workshop proceedings are available. Thank you for making TTATT 2016 a success.

Invited speaker

  • We mourn the untimely loss of Zoltán Ésik (University of Szeged, Hungary). His contributions will be remembered. RIP.
  • Kenji Hashimoto (Nagoya University, Japan): Determinacy and Query Preservation of Tree Transducers
    Determinacy and query preservation have been studied as formalizations of information preservation in data transformation in the database community. A transformation (or view) determines a query if there is a function that can map the output of the view to the output of query. Also, a view preserves a query in a designated class if the view determines the query with a function in the same class as the given query. We study the problems of deciding for a given view and query on trees, whether the view determines/preserves the query. In the talk, I present our results concerning the decidability and complexity on determinacy and query preservation for views given by functional linear extended bottom-up tree transducers and queries given by functional bottom-up tree transducers. I also present another result on query preservation when queries are given as n-ary queries based on runs of tree automata.

Accepted papers

  • Johanna Björklund, Frank Drewes and Anna Jonsson
    "On the N-Best Problem for Hypergraphs"
  • Yu Ke Huang and Zhi Ying Wen
    "The Square Trees in the Tribonacci Sequence"
  • Nicolaas Weideman, Brink Van Der Merwe and Frank Drewes
    "The Output Size Problem for String-to-Tree Transducers"
  • Kenji Hashimoto, Suguru Nishimura and Hiroyuki Seki
    "Direct Evaluation of Selecting Tree Automata on XML Documents Compressed with Top Trees"
  • Jacques Duparc and Kevin Fournier
    "A Lower Bound for the Length of the Wadge-Wagner Hierarchy of Regular Tree Languages"
  • Nathaniel Filardo and Jason Eisner
    "Rigid Tree Automata With Isolation"
  • Anssi Yli-Jyrä
    "Aligned Multistring Languages"


Monday, July 18, 2016
09:00-09:30 Hashimoto: Determinacy and Query Preservation of Tree Transducers
10:30-11:00Björklund, Drewes, Jonsson: On the N-Best Problem for Hypergraphs
11:00-11:30Weideman, Van Der Merwe, Drewes: The Output Size Problem for String-to-Tree Transducers
11:30-12:00Hashimoto, Nishimura, Seki: Direct Evaluation of Selecting Tree Automata on XML Documents
12:00-12:30 lunch
13:30-14:00Huang, Wen: The Square Trees in the Tribonacci Sequence
14:00-14:30Duparc, Fournier: A Lower Bound for the Length of the Wadge-Wagner Hierarchy
14:30-15:00Filardo, Eisner: Rigid Tree Automata With Isolation
15:00-15:30 break
15:30-16:00Yli-Jyrä: Aligned Multistring Languages
16:00-16:30Business meeting


  • string and tree automata
  • string and tree transducers
  • extensions of those classical models
  • relations to other formalisms
  • applications of those formalisms

Important dates

  • Submission deadline: May 16, 2016
  • Notification: June 16, 2016
  • Early registration: June 19, 2016
  • Final version: July 7, 2016
  • Workshop: July 18, 2016

Program committee

Contact: maletti@ims.uni-stuttgart.de