ICTCS 2020
21st Italian Conference on Theoretical Computer Science

Table of Contents

• Preface
  
  

Invited Talks

• Centrality in Network Analysis (text not included)
  Paolo Boldi
• The future of data structures: data-aware and self-designing (text not included)
  Paolo Ferragina

IC-EATCS Best Young Researcher

• Interval-based Problems: Decidability and Complexity (text not included)
  Pietro Sala

IC-EATCS Best PhD thesis

• Connectivity in Directed Graphs: Static and Dynamic (text not included)
  Nikos Parotsidis

IC-EATCS Best master thesis

• Distributed Clustering in General Metrics via Coresets (text not included)
  Alessio Mazzetto

Session 1: Algorithms

• A Substructure based Lower Bound for Eternal Vertex Cover Number. 1-14
  Jasine Babu , Veena Prabhakaran , Arko Sharma
• Structural Parameterizations of Tracking Paths Problem 15-27
  Pratibha Choudhary , Venkatesh Raman
• A Realistic Model for Rescue Operations after an Earthquake (short paper) 28-32
  Tiziana Calamoneri , Federico Corò

Session 2: Computability

• From Decidability to Undecidability by Considering Regular Sets of Instances 33-46
  Petra Wolf
• From Hilbert's 10th Problem to slim, Undecidable Fragments of Set Theory 47-60
  Domenico Cantone , Eugenio Omodeo , Mattia Panettiere
• Compositional Modeling of Biological Systems in CospanSpan(Graph) (short paper) 61-66
  Alessandro Gianola , Stefano Kasangian , Desiree Manicardi , Nicoletta Sabadini , Simone Tini

Session 3: Semantics

• Software Transactional Memory with Interactions 67-80
  Marino Miculan , Marco Peressotti
• A Process Calculus Approach to Correctness Enforcement of PLCs 81-94
  Ruggero Lanotte , Massimo Merro , Andrei Munteanu
• Why Proof-Theory Matters in Specification-Based Testing (short paper) 95-100
  Alberto Momigliano

Session 4: Logic

• Differential Logical Relations Part II: Increments and Derivatives 101-114
  Ugo Dal Lago , Francesco Gavazzo
• Linear Temporal Logics for Structured Context-Free Languages (short paper) 115-121
  Michele Chiari , Davide Bergamaschi , Dino Mandrioli , Matteo Pradella

Session 5: Algorithms

• Breaking Symmetries on Tessellation Graphs via Asynchronous Robots. 122-136
  Serafino Cicerone
• Shape-Preserving Pattern Matching 137-148
  Domenico Cantone , Simone Faro , M. Oguzhan Kulekci
• Quantum Algorithm for Ensemble Learning (short paper) 149-154
  Antonio Macaluso , Stefano Lodi , Claudio Sartori

Session 6: Computability

• Undecidability of Future Timeline-based Planning over Dense Temporal Domains? 155-166
  Laura Bozzelli , Alberto Molinari , Angelo Montanari , Adriano Peron
• A Java visual Simulator of Turing Machines (short paper) 167-123
  Alessandro Burigana , Francesco De Martino , Agostino Dovier
• A Generalized LR(1) Parser or Extended Context-Free Grammars (short paper) 124-130
  Angelo Borsotti , Luca Breveglieri , Stefano Crespi Reghizzi , Angelo Morzenti

Session 7: Complexity

• Finding an Optimal Label-Splitting to Make a Transition System Petri Net Implementable: a Complete Complexity Characterization 131-144
  Ronny Tredup
• On A Class of Constrained Synchronization Problems in NP 145-157
  Stefan Hoffmann

Session 8: Algorithms

• Hierarchical Decompositions of Dihypergraphs 158-171
  Lhouari Nourine , Simon Vilmin
• Complexity of Scorpion Solitaire and applications to Klondike 172-183
  Francesco Arena , Miriam Di Ianni
• Novel Paradigm for the design of Obviously Strategyproof Mechanisms (short paper) 184-189
  Diodato Ferraioli , Adrian Meier , Paolo Penna , Carmine Ventre

Session 9: Complexity

• Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete 190-201
  Giorgio Ausiello , Francesco Cristiano , Paolo Fantozzi , Luigi Laura
• Fair Division is Hard even for Amicable Agents (short paper) 202-207
  Neeldhara Misra , Aditi Sethia

Session 10: Semantics

• Extending Backward Compatibility of Probabilistic Testing via Coherent Resolutions 208-222
  Marco Bernardo
• A General Syntax for Nonrecursive Higher Inductive Types (short paper) 223-229
  Marco Girardi , Roberto Zunino , Marco Benini
• Forward proof-search and Countermodel Construction in Intuitionistic Propositional Logic (short paper) 230-235
  Camillo Fiorentini , Mauro Ferrari

Session 11: Logic

• Equational Logic and Set-Theoretic Models for Multi-Languages 236-249
  Samuele Buro , Roy Crole , Isabella Mastroeni
• Time Series Checking with Fuzzy Interval Temporal Logics 250-262
  Willem Conradie , Dario Della Monica , Emilio Muñoz-Velasco , Guido Sciavicco , Ionel Eduard Stan