ICTCS 2018
Italian Conference on Theoretical Computer Science

Table of Contents

• Preface
  
  

Invited Talks

• Pairwise Compatibility Graphs (invited paper) 1-6
  Rossella Petreschi , Tiziana Calamoneri
• Bisimilarity Via Unique-Solution Techniques (invited paper) 7-11
  Davide Sangiorgi

IC-EATCS Best Young Researcher

• On String Attractors 12-16
  Nicola Prezza

IC-EATCS Best PhD thesis (Mattia Gastaldello award)

• Round and Computational Efficiency of Two-Party Protocols (text not included)
  Michele Ciampi
• Delayed-Input and Non-Malleable Cryptographic Protocols (text not included)
  Luisa Siniscalchi

IC-EATCS Best master thesis

• Flexible Coinduction for Infinite Behaviour 17-23
  Francesco Dagnino

Session 1: Games and Distributed Algorithms

• Hedonic Games with Social Context 24-35
  Gianpiero Monaco , Luca Moscardelli , Yllka Velaj
• On the Effectiveness of Connection Tolls in Fair Cost Facility Location Games 36-47
  Felix C. Rodrigues , Guido Schaefer , Eduardo C. Xavier
• The Price of Anarchy of Affine Congestion Games with Similar Strategies 48-59
  Vittorio Bilò , Cosimo Vinci
• On the Emergent Behavior of the 2-Choices Dynamics 60-64
  Emilio Cruciani , Emanuele Natale , André Nusser , Giacomo Scornavacca

Session 2: Graphs

• Threshold-Bounded Dominating Set with Incentives 65-76
  Gennaro Cordasco , Luisa Gargano , Adele A. Rescigno
• On Mining Distances in Large-Scale Dynamic Graphs 77-81
  Serafino Cicerone , Mattia D’Emidio , Daniele Frigioni
• Time-Based Similar Trajectories on Graphs 82-86
  Shima Moghtasedi
• Graph Theoretic Detection of Inefficiencies in Network Models 87-91
  Ivano Salvo , Daniele Gorla , Pietro Cenciarelli

Session 3: AI, Complexity and Decidability

• On Randomised Strategies in the λ-calculus 92-103
  Ugo Dal Lago , Gabriele Vanoni
• Neural Cryptanalysis of Classical Ciphers 104-115
  Riccardo Focardi , Flaminia L. Luccio
• Timeline-Based Planning over Dense Temporal Domains with Trigger-less Rules is NP-Complete 116-127
  Laura Bozzelli , Alberto Molinari , Angelo Montanari , Adriano Peron , Gerhard Woeginger
• The Fixed Point Problem for General and for Linear SRL Programs is Undecidable 128-139
  Armando B. Matos , Luca Paolini , Luca Roversi

Session 4: Logics and Constraints

• Metric Right Propositional Neighborhood Logic with an Equivalence Relation 140-151
  Pietro Sala
• Graded CTL* over Finite Paths 152-161
  Loredana Sorrentino , Sasha Rubin , Aniello Murano
• Power (Set) ALC 162-173
  Laura Giordano , Alberto Policriti
• Random Models of Very Hard 2QBF and Disjunctive Programs: An Overview (extended abstract; full paper published at IJCAI 2017 ) 174-178
  Giovanni Amendola , Francesco Ricca , Miroslaw Truszczynski

Session 5: Formal Languages and Static Analysis

• Preliminary Results on the Modeling of System Level Diagnosis Problems with Abstract Argumentation 179-190
  Stefano Bistarelli , Antonio Caruso
• On the Generating Functions of Languages Accepted by Deterministic One-reversal Counter Machines 191-202
  Paolo Massazza
• On Some Succinct Representations of Regular Languages (extended abstract; full paper published at CIAA 2018 and NCMA 2017 ) 203-207
  Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero
• Linear-Time Limited Automata (extended abstract; full paper published at DCFS 2018 ) 208-212
  Bruno Guillon , Luca Prigioniero
• A Taxonomy of Program Analyses 213-217
  Gianluca Amato , Maria Chiara Meo , Francesca Scozzari

Session 6: Concurrency

• Deciding Hedged Bisimilarity 218-229
  Alessio Mansutti , Marino Miculan
• On the Reactive Nature of Financial Networks 230-241
  Silvia Crafa , Daniele Varacca
• Relating some Logics for True Concurrency 242-253
  Tommaso Padoan
• Trace Metrics on Nondeterministic Probabilistic Processes (text not included)
  Valentina Castiglioni , Michele Loreti , Simone Tini