1,721,059 research outputs found
46th International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2021, August 23-27, 2021, Tallinn, Estonia
No full textThe International Symposium on Mathematical Foundations of Computer Science (MFCS conference series) is a well-established venue for presenting research results in theoretical computer science. The broad scope of the conference encourages interactions between researchers who might not meet at more specialized venues. The first MFCS conference was organized in 1972 in Jabłonna (near Warsaw, Poland). Since then, the conference traditionally moved between the Czech Republic, Slovakia, and Poland. More recently, the conference started traveling to other European countries, including Denmark, the United Kingdom, Germany. The venue for this – the 46th – edition of MFCS, is Tallinn, Estonia.
The program committee of MFCS 2021 accepted 85 papers out of 199 submissions, with the authors of the submitted papers representing over 35 countries. We would like to express our deep gratitude to all the committee members and reviewers for their extensive reports and discussions on the merits of the submissions. Due to the Covid-19 pandemic MFCS 2021 was held as a hybrid event. It featured invited talks by Amina Doumane (ENS Lyon), Martin Grohe (RWTH Aachen University), Joël Ouaknine (Max Planck Institute for Software Systems), Eva Rotenberg (Technical University of Denmark), and Barna Saha (UC Berkeley) on topics that reflected the broad scope of the conference.
MFCS proceedings have been published in the Dagstuhl/LIPIcs series since 2016. We would like to thank Michael Wagner and the LIPIcs team for all their kind help and support. We also warmly thank the organising committee of MFCS, chaired by Pawel Sobocinski, for their hard work in setting up and running the event
String diagram rewrite theory III: Confluence with and without Frobenius
Full text linkIn this paper, we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorially as double-pushout rewriting with interfaces (DPOI) on (labelled) hypergraphs. For standard DPO rewriting without interfaces, confluence for terminating rewriting systems is, in general, undecidable. Nevertheless, we show here that confluence for DPOI, and hence string diagram rewriting, is decidable. We apply this result to give effective procedures for deciding local confluence of symmetric monoidal theories with and without Frobenius structure by critical pair analysis. For the latter, we introduce the new notion of path joinability for critical pairs, which enables finitely many joins of a critical pair to be lifted to an arbitrary context in spite of the strong non-local constraints placed on rewriting in a generic symmetric monoidal theory
When Lawvere Meets Peirce: An Equational Presentation of Boolean Hyperdoctrines
Full text linkFo-bicategories are a categorification of Peirce’s calculus of relations. Notably, their laws provide a proof system for first-order logic that is both purely equational and complete. This paper illustrates a correspondence between fo-bicategories and Lawvere’s hyperdoctrines. To streamline our proof, we introduce peircean bicategories, which offer a more succinct characterization of fo-bicategories
Front Matter, Table of Contents, Preface, List of Authors
No full textFront Matter, Table of Contents, Preface, List of Author
On Doctrines and Cartesian Bicategories
Full text linkWe study the relationship between cartesian bicategories and a specialisation of Lawvere’s hyperdoctrines, namely elementary existential doctrines. Both provide different ways of abstracting the structural properties of logical systems: the former in algebraic terms based on a string diagrammatic calculus, the latter in universal terms using the fundamental notion of adjoint functor. We prove that these two approaches are related by an adjunction, which can be strengthened to an equivalence by imposing further constraints on doctrines
Modular encoding of synchronous and asynchronous interactions using open Petri nets
No full textThe paper investigates the relationships between two well-known approaches to the modelling of concurrent and distributed systems, process calculi and Petri nets. A frame- work for the modular encoding of process calculi into Petri nets is proposed, which is based on a reactive variant of Petri nets. In particular, two exemplary calculi are considered: (asynchronous) CCS and CSP, representing alternative interaction paradigms, namely asynchronous and (broadcast) synchronous communication. The encoding is proved to preserve as well as to reflect the operational semantics. As a consequence, it is well- behaved with respect to the standard behavioural equivalences, a fact that is exploited to perform a “technology transfer” between the two formalisms, in terms of un/decidability results for classical properties such as reachability and deadlock-freedom.
The encoding highlights the expressiveness of the proposed reactive variant of nets, as well as paving the way for a fruitful integration of tools and techniques between the visual formalism of nets and the algebraic framework of processes
Behavioral Metrics via Functor Lifting
Full text linkWe study behavioral metrics in an abstract coalgebraic setting. Given a coalgebra alpha : X -> FX in Set, where the functor F specifies the branching type, we define a framework for deriving pseudometrics on X which measure the behavioral distance of states. A first crucial step is the lifting of the functor F on Set to a functor /F in the category PMet of pseudometric spaces. We present two different approaches which can be viewed as generalizations of the Kantorovich and Wasserstein pseudometrics for probability measures. We show that the pseudometrics provided by the two approaches coincide on several natural examples, but in general they differ. Then a final coalgebra for F in Set can be endowed with a behavioral distance resulting as the smallest solution of a fixed-point equation, yielding the final /F-coalgebra in PMet. The same technique, applied to an arbitrary coalgebra alpha : X -> FX in Set, provides the behavioral distance on X. Under some constraints we can prove that two states are at distance 0 if and only if they are behaviorally equivalent
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
