4th Int. Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016)
July 18, 2016 — Seoul, South Korea(co-located with CIAA 2016)
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.
- 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.
- 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:00||Björklund, Drewes, Jonsson: On the N-Best Problem for Hypergraphs|
|10:30-11:00||Weideman, Van Der Merwe, Drewes: The Output Size Problem for String-to-Tree Transducers|
|11:30-12:00||Hashimoto, Nishimura, Seki: Direct Evaluation of Selecting Tree Automata on XML Documents|
|13:30-14:00||Huang, Wen: The Square Trees in the Tribonacci Sequence|
|14:00-14:30||Duparc, Fournier: A Lower Bound for the Length of the Wadge-Wagner Hierarchy|
|14:30-15:00||Filardo, Eisner: Rigid Tree Automata With Isolation|
|15:30-16:00||Yli-Jyrä: Aligned Multistring Languages|
- 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
- Submission deadline: May 16, 2016
- Notification: June 16, 2016
- Early registration: June 19, 2016
- Final version: July 7, 2016
- Workshop: July 18, 2016
- Arnaud Carayol (Université Paris-Est, France)
- Olivier Carton (Université Paris Diderot, France)
- Frank Drewes (Umeå University, Sweden)
- Emmanuel Filiot (Université Libre de Bruxelles, Belgium)
- Zoltán Fülöp (University of Szeged, Hungary)
- Andreas Maletti (Universität Stuttgart, Germany)
- Sebastian Maneth (University of Edinburgh, United Kingdom)
- Wim Martens (Universität Bayreuth, Germany)
- Akimasa Morihata (University of Tokyo, Japan)
- Keisuke Nakano (University of Electro-Communications, Japan)
- Joachim Niehren (Inria Lille, France)
- Damian Niwinski (University of Warsaw, Poland)
- Helmut Seidl (Technische Universität München, Germany)
- Hiroyuki Seki (Nagoya University, Japan)
- Jean-Marc Talbot (Aix-Marseille Université, France)
- Margus Veanes (Microsoft Research, USA)
- Heiko Vogler (Technische Universität Dresden, Germany)
- Bruce Watson (Stellenbosch University, South Africa)
- James Worrell (University of Oxford, United Kingdom)