Paper published in Information & Computation
The following paper has been published in Information & Computation: Posets With Interfaces as a Model for Concurrency Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternativelytaking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a 2-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures. https://www.lrde.epita.fr/wiki/Publications/fahrenberg.22.iandc
The following paper has been published in Science of Computer Programming: Featured Games Uli Fahrenberg, Axel Legay Feature-based analysis of software product lines and family-based model checking have seen rapid development. Many model checking problems can be reduced to two-player games on finite graphs. A prominent example is mu-calculus model checking, which is generally done by translating to parity games, but also many quantitative model-checking problems can be reduced to (quantitative) games. As part of a program to make game-based model checking available for software product lines, we introduce featured reachability games, featured minimum reachability games, featured discounted games, featured energy games, and featured parity games. We show that all these admit optimal featured strategies, which project to optimal strategies for any product, and how to compute winners and values of such games in a family-based manner. https://www.lrde.epita.fr/wiki/Publications/fahrenberg.22.scp
The following paper has been published in Algebra Universalis: Catoids and Modal Convolution Algebras Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemiański We show how modal quantales arise as convolution algebras 𝑄𝑋 of functions from catoids X, multisemigroups equipped with source and target maps, into modal quantales value or weight quantales Q. In the tradition of boolean algebras with operators we study modal correspondences between algebraic laws in X, Q and 𝑄𝑋. The catoids introduced generalise Schweizer and Sklar’s function systems and single-set categories to structures isomorphic to algebras of ternary relations, as they are used for boolean algebras with operators and substructural logics. Our correspondence results support a generic construction of weighted modal quantales from catoids. This construction is illustrated by many examples. We also relate our results to reasoning with stochastic matrices or probabilistic predicate transformers. The paper is available at https://link.springer.com/article/10.1007/s00012-023-00805-9
participants (1)
-
Uli Fahrenberg