----------------------------------------------------------------------
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).
----------------------------------------------------------------------