Automata that work on tree-structured graphs play an important role in areas such as static analysis of software, program transformation, and XML processing. They are also widely used in natural language process to represent the syntactical structure of sentences. A workshop dedicated to this family of devices was organised as part of the 18th European Joint Conference on Theory and Practice of Software (ETAPS). ETAPS is a forum for academic and industrial researchers active in Software Science, and this year’s edition took place at the Queen Mary University of London.
The MICO project was represented by a paper on the efficient computation of the optimal parse trees with respect to a weighted tree automaton. Key ingredients were regular properties of languages, priority queues, and various pruning strategies. The practical value of the work lies in that it can be used to make certain kinds of machine-translation systems faster and more accurate.
The workshop included both invited talks and paper presentations. In the former category, Christof Löding from RTWH Aachen presented work on the decidability of problems related to transducer-based implementation of logical specifications; Mikolaj Bojanczyk from Warsaw University talked about the advantages of including structural information in the representation of transductions; and Sebastian Maneth from the University of Edinburgh discussed the difficulty of choosing the the right type of transducers for a given computation problem. Among the paper presentations, there were several talks on automata construction and transformation by researchers from e.g. Germany, Algeria, the Netherlands, Hungary, UK, and France.
All in all, the workshop was a nice opportunity to exchange ideas and experiences with researchers from different areas, with tree automata and transducers as a uniting theme.