ICTCS 2023
Italian Conference on Theoretical Computer Science 2023

Table of Contents

• Preface
  

Invited Talks

• Finite-State Polynomial Computation (text not included)
  Mikołaj Bojańczyk
• Graph Pangenomics: a Journey from Applications to Theory and back… (text not included)
  Paola Bonizzoni

IC-EATCS Best Young Researcher

• Recent Advances in Adaptive Stochastic Optimization (text not included)
  Cosimo Vinci

IC-EATCS Best PhD Thesis

• Space and Time Models for the λ-Calculus (text not included)
  Gabriele Vanoni

IC-EATCS Best Master Thesis

• Algoritmi per la Trasformata di Burrows-Wheeler Posizionale con Compressione Run-Length (text not included)
  Davide Cozzi

Session 1: Logic and Semantics

• The Satisfiability Problem for Boolean Set Theory with a Rational Choice Correspondence 1-14
  Domenico Cantone, Alfio Giarlotta, Pietro Maugeri, Stephen Watson
• DisTL: A Temporal Logic for the Analysis of the Expected Behaviour of Cyber-Physical Systems 15-30
  Valentina Castiglioni, Michele Loreti, Simone Tini
• Termination of Rewriting on Reversible Boolean Circuits as a Free 3-Category Problem 31-43
  Adriano Barile, Stefano Berardi, Luca Roversi
• On the Weak Continuation of Reverse Bisimilarity vs. Forward Bisimilarity 44-58
  Marco Bernardo, Andrea Esposito
• Linear Realisability Over Nets and Second Order Quantification (short paper) 59-64
  Adrien Ragot, Thomas Seiller, Lorenzo Tortora De Falco

Session 2: Graphs

• L(3, 2, 1)-Labeling of Certain Planar Graphs 65-76
  Tiziana Calamoneri
• A Heuristic for the P-time Reconstruction of Unique 3-Uniform Hypergraphs from their Degree Sequences 77-91
  Michela Ascolese, Andrea Frosini, Elisa Pergola, Simone Rinaldi
• On Graphs that are not Star-k-PCGs (short paper) 92-97
  Angelo Monti, Blerina Sinaimeri
• On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges (short paper) 98-103
  Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli
• (Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs (short paper) 104-109
  Tiziana Calamoneri, Federico Corò
• Assembling Coherent Network Topologies Using Round-Trip Graphs (short paper) 110-115
  Marino Miculan, Matteo Paier

Session 3: String algorithms and Combinatorics

• Density of Ham- and Lee- non-isometric k-ary Words 116-128
  Marcella Anselmo, Manuela Flores, Maria Madonia
• On the Number of Equal-Letter Runs of the Bijective Burrows-Wheeler Transform 129-142
  Elena Biagi, Davide Cenzato, Zsuzsanna Liptak, Giuseppe Romana
• On the k-Hamming and k-Edit Distances 143-156
  Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi, Matteo Spezialetti
• Setting the Path to the Combinatorial Characterization of Prime Double Square Polyominoes 157-168
  Michela Ascolese, Andrea Frosini
• Algorithmic View on Circular String Attractors 169-180
  Giuseppe Romana

Session 4: Languages and computational models

• A Linear-size Cascade Decomposition for Wheeler Automata 181-191
  Giovanna D’Agostino, Luca Geatti, Davide Martincigh, Alberto Policriti
• Large Deviation Properties for Pattern Statistics in Primitive Rational Models 192-205
  Massimiliano Goldwurm, Marco Vignati
• The Quantum Cyclic Rotation Gate 206-218
  Arianna Pavone, Caterina Viola
• Testing Wheelerness of Regular Languages (short paper) (text not included)
  Ruben Becker, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Alberto Policriti, Nicola Prezza
• Two-Dimensional Dyck Words (short paper) (text not included)
  Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro
• On the (Im)Possibility of Estimating Various Notions of Differential Privacy (short paper) 219-224
  Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi, Pablo Piantanida

Session 5: Computational models

• (Not So) Boring Abstract Machines 225-240
  Ugo Dal Lago, Gabriele Vanoni
• Finite State Verifiers with Both Private and Public Coins 241-253
  M. Utkan Gezer, A. C. Cem Say
• Properties of a Computational Lambda Calculus for Higher-Order Relational Queries 254-267
  Claudio Sacerdoti Coen, Riccardo Treglia
• Tropical Mathematics and the Lambda-Calculus (short paper) (text not included)
  Davide Barbarossa, Paolo Pistone

Session 6: Formal methods, Complexity and Game Theory

• When Input Integers are Given in the Unary Numeral Representation 268-282
  Tomoyuki Yamakami
• Complexity Results for Some Fragments of Set Theory Involving the Unordered Cartesian Product Operator 283-298
  Domenico Cantone, Pietro Maugeri
• Step-by-step Robustness for Biochemical Networks 299-313
  Ruggero Lanotte, Desiree Manicardi, Simone Tini
• Utility-Sharing Games: How to Improve the Efficiency with Limited Subsidies 314-327
  Vittorio Bilò, Lucaleonardo Bove, Cosimo Vinci
• Schelling Games with Continuous Types (short paper) 328-333
  Davide Bilò, Vittorio Bilò, Michelle Doring, Pascal Lenzner, Louise Molitor, Jonas Schmidt