Copyright c 2014 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. Re-publication of material from this volume requires permission by the copyright owners. fstefano.bistarelli j andrea.formisanog@unipg.it This volume contains the papers presented at ICTCS 2014, the 15th Italian Conference on
ICTCS is the traditional meeting of the Italian Chapter of the European Association for Theoretical Computer Science (EATCS). The purpose of these meetings is fostering the cross-fertilisation of ideas stemming from different areas of theoretical computer science. Hence, they represent occasions for exchanging ideas and for sharing experiences between researchers. They also provide the ideal environment where junior researchers and PhD students can meet senior researchers.
The Italian Chapter of the EATCS was founded in 1972 and previous meetings took place in Pisa (1972), Mantova (1974 and 1989), L’Aquila (1992), Ravello (1995), Prato (1998), Torino (2001), Bertinoro (2003), Pontignano (2005), Roma (2007), Cremona (2009), Camerino (2010), Varese (2012) and Palermo (2013). As usual, ICTCS 2014 was open to researchers from outside Italy, who are always welcome to submit papers and attend these periodical events.
In this edition, there were 30 submitted contributions. Each of them was reviewed by at least 3 Program Committee members. The Committee decided to accept 26 papers covering several areas of theoretical computer science. The participants came from institutions of various countries, namely, China, Finland, France, India, Israel, Italy, Japan, Poland, Tunisia, Turkey, UK, and USA. The program included two invited speakers, Rocco De Nicola (IMT, Lucca) and Giuseppe Liotta (Universita` di Perugia) and a presentation given by Flavio Chierichetti (Sapienza Universita` di Roma), the recipient of the Young Researcher in Theoretical Computer Science Award 2014, conferred this year by the Italian Chapter. Furthermore, Livio Bioglio (INSERM, Paris) and Andrea Marino (Universita` di Milano), the two recipients of the Best PhD Thesis in Theoretical Computer Science Award 2014, assigned by the Italian Chapter, gave two talks illustrating their recent research. The program of ICTCS 2014 included a special session devoted to the memory of Alberto Bertoni, which was one of the founders of the Italian Chapter and recently passed away. This session, was organized by Arturo Carpi and Alessandra Cherubini. We would like to express our gratitude to the invited speakers, to the recipients of the three Awards, and to all authors and participants. We also wish to thank the members of the Program Committee and all additional anonymous reviewers for their hard work. A special mention is due to the colleagues of the Organizing Committee for the invaluable contribution they gave in organizing ICTCS 2014.
We would like to give special thanks to the various sponsors that supported the event: EATCS, Universita` di Perugia, Dipartimento di Matematica e Informatica, Regione Umbria, Provincia di Perugia, Comune di Perugia, Fondazione Perugiassisi 2019, Fondazione Cassa di Risparmio di Perugia, INdAM-GNCS, IOS Press. Finally, we mention EasyChair and CEUR-WS.org that helped us in organizing the conference and producing the proceedings.
A formal approach to autonomic systems programming: the SCEL language
Rocco De Nicola
Giuseppe Liotta
Flavio Chierichetti
Livio Bioglio
Andrea Marino
Marco Bernardo, Flavio Corradini, Luca Tesei
Alberto Bertoni, Massimiliano Goldwurm, Jianyi Lin, Linda Pini
Arman Boyacı, Tınaz Ekim, Mordechai Shalom, Shmuel Zaks
Antonio Bucciarelli, Alberto Carraro, Giordano Favro, Antonino Salibra 1 3 9 11 15 21 33 45 59
Tiziana Calamoneri, Blerina Sinaimeri
Arturo Carpi, Flavio D’Alessandro
Alberto Casagrande, Eugenio Omodeo
Alessandra Cherubini, Andrzej Kisielewicz
Giulianella Coletti, Davide Petturiti, Barbara Vantaggi
Andrea Formisano, Flavio Vella A metamodeling level transformation from UML sequence diagrams to Coq
Chao Li, Liang Dou, Zongyuan Yang
Roberto Mantaci, Paolo Massazza, Jean-Baptiste Yune`s
Angelo Montanari, Marco Pazzaglia, Pietro Sala Efficient channel assignment for cellular networks modeled as honeycomb grid
Soumen Nandi, Nitish Panigrahy, Mohit Agrawal, Sasthi C. Ghosh, Sandip Das
Minh Ngo, Fabio Massacci
Cosimo Vinci, Vittorio Bilo`
Tomoyuki Yamakami 73 81 93 109 121 133 147 159 171 183 197 213 225
Proving termination of programs having transition invariants of height !
Stefano Berardi, Paulo Oliva, Silvia Steila
Mattia D’Emidio, Daniele Frigioni
Christian Choffrut, Bruno Guillon
Stefano Mazzanti
Author Index