ICTCS 2025
Italian Conference on Theoretical Computer Science 2025

Table of Contents

• Preface
  Summary: 29 papers were submitted for peer-review to this conference. Out of these, 26 papers were accepted, 13 as regular papers and 13 as communications. 1–2

Invited Talks

• Priced and Energy Timed Automata (not published in this volume)
  Kim G. Larsen
• Theoretical Computer Science and Explanations that Transform the World (not published in this volume)
  Giuseppe Persiano

IC-EATCS Best Young Researcher

• Single-dimensional contract design (not published in this volume)
  Andrea Celli

IC-EATCS Best PhD Thesis

• On Data Structures for Texts and Permutations (not published in this volume)
  Francesco Masillo

IC-EATCS Best Master Thesis

• On the Complexity and Approximability of Bounded Access Lempel Ziv Compression (not published in this volume)
  Francesca Ugazio

Session 1: Graphs, Games, Algorithms and Complexity

• Watching Systems with Bounded Probes 3–15
  Gennaro Cordasco , Luisa Gargano , Adele Rescigno
• Experimental Evaluation of Blum’s Maximum Matching Algorithm in General Graphs 16–27
  Ahmad Dandeh , Tamas Lukovszki
• The Black-and-White Coloring Problem on Tree-Structured Hypergraphs 28–37
  Shira Zucker
• Generating Constrained Lattice Paths in a Grid Related to Counting Cycles 38–48
  Hareshkumar Jadav , Mihir Patel , Samip Shah , Ranveer Singh , Harsh Talati
• Finite Guarding of Weakly Visible Segments via LineAspect Ratio in Simple Polygons 49–59
  Arash Vaezi
• Multipacking in Hypercubes (short paper) 60–66
  Deepak Rajendraprasad , Varun Sani , Birenjith Sasidharan , Jishnu Sen
• Hyperset Individualisation Algorithms 67–80
  Simone Boscaratto , Francesco Nascimben , Alberto Policriti

Session 2: Graphs, Games, Algorithms and Complexity (Communications)

• Communications: Duality, chi-Boundedness and Order Density of Homomorphisms of Ordered Graphs 81–86
  Michal Čertík , Jaroslav Nešetřil
• Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences 87–93
  Michele Flammini , Maria Fomenko , Giovanna Varricchio
• OB-GRAG: LLM Assisted Graph Creation and Querying via Domain Specific Ontology 94–100
  Paulis Barzdins , Normunds Gruzitis

Session 3: Logic and Formal Methods

• A Temporal, Deontic, Conditional Logic with Typicality: a Preliminary Report 101–112
  Mario Alviano , Laura Giordano , Daniele Theseider Dupre
• Recurrent Neural Networks for Guiding Proof Search in Propositional Logic 113–126
  Gianluca Amato , Nicola Balestra , Marco Maggesi , Maurizio Parton

Session 4: Logic and Formal Methods (Communications)

• Displayed Universal Algebra in UniMath: Basic Definitions and Results 127–133
  Gianluca Amato , Matteo Calosci , Marco Maggesi , Cosimo Perini Brogi
• Realizability Models and Complexity Classes 134–139
  Eugenio Moggi
• Linearization and Model Reduction in Zonotope-Based Reachability Analysis of Nonlinear ODEs 140–146
  Michele Boreale , Luisa Collodi
• Towards Algebraic Analysis of Probabilistic Programs 147–153
  Luisa Collodi , Michele Boreale , Alessandro Pompa Di Gregorio
• A Modular Proof of Semantic Completeness for Normal Systems beyond the Modal Cube, Formalised in HOLMS 154–162
  Antonella Bilotta , Marco Maggesi , Cosimo Perini Brogi
• An Agda Implementation of the Modal Logic S4.2: First Investigations 163–168
  Riccardo Borsetto , Margherita Zorzi

Session 5: Automata, Languages and Computation

• Omission Failures in Choreographic Programming 169–184
  Eva Graversen , Fabrizio Montesi , Marco Peressotti
• Attribute-Based Precedence Relations for Free-Form Grammars 185–197
  Angelo Borsotti , Stefano Crespi Reghizzi , Matteo Pradella
• Wheelerness and Complementation 198–210
  Giuseppa Castiglione , Giovanna D’Agostino , Alberto Policriti , Antonio Restivo , Brian Riccardi
• On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle 211–223
  Davide Ancona , Angelo Ferrando

Session 6: Automata, Languages and Computation (Communications)

• Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity, and Reversibility 224–229
  Firas Ben Ramdhane , Alberto Dennunzio , Luciano Margara , Giuliamaria Menara

Papers Presented Only

• An Automaton-based Characterisation of First Order Logic over Infinite Trees (not published in this volume)
  Massimo Benerecetti , Dario Della Monica , Angelo Matteo , Fabio Mogavero , Gabriele Puppis
• On the Computation of Winning Strategies in Timed Games with Dense Real-Time Constraints (not published in this volume)
  Andrea Manini , Matteo Rossi , Pierluigi San Pietro
• Advances in Fair Allocation of Indivisible Goods under Non-monotone Valuations (not published in this volume)
  Vittorio Bilò , Martin Loebl , Cosimo Vinci