ICTCS 2021
22nd Italian Conference on Theoretical Computer Science
13-15 September 2021, Bologna, Italy

Presentation Call for papers Important dates Committees Program Registration


Monday, September 13

08:45-09:00OpeningM. Gabbrielli, Head of Department at University of Bologna
09:00-10:00Invited talk: Luca Padovani, Lock freedom of binary sessions under strong fairness assumptions (chair: C. Sacerdoti Coen)
10:15-11:30Session 1: algorithms (chair: N. Galesi)
  • 10:15-10:35 Enhancing Characters Distance Text Sampling by Condensed Alphabets. S. Faro, F. P. Marino and A. Pavone.
  • 10:35-10:55 Proving a conjecture on 8-distance coloring of the infinite hexagonal grid. S. C. Ghosh and S. Koley.
  • 10:55-11:15 An Optimal Monotone Contention Resolution Scheme for Uniform and Partition Matroids R. Santiago and D. Kashaev
  • 11:15-11:30 Cooperative Truck-Drone Scheduling Approach for Last-Mile Deliveries. F. B. Sorbelli, F. Corò, S. K. Das, L. Palazzetti and C. M. Pinotti.
11:45-12:25Session 2.1: formal languages (chair: D. Bresolin)
  • 11:45-12:05 Ordering regular languages: a danger zone D. Martincigh, G. D'Agostino and A. Policriti
  • 12:05-12:25 Extended omega-Regular Languages and Interval Temporal Logic D. Della Monica, A. Montanari and P. Sala
12:25-13:45Lunch Break
13:45-14:00Session 2.2: formal languages (chair: D. Bresolin)
  • 13:45-14:00 Iterated Transduction on Unary Languages M. Kutrib, A. Malcher, C. Mereghetti and B. Palano
14:00-15:10Session 3: logics (chair: L. Roversi)
  • 14:00-14:20 A Unifying Four-State Labelling Semantics for Bridging Abstract Argumentation Frameworks and Belief Revision S. Bistarelli and C. Taticchi.
  • 14:20-14:40 On Counting Propositional Logic and Wagner's Hierarchy M. Antonelli, U. Dal Lago and P. Pistone.
  • 14:40-14:55 Recent results on Strategy Logic with imperfect information B. Maubert
  • 14:55-15:10 Inference From Non-Horn Clauses With Partial Predicates A. Sakharov
15:25-16:25IC-EATCS Meeting

Tuesday, September 14

09:00-10:00EATCS awards
  • Best young researcher: Fabrizio Montecchiani
  • Best PHD thesis: Giulia Bernardini and Francesco Dagnino, ex aequo
  • Best master thesis: Linpeng Zhang, "Some Intensional Versions of Rice's Theorem"
10:15-11:15Session 4: concurrency and decidability (chair: M. Miculan)
  • 10:15-10:35 Decidability of Two Truly Concurrent Equivalences for Finite Bounded Petri Nets A. Cesco and R. Gorrieri
  • 10:35-10:55 A decidable theory treating addition of differentiable real functions G. Buriola, D. Cantone, G. Cincotti, E. Omodeo and . Spartà
  • 10:55-11:15 Two crucial cubic-time components of polynomial-maximal decidable Boolean languages D. Cantone, P. Maugeri and E. Omodeo
11:30-12:20Session 5: combinatorics (chair: I. Salvo)
  • 11:30-11:50 L(2,1)-edge labeling of Infinite Triangular Grid S. Bandopadhyay, S. C. Ghosh and S. Koley
  • 11:50-12:05 On Counting L-Convex Polyominoes V. Dorigatti and P. Massazza
  • 12:05-12:20 Reducing the local alphabet size in tiling systems for picture languages S. Crespi Reghizzi, A. Restivo and P. San Pietro
12:20-14:00Lunch Break
14:00-15:00Invited talk: F. Montecchiani (IC-EATCS Young Researcher Award), "Emerging Research Topics in Graph Drawing", (chair: I. Salvo)
15:15-15:55Session 6: games (chair: D. Ferraioli)
  • 15:15-15:35 Fractional Hedonic Games With a Limited Number of Coalitions F. Li
  • 15:35-15:55 The Obnoxious Facility Location Game with Dichotomous Preferences F. Li, G. Plaxton and V. Sinha
16:00-17:00Round table GRI, topic "La valutazione delle pubblicazioni scientifiche di informatica teorica" G. Delzanno (Vice-Presidente della Giunta del GRIN, Presidene della Commissione Scientifica), A. Dovier (Membro della Giunta del GRIN, già Commissario ASN), A. Montanari (Presidente del Capitolo Italiano dell'EATCS), C. Piazza (Responsabile VQR 2015-2019, UNIUD)

Wednesday, September 15

09:00-10:00Invited talk: Nadia Pisanti, On-line Pattern Matching on Degenerate Texts (chair: T. Calamoneri)
10:15-10:55Session 7: complexity (chair: N. Pisanti)
  • 10:15-10:35 Stability of Special Graph Classes R. Weishaupt and J. Rothe.
  • 10:35-10:55 Nondeterministically Selecting Positive Instances of Context-Free Languages T. Yamakami
11:05-11:40Session 8: computation and deduction (chair: F. Dagnino)
  • 11:05-11:25 Enhanced regular corecursion for data streams D. Ancona, P. Barbieri and E. Zucca
  • 11:25-11:40 A filter model for the state monad U. De'Liguoro and R. Treglia
11:40-13:55Lunch Break
13:55-14:45Session 9: quantum computation and model checking (chair: U. Dal Lago)
  • 13:55-14:15 Fast Classical and Quantum Algorithms for Online k-server Problem on Trees R. Kapralov, K. Khadiev, J. Mokut, Y. Shen and M. Yagafarov
  • 14:15-14:30 Combine Model Checking and Runtime Verification in Multi-Agent Systems A. Ferrando and V. Malvone
  • 14:30-14:45 Towards a Model Checking Tool for Strategy Logic with Simple Goals V. Malvone and S. Stranieri
15:00-15:40Session 10: strings and alignments (chair: E. Merelli)
  • 15:00-15:20 Hardness of MSA with Selective Column Scoring A. Caucchiolo and F. Cicalese
  • 15:20-15:40 Pruned BNDM: extending the bit-parallel suffix automata to large strings S. Faro and S. Scafiti