Generating Posets Beyond N
Uli Fahrenberg, Ecole Polytechnique
We introduce iposets - posets with interfaces - equipped with a novel gluing
composition along interfaces and the standard parallel composition. We study
their basic algebraic properties as well as the hierarchy of gluing-parallel
posets generated from singletons by finitary applications of the two
compositions. We show that not only series-parallel posets, but also
interval orders, which seem more interesting for modeling concurrent and
distributed systems, can be generated, but not all posets. Generating posets
is also important for constructing free algebras for concurrent semi-rings
and Kleene algebras that allow compositional reasoning about such systems.
Ulrich (Uli) Fahrenberg holds a PhD in mathematics from Aalborg University, Denmark. He has started his career in computer science as an assistant professor at Aalborg University. Afterwards he has worked as a postdoc at Inria Rennes, France, and since 2016 he is a researcher at the computer science lab at École polytechnique in Palaiseau, France. Uli Fahrenberg works in algebraic topology, concurrency theory, real-time verification, and general quantitative verification. He has published more than 80 papers in computer science and mathematics. He has been a member of numerous program committees, and since 2016 he is a reviewer for AMS Mathematical Reviews.