---------------------------------------------------------------------- IFIP Working Group 1.6 on Term Rewriting Report of the annual meeting: June 27, 2013 (Eindhoven, The Netherlands) Chair: Juergen Giesl Secretary: Peter Schneider-Kamp 23 Participants: Takahito Aoto Mauricio Ayala-Rincon Frederic Blanqui Santiago Escobar (for Salvador Lucas) Juergen Giesl Nao Hirokawa Florent Jacquemard (invited) Delia Kesner Temur Kutsia (invited) Elena Machkasova Georg Moser Naoki Nishida Mitsu Okada Vincent van Oostrom Femke van Raamsdonk Christophe Ringeissen (for Michael Rusinowitch) Kristoffer Rose Manfred Schmidt-Schauss Aaron Stump (invited) Rene Thiemann Yoshihito Toyama Johannes Waldmann Hans Zantema ---------------------------------------------------------------------- Agenda: 1. Presentation by Aaron Stump 2. International School on Rewriting (ISR) 3. Presentation by Florent Jacquemard 4. Presentation by Temur Kutsia 5. Discussion on the Future of RTA 6. Discussion on the List of Open Problems in Rewriting 7. Business Meeting ---------------------------------------------------------------------- 1. Aaron Stump: Automata-Based Parsing by Run Rewriting In this talk, I will present joint work in progress with Nao Hirokawa to develop a new approach to parsing based on rewriting. Reversing the arrows in the productions of a grammar trivially yields a string-rewriting system, which can easily be converted into a term-rewriting system that builds parse trees as it rewrites. But such rewriting systems usually fail to be confluent. We show how to recover confluence by changing the kind of objects the rules rewrite. Instead of rewriting strings, we rewrite runs of an automaton approximating the language of the grammar. A run is an alternating list of characters from the input string and automaton states. Grammars can be converted automatically into run-rewriting rules by an application of a theorem of Book and Otto, on applying monadic string-rewriting systems to finite automata. Confluent run-rewriting has several benefits over traditional parsing methods: ambiguities in the grammar show up as critical pairs, which can be resolved by adding new rewrite rules (instead of precedences or grammar layers); and parallel parsing now becomes very easy (unlike for traditional methods), as it is just parallel rewriting. ---------------------------------------------------------------------- 2. International School on Rewriting (ISR) * Mauricio Ayala-Rincon (for Carlos Castro): Report on ISR 2014 - ISR will take place on August 25-29 in Valparaiso, Chile. - These dates were chosen in order to be close to WoLLIC (which is on September 1-4). - The location is the TU Federico Santa Maria with 10,000 students in engineering. - The climate is sunny with 16-18 degrees Celsius. - The aim is to invite researchers from rewriting as invited speakers to WoLLIC (in this way, they can get financial support). Travel support for invited speakers to ISR is most likely not possible. - From Monday to Thursday, there will be a beginner track (with 18 hours of lectures and 6 hours of exercises) and an advanced track (with 24 hours of lectures). On Friday, there will be an application track for all participants. - The lecturers confirmed so far include Aart Middeldorp, Claude Kirchner, Mauricio Ayala-Rincon, Pierre-Etienne Moreau, Salvador Lucas and (probably) Johannes Waldmann. - A web page is in progress. - There is discussion about whether longer lectures on applications would be possible. * Vincent van Oostrom: Proposal for Change in the Bylaws of ISR - The ISR steering committee (represented by Vincent van Oostrom) proposes a change in the ISR bylaws. Currently, ISR has to take place every second year. The proposal is to permit ISR in consecutive years, if one ISR is in Europe and the other ISR is outside Europe. - Several variants are discussed. - Finally, the audience agrees on the following change of the bylaws: The aim is to have ISR at least every second year. Moreover, the aim is to achieve geographic diversity. * Johannes Waldmann: Proposal for ISR 2015 - Johannes Waldmann (together with Alfons Geser) proposes to organize ISR 2015 in Leipzig, Germany. - The proposed date would be between late July and early September. - The location would be the HTWK with 6,600 students. - Affordable accommodation is available and lunch could be taken at the Mensa (student's canteen). - In Leipzig, there is local expertise on termination, verification, functional programming, and (tree) automata (by Manfred Droste at Leipzig University). - The lectures would give ECTS credits, which is important to attract local students. - The student fee would be around 300 Euros (plus 300 Euros for the accommodation). - Johannes Waldmann has experience in organizing scientific events (e.g., the termination workshop in 2009). - The school would be supported by the HTWK. - The proposal is accepted unanimously by the audience. * Santiago Escobar: Report on ISR 2012 - Santiago Escobar reports on ISR 2012 in Valencia. - Financially, there was a loss of 4,000 Euro, because there were not enough students in the advanced track, while most of the costs came from (travel expenses for) the lecturers of the advanced track. The loss is covered by the organizing research group. - One reason for the few participants could have been the date which overlapped with classes or exams in other European countries. ---------------------------------------------------------------------- 3. Florent Jacquemard: Unranked Tree Rewriting and Effective Closures of Languages We consider rewriting systems for unranked ordered trees, where the number of children of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of trees) instead of just trees. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We consider properties of preservation for classes of unranked tree languages, including hedge automata languages and various context-free extensions. Finally, applications to static type checking for XML transformations and to the verification of read/write access control policies for XML updates will be mentioned. ---------------------------------------------------------------------- 4. Temur Kutsia: Unification, Matching, and Transformation of Unranked Terms We give a brief survey of equation solving methods for unranked terms, including unification and matching with sequence variables, and present a variant of a calculus for conditional transformations of sequences of unranked terms. ---------------------------------------------------------------------- 5. Georg Moser: Discussion on the Future of RTA - There is concern about the way application papers are treated when they are submitted to RTA. Georg Moser points out that 2 out of 6 members of the RTA steering committee stand for application areas. - There is also concern about the publication policy of RTA (LIPIcs instead of Springer proceedings). In 2014, RTA and TLCA will join FLoC as one conference with Springer proceedings. There will also be just one PC with one PC chair (Gilles Dowek). - In the long run, it is not clear whether TLCA would be interested in joining with RTA (they prefer Springer proceedings and they would probably rather join with ICFP). - Compared to RDP in Novi Sad, both RTA and TLCA have fewer participants this time. In Novi Sad, RTA had around 80 participants and TLCA had around 70 participants. This year, RTA has around 60 participants and TLCA has around 50 participants. - In 2015, RTA and TLCA will take place in Warsaw, Poland. It is not yet clear whether they will be combined or just co-located. The PC chair of RTA will be Maribel Fernandez. - Georg Moser points out that more workshops would be helpful for RTA. - Since application papers are often rejected at RTA, papers on applications of term rewriting are rather submitted to other conferences. This may be good for the field of term rewriting as such, but it is not good for RTA. - To increase the number of application papers at RTA, it is proposed to have separate categories for papers on applications and for papers on certification and formalization. Moreover, it is proposed to replace the category for system descriptions by a category for implementation reports. - The call-for-papers should contain clear criteria for the evaluation of papers in these categories. - For implementation reports, one could require that the tools have to be open-source and that the source code has to be published in addition to the paper. - The RTA steering committee will inform Gilles Dowek about these new proposals such that he can formulate the call-for-papers accordingly. ---------------------------------------------------------------------- 6. Hans Zantema: Open Problems in Rewriting - Since 2012, Hans Zantema maintains the list of open problems in rewriting (he took it over from Ralf Treinen). - Ralf Treinen had developed a system for automating tasks concerned with the maintenance of the list, but this is difficult to use for others. - Therefore, in the future, problems should only be submitted as small pdf files. - In the last years, there were no reactions and no new problems submitted. - Several participants of the meeting brought open problems. They will send them to Hans Zantema directly. - It is pointed out that the list is not meant for under-specified problems. - Problem descriptions should not contain URLs, since these often change over time. - Problem descriptions should contain keywords to allow the search for problems. ---------------------------------------------------------------------- 7. Business Meeting - Membership issues were discussed. Before the meeting in 2013, the strict rule was announced that the membership expires for members who are not present at 3 meetings in a row. Therefore, members who do not attend any of the meetings in 2013, 2014, and 2015 will be removed from the WG after the meeting in 2015. - Aaron Stump is invited as a new member to the WG after having been invited to the meetings in 2011 and 2013. - The next IFIP WG 1.6 meeting should take place as a 1-day workshop at FLoC in Vienna, close to RTA. The preference is to have it after RTA. - Since the next meeting will again be for a full day, the goal is to have 4 invitees instead of 3. - Invited talks should focus on ongoing or future directions of the invitee's research (in particular, it would also be nice if they contain open problems). ----------------------------------------------------------------------