Program

Venue Sala Lanza, Palermo’s Botanical Garden, Via Lincoln 2, Palermo

Paper Slots Regular papers: 25 min (20 min + 5 min for Q&A); Communications: 15 min (10 min + 5 min for Q&A)

September 13th

08:45-09:00 Opening ICTCS 2023

09:00-10:00 Invited Talk – Finite-state polynomial computation (abstract), Mikołaj Bojańczyk, University of Warsaw, Poland – Chair: M. Goldwurm

10:00-10:30 Coffee Break

10:30-12:25 Session n. 1 – LOGIC AND SEMANTICS – Chair: P. Vocca 

  • 10:30-10:55 The satisfiability problem for Boolean set theory with a rational choice correspondence, Domenico Cantone, Alfio Giarlotta, Pietro Maugeri and Stephen Watson (.pdf)
  • 10:55-11:20 DisTL: A Temporal Logic for the Analysis of the Expected Behaviour of Cyber-Physical Systems, Valentina Castiglioni, Michele Loreti and Simone Tini (.pdf)
  • 11:20 – 11:45 Termination of Rewriting on Reversible Boolean Circuits as a free 3-Category problem, Adriano Barile, Stefano Berardi and Luca Roversi (.pdf)
  • 11:45 – 12:10 On the Weak Continuation of Reverse Bisimilarity vs. Forward Bisimilarity, Andrea Esposito and Marco Bernardo (.pdf)
  • 12:10 – 12:25 Linear realisability over nets and second order quantification, Adrien Ragot, Thomas Seiller and Lorenzo Tortora De Falco (.pdf)

12:25-14:00 Lunch

14:00-15:50 Session n. 2 – GRAPHS – Chair: G. D’Agostino

  • 14:00 – 14:25 L(3, 2, 1)-Labeling of Certain Planar Graphs, Tiziana Calamoneri (.pdf)
  • 14:25 – 14:50 A heuristic for the P-time reconstruction of unique 3-uniform hypergraphs from their degree sequences, Michela Ascolese, Andrea Frosini, Elisa Pergola and Simone Rinaldi (.pdf)
  • 14:50 – 15:05 On graphs that are not star-k-PCGs (extended abstract), Angelo Monti and Blerina Sinaimeri (.pdf)
  • 15:05 -15:20 On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges, Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali and Tommaso Piselli (.pdf)
  • 15:20 – 15.35 (Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs -Extended Abstract-, Tiziana Calamoneri and Federico Corò (.pdf)
  • 15:35 – 15:50 Assembling coherent network topologies using round-trip graphs, Marino Miculan and Matteo Paier (.pdf)

15:50 -16:20 Coffee Break

16:20-17:20 Panel “Dialogo sulla ricerca in informatica teorica in Italia” – Panelists: Angelo Montanari (President of EATCS Italian Chapter) and Fabio Gadducci (President of GRIN – Gruppo di Informatica)

17:20-18:20 Assembly of the IC of the EATCS

September 14th

09:00-10:00 Invited Talk – Graph Pangenomics: a journey from Applications to Theory and back… (abstract), Paola Bonizzoni, University of Milano-Bicocca, Italy – Chair: M. Sciortino

10:00-10:30 Coffee Break

10:30-12:35 Session n. 3 – String algorithms and Combinatorics – Chair: D. Giammarresi

  • 10:30-10:55 Density of Ham- and Lee- non-isometric k-ary Words, Marcella Anselmo, Manuela Flores and Maria Madonia (.pdf)
  • 10:55-11:20 On the number of equal-letter runs of the Bijective Burrows-Wheeler Transform, Elena Biagi, Davide Cenzato, Zsuzsanna Liptak and Giuseppe Romana (.pdf)
  • 11:20 – 11:45 On the k-Hamming and k-Edit Distances, Chiara Epifanio, Luca Forlizzi, Francesca Marzi, Filippo Mignosi, Giuseppe Placidi and Matteo Spezialetti (.pdf)
  • 11:45 – 12:10 Setting the path to the combinatorial characterization of prime double square polyominoes, Michela Ascolese and Andrea Frosini (.pdf)
  • 12:10 – 12:35 Algorithmic View on Circular String Attractors, Giuseppe Romana (.pdf)

12:35-14:00 Lunch

14:00-16:00  Session n. 4 – Languages and computational models – Chair: F. Mignosi

  • 14:00 – 14:25 A linear-size cascade decomposition for Wheeler automata, Giovanna D’Agostino, Luca Geatti, Davide Martincigh and Alberto Policriti (.pdf)
  • 14:25 – 14:50 Large deviation properties for pattern statistics in primitive rational models, Massimiliano Goldwurm and Marco Vignati (.pdf)
  • 14:50 – 15:15 The Quantum Cyclic Rotation Gate, Arianna Pavone and Caterina Viola (.pdf)
  • 15:15 – 15:30 Testing Wheelerness of Regular Languages, Ruben Becker, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Alberto Policriti and Nicola Prezza
  • 15:30 – 15.45 Two-dimensional Dyck words (Extended Abstract), Stefano Crespi Reghizzi, Antonio Restivo and Pierluigi San Pietro (.pdf)
  • 15:45 – 16:00 On the (Im)Possibility of Estimating Various Notions of Differential Privacy (short paper), Daniele Gorla, Louis Jalouzot, Federica Granese, Catuscia Palamidessi and Pablo Piantanida (.pdf)

16:00-16:30 Coffee Break

16:30-18:00  Panel “Automi e Linguaggi Formali nella nascita e nello sviluppo dell’Informatica Teorica in Italia” – Chair: G. Fici

  • 16:30 – 17:30 Seminar – Antonio Restivo, University of Palermo
  • 17:30 – 18:00 Discussion

20:00 Conference Dinner at “Ai Tetti Dining” , Via Vittorio Emanuele 327, Palermo

September 15th

09:00-09:15 EATCS Prize Ceremony  – Chair: A. Montanari

  • Best Young Researcher: Cosimo Vinci 
  • Best PhD Thesis: Gabriele Vanoni 
  • Best Master Thesis: Davide Cozzi

09:15: 10:00 Best young researcher in TCS – Cosimo Vinci – Invited talk – Chair: G. Castiglione

10:00-10:30 Coffee Break

10:30 -10:55 Best PhD Thesis in TCS – Gabriele Vanoni – Invited talk – Chair: G. Castiglione

10:55-12:25 Session n. 5 – Computational Models – Chair: C. Vinci

  • 10:55-11:20 (Not So) Boring Abstract Machines, Ugo Dal Lago and Gabriele Vanoni (.pdf)
  • 11:20-11:45 Finite state verifiers with both private and public coins, M. Utkan Gezer and A. C. Cem Say (.pdf)
  • 11:45 – 12:10 Properties of a Computational Lambda Calculus for Higher-Order Relational Queries, Claudio Sacerdoti Coen and Riccardo Treglia (.pdf)
  • 12:10 – 12:25 Tropical mathematics and the Lambda-Calculus, Davide Barbarossa and Paolo Pistone (.pdf)

12:25-14:00 Lunch

14:00-15:55 Session n. 6 – Formal methods, Complexity and Game Theory – Chair: U. Dal Lago

  • 14:00 – 14:25 When Input Integers are Given in the Unary Numeral Representation, Tomoyuki Yamakami (.pdf)
  • 14:25 – 14:50 Complexity results for some fragments of set theory involving the unordered Cartesian product operator, Domenico Cantone and Pietro Maugeri (.pdf)
  • 14:50 – 15:15 Step-by-step Robustness for Biochemical Networks, Ruggero Lanotte, Desiree Manicardi and Simone Tini (.pdf)
  • 15:15 – 15:40 Utility-Sharing Games: How to Improve the Efficiency with Limited Subsidies, Vittorio Bilo, Lucaleonardo Bove and Cosimo Vinci (.pdf)
  • 15:40 – 15.55 Schelling Games with Continuous Types (Extended Abstract), Davide Bilò, Vittorio Bilò, Michelle Doring, Pascal Lenzner, Louise Molitor and Jonas Schmidt

15:55 – 16:00 Closing ICTCS 2023

16:00-16:30 Coffee Break

16:30 – 17:30 Guided tour of the botanical garden