ETAPS 2021: 27 March-1 April 2021, Luxembourg, Luxembourg (online)

FoSSaCS 2021 programme

All times are in CEST (GMT+2)

Monday, March 29
10h40 - 12h00 FoSSaCS

Types (Chair: Giulio Manzonetto)

  • Yōji Fukihara and Shin-ya Katsumata. Generalized Bounded Linear Logic and Its Categorical Semantics [doi]
  • Satoshi Kura. General Semantic Construction of Dependent Refinement Type Systems, Categorically [doi]
  • Thorsten Altenkirch, Simon Boulier, Ambrus Kaposi, Christian Sattler and Filippo Sestini. Constructing a universe for the setoid model [doi]
  • Mario Bravetti, Julien Lange and Gianluigi Zavattaro. Fair Refinement for Asynchronous Session Types [doi]
15h20 - 16h40

Automata and category (Chair: Jacques Garrigue)

  • Robin Piedeleu and Fabio Zanasi. A String Diagrammatic Axiomatisation of Finite-State Automata [doi] (EATCS best paper award winner)
  • Gerco van Heerdt, Tobias Kappé, Jurriaan Rot and Alexandra Silva. Learning Pomset Automata [doi]
  • Filippo Bonchi and Alessio Santamaria. Combining Semilattices and Semimodules [doi]
  • Robert Myers, Stefan Milius and Henning Urbat. Nondeterministic Syntactic Complexity [doi]
Tuesday, March 30
10h40 - 12h00 FoSSaCS 

Automata (Chair: Stefan Kiefer)

  • Bartek Klin, Sławomir Lasota and Szymon Toruńczyk. Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages [doi] (EATCS best paper award winner)
  • Alex Dixon, Ranko Lazic, Andrzej Murawski and Igor Walukiewicz. Leafy automata for higher-order concurrency [doi]
  • Sougata Bose, S.N. Krishna, Anca Muscholl and Gabriele Puppis. One-way Resynchronizability of Word Transducers [doi]
  • Orna Kupferman and Salomon Sickert. Certifying Inexpressibility [doi]
14h00 - 15h20


Logics and programming languages (Chair: Nikos Tzevelekos)

  • Christoph Haase and Jakub Różycki. On the Expressiveness of Büchi Arithmetic [doi]
  • Mauricio Ayala-Rincón, Maribel Fernandez, Daniele Nantes-Sobrinho and Deivid Vale. Nominal Equational Problems [doi]
  • Bartosz Bednarczyk and Jakub Michaliszyn. "Most of" leads to undecidability: Failure of adding frequencies to LTL [doi]
  • Paul Wild and Lutz Schröder. A Quantified Coalgebraic van Benthem Theorem [doi]
Wednesday, March 31
10h40 - 12h00


Models and complexity (Chair: Dmitry Chistikov)

  • Silvio Ghilardi, Alessandro Gianola and Deepak Kapur. Interpolation and Amalgamation for Arrays with MaxDiff [doi]
  • Richard Mayr, Sven Schewe, Patrick Totzke and Dominik Wojtczak. Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP [doi]
  • Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier and Thomas Zeume. Work-sensitive Dynamic Complexity of Formal Languages [doi]
  • Philipp Czerner and Stefan Jaax. Runtime Analysis of Broadcast Consensus Protocols [doi]
14h00 - 15h20


Distributed/quantum/stochastic/reactive (Chair: Ugo Dal Lago)

  • Renaud Vilmart. The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford [doi]
  • Paolo Baldan, Richard Eggert, Barbara König and Tommaso Padoan. Fixpoint Theory - Upside Down [doi]
  • A. R. Balasubramanian, Javier Esparza and Mikhail Raskin. Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy [doi]
  • Christian Graulund, Neil Krishnaswami and Dmitrij Szamozvancev. Adjoint Reactive GUI Programming [doi]

15h40 -



Lambda-calculus/logic (Chair: Robert Harper)

  • Patricia Johann, Enrico Ghiorzi and Daniel Jeffries. Parametricity for Primitive Nested Types [doi]
  • Delia Kesner, Loïc Peyrot and Daniel Ventura. The Spirit of Node Replication [doi]
  • Alexander Gheorghiu and Sonia Marin. Focused Proof-search in the Logic of Bunched Implications [doi]
  • Claudia Faggian and Giulio Guerrieri. Factorization in Call-by-Name and Call-by-Value Calculi via Linear Logic [doi]