FoSSaCS 2021 programme

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]

FoSSaCS
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]

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]

FoSSaCS 

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]

FoSSaCS 

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]

FoSSaCS 

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 -

17h00

FoSSaCS  

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]