ictcs 2014

15th Italian Conference on Theoretical Computer Science
the conference of the italian chapter of the EATCS
To be held in Perugia, Italy, September 17-19th 2014
City of Perugia, Italy

Conference Program

Locations

On Wednesday 17 and Friday 19, all activites will be held in the Department of Mathematics and Computer Science (DMI), via Vanvitelli, 1 06123 Perugia.

On Thursday 18, all activites will be held in the Auditorium Santa Cecilia, via Fratti,2 06123 Perugia.

Program

Wednesday >> Thursday >> Friday

September 17th, Wednesday
Time first day
09:00 Welcome + Opening [Aula A3]
09:25 Invited Talk [Aula A3]

Chair: Andrea Formisano (Università di Perugia).

Giuseppe Liotta (Università di Perugia).
Graph Drawing Beyond Planarity: Some results and open problems [slides]

Abstract: Recent technological advances have generated torrents of networked data sets that are often represented and visually analyzed as graphs drawn in the plane. The large size of these data sets poses fascinating challenges to graph drawers both from a practical and from a theoretical point of view: while a considerable portion of the existing graph drawing literature showcases elegant algorithms and sophisticated data structures under the assumption that the input graph is planar, most graphs are in fact non-planar in practice. In this talk I will briefly review recent findings and outline some emerging research directions about the theory of "nearly planar" graphs, i.e. graphs that have drawings where some crossing configurations are forbidden.


10:25 Coffee Break
10:55
Session 1 - [Aula A3]

Chair: Angelo Montanari (University of Udine).

Stefano Mazzanti.
Logspace computability and regressive machines [slides]

Arturo Carpi and Flavio D'Alessandro.
Cerny-like problems for finite sets of words

Luca Bernardinello, Lucia Pomello and Stefania RombolÓ.
Orthomodular Algebraic Lattices Related to Combinatorial Posets [slides]

Marco Bernardo, Flavio Corradini and Luca Tesei.
Timed Process Calculi: From Durationless Actions to Durational Ones

12:35 Lunch Break
14:00
Session 2 - [Aula A3]

Chair: Ugo de'Liguoro (Università di Torino).

Chao Li, Liang Dou and Zongyuan Yang.
A Metamodeling Level Transformation from UML Sequence Diagrams to Coq
Stefano Berardi, Paulo Oliva and Silvia Steila.
Proving termination of programs having transition invariants of height omega

Antonio Bucciarelli, Alberto Carraro, Giordano Favro and Antonino Salibra.
A graph-easy class of mute lambda-terms [slides]

Angelo Montanari, Marco Pazzaglia and Pietro Sala.
Adding two equivalence relations to the interval temporal logic AB [slides]

15:40 Coffee Break
16:10
Session 3 - [Aula A3]

Chair: Raffaella Gentilini (Università di Perugia).

Tomoyuki Yamakami.
Structural Complexity of Multi-Valued Partial Functions Computed by Nondeterministic Pushdown Automata

Giovanna Lavado, Giovanni Pighizzini and Shinnosuke Seki.
Operational State Complexity under Parikh Equivalence [slides]

Alessandra Cherubini and Andrzej Kisielewicz.
Binary 3-compressible automata [slides]

Bruno Guillon and Christian Choffrut.
An algebraic characterization of unary two-way transducers [slides]

Tiziana Calamoneri and Blerina Sinaimeri.
Relating threshold tolerance graphs to other graph classes [slides]




Wednesday >> Thursday >> Friday

September 18th, Thursday

Time

second day in [ @ Auditorium Santa Cecilia - map]

10:00 Opening
10:10 ICTCS Young TCS Research Award and Presentation

Chair: Andrea Pietracaprina (Università Di Padova).

Flavio Chierichetti (Sapienza Università di Roma).
Trace Complexity
[slides]

11:10 Coffee Break
11:40 ICTCS Doctoral Research Awards and Presentations

Chair: Arturo Carpi (Università di Perugia).

Track A: "Algorithms, Automata, Complexity and Game Theory"

Andrea Marino (Università di Milano).
Algorithms for biological graphs: analysis and enumeration
[slides]

Track B: "Logics, Semantics and Programming Theory"

Livio Bioglio (INSERM, UMR-S 1136, iPLESP, Paris).
Type Disciplines for Systems Biology


12:40 Lunch Break

14:00 Session - In memoriam: Bertoni

Chair: Arturo Carpi (Università di Perugia).


In memoriam: Professor Alberto Bertoni (1946-2014).

Christian Choffrut .
"Alberto Bertoni: uno scienziato italiano"

Interverranno: Antonio Restivo, Giancarlo Mauri, Massimiliano Goldwurm, Giovanni Pighizzini, Nicoletta Sabadini

15:40 Coffee Break
16:10 ICTCS Meeting

Chair: Tiziana Calamoneri (Sapienza Università di Roma).

17:50



Wednesday >> Thursday >> Friday

September 19th, Friday
Time third day
09:15 Opening [Aula A3]
09:25 Invited Talk [Aula A3]

Chair: Stefano Bistarelli (Università di Perugia).

Rocco De Nicola (Institute for Advanced Studies Lucca).
A formal approach to autonomic systems programming: The SCEL Language [slides]

Abstract:The autonomic computing paradigm has been proposed to cope with size, complexity and dynamism of contemporary software-intensive systems. The challenge for language designers is to devise appropriate abstractions and linguistic primitives to deal with the large dimension of systems, and with their need to adapt to the changes of the working environment and to the evolving requirements. We propose a set of programming abstractions that permit to represent behaviours, knowledge and aggregations according to specific policies, and to support programming context-awareness, self-awareness and adaptation. Based on these abstractions, we define SCEL (Software Component Ensemble Language), a kernel language whose solid semantic foundations lay also the basis for formal reasoning on autonomic systems behaviour. To show expressiveness and effectiveness of SCEL's design, we present a Java implementation of the proposed abstractions and show how it can be exploited for programming a robotics scenario that is used as a running example for describing features and potentials of our approach.


10:25 Coffee Break
10:55
Session 1 - [Aula A3]

Chair: Tiziana Calamoneri (Sapienza Università di Roma).

Laura Giordano, Valentina Gliozzi, Nicola Olivetti and Gian Luca Pozzato.
Minimal models for Rational Closure in SHIQ

Roberto Mantaci, Paolo Massazza and Jean-Baptiste Yunes.
An Efficient Algorithm for Generating Symmetric Ice Piles [slides]


Giulianella Coletti, Davide Petturiti and Barbara Vantaggi.
Extendibility of Choquet rational preferences on generalized lotteries

Cosimo Vinci and Vittorio Bilò.
On the Stackelberg Fuel Pricing Problem

12:35 Lunch Break
14:00
Session 2 - [Aula A3]

Chair: Eugenio Omodeo (Università di Trieste).

Gianlorenzo D'Angelo, Daniele Diodati, Alfredo Navarra and Cristina M. Pinotti.
Optimal placement of storage nodes in a wireless sensor network [slides]

Soumen Nandi, Nitish Panigrahy, Mohit Agrawal, Sasthi Ghosh and Sandip Das.
Efficient Channel Assignment for Cellular Networks Modeled as Honeycomb Grid


Mattia D'Emidio and Daniele Frigioni.
Engineering Shortest-Path Algorithms for Dynamic Networks

Alberto Bertoni, Massimiliano Goldwurm, Jianyi Lin and Linda Pini.
Size-constrained 2-Clustering in the Plane with Manhattan Distance

15:40 Coffee Break
16:10
Session 3 - [Aula A3]

Chair: Marco Bernardo (Università di Urbino).

Minh Ngo and Fabio Massacci.
Programmable Enforcement Framework of Information Flow Policies

Arman Boyaci, Tinaz Ekim, Mordechai Shalom and Shmuel Zaks.
Graphs of Edge-Intersecting and Non-Splitting Paths [slides]

Alberto Casagrande and Eugenio Omodeo.
Reasoning about Connectivity without Paths [slides]

Stefano Bistarelli, Martine Ceberio, Francesco Santini and Joel A. Henderson.
Abstract Argumentation Frameworks to Promote Fairness and Rationality in Multi-Experts Multi-Criteria Decision Making

Andrea Formisano and Flavio Vella.
On multiple learning schemata in conflict driven solvers