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

July 18, 2016 — Seoul, South Korea

(co-located with CIAA 2016)

Accepted papersProgramTopicsFinal versionImportant 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.


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"

Program

Monday, July 18, 2016
09:00-09:30 Hashimoto: Determinacy and Query Preservation of Tree Transducers
09:30-10:00
10:00-10:30break
10:30-11:00Björklund, Drewes, Jonsson: On the N-Best Problem for Hypergraphs
10:30-11:00Weideman, 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
12:30-13:00
13:00-13:30
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
16:30-17:00

Topics

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

Final versions of submissions

The final version of an accepted contribution should be formatted according to the usual LNCS article style and should not exceed 6 pages (excluding the references). Any appendix submitted for review should be removed. We require no copyright transfer, but expect that authors agree to the electronic dissemination of the final version via the workshop homepage.

The final version should be uploaded in source and as a reference PDF electronically via EasyChair to

https://easychair.org/conferences/?conf=ttatt2016

We expect that each contribution is presented by one author. TTATT registration is included in the CIAA registration, so please register here.


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