Generating Posets with Interfaces

In concurrency theory, partially ordered sets (posets) are used to model executions of programs which exhibit both sequentiality and concurrency of events [Win77, Pra86, Vog92]. Series-parallel posets have been investigated due to their algebraic malleability---they are freely generated by serial and parallel composition [Gra81, Gis88]---and form a model of concurrent Kleene algebra [HMSW11]. Interval orders are another class of posets that arise naturally in the semantics of Petri nets [Vog92, JK93, JY17], higher-dimensional automata [vG06a, FJSZ21b], and distributed systems [Lam78]. Series-parallel posets and interval orders are incomparable.

This paper continues work begun in [FJST20] to consolidate series-parallel posets and interval orders. To this end, we have equipped posets with interfaces and extended the serial composition to an operation which glues posets along their interfaces. We have investigated the algebraic structure of the so-defined gluing-parallel posets, which encompass both series-parallel posets and interval orders, in [FJST20, FJSZ21c]. Here we concern ourselves with the combinatorial properties of this class.

An iposet is a poset with interfaces. We generate (and count) all isomorphism classes of iposets and of gluing-parallel iposets on up to 8 points, and of gluing-parallel posets (with interfaces removed) on up to 10 points. In order to do so, we introduce a new subclass of iposets with full interfaces and then generate all isomorphism classes of such ‘‘​Winkowski’’ iposets on up to 8 points and of gluing-parallel Winkowski iposets on up to 9 points.

We have found eleven forbidden substructures for gluing-parallel (i)posets, five on 6 points, one on 8 points, and five other on 10 points. We currently do not know whether there are any forbidden substructures on 11 points or more.

To conduct our exploration we have written software in Julia, using the LightGraphs package. We use a recursive algorithm to generate iposets and Julia’s built-in threading support for parallelization. For isomorphism checking we use a new incomplete invariant which may be computed in linear time yet identifies only relatively few pairs of non-isomorphic (i)posets. We also detail the software and process used to find forbidden substructures. Our software and generated data are freely available; McKay’s similarly freely available data has been of great help in our work.

After a preliminary Section 2 on posets we introduce interfaces in Section 3. Section 4 then reports on our software and Section 5 on forbidden substructures. Before we then can examine Winkowski iposets in Section 7 we need to concern ourselves with discrete iposets in Section 6.

We expose the numbers of non-isomorphic (i)posets in various classes throughout the paper. Table 1 shows the numbers of posets, series-parallel posets, interval orders, the union of the latter two classes, and series-parallel interval orders. Table 2 counts iposets and gluing-parallel (i)posets, Table 4 shows the numbers of some subclasses of discrete iposets, and Table 5 exposes the numbers of Winkowski and gluing-parallel Winkowski iposets. The appendix contains the counts of iposets and gluing-parallel iposets, and of their Winkowski subclasses, split by the numbers of sources and targets.

The main contributions of this paper are, especially when compared to [FJSZ21c], the exposition of the new subclass of Winkowski iposets and the showcase of Julia as a programming language for combinatorial exploration. Further, we believe that our new incomplete isomorphism invariant may be useful also in other contexts, but this remains to be explored.

A poset $(P,\mathord{<})$ is a finite set $P$ equipped with an irreflexive transitive binary relation $<$ (asymmetry of $<$ follows). We use Hasse diagrams to visualize posets, but put greater elements to the right of smaller ones. Posets are equipped with a serial and a parallel composition. They are based on the disjoint union (coproduct) of sets, which we write $X\sqcup Y=\{(x,1)\mid x\in X\}\cup\{(y,2)\mid y\in Y\}$.

A poset is series-parallel (an sp-poset) if it is either empty or can be obtained from the singleton poset by finitely many serial and parallel compositions. It is well known [VTL82, Gra81] that a poset is series-parallel if and only if it does not contain the induced subposet

Further, generation of sp-posets is free: they form the free algebra in the variety of double monoids.

An interval order [Fis70] is a relational structure $(P,<)$ with $<$ irreflexive such that $w<y$ and $x<z$ imply $w<z$ or $x<y$, for all $w,x,y,z\in P$. Transitivity of $<$ follows, and interval orders are therefore posets. Interval orders are precisely those posets that do not contain the induced subposet

Concurrency theory employs both sp-posets and interval orders (and their labeled variants), the former for their algebraic malleability and the latter because the precedence order of events in distributed systems typically is an interval order. We are interested in classes of posets which retain the pleasurable algebraic properties of sp-posets but include interval orders.

Posets $(P_{1},\mathord{<}_{1})$ and $(P_{2},\mathord{<}_{2})$ are isomorphic if there is a bijection $f:P_{1}\to P_{2}$ such that for all $x,y\in P_{1}$, $x<_{1}y\Leftrightarrow f(x)<_{2}f(y)$. It is well-known (and easy to see, given that posets are isomorphic if and only if their Hasse diagrams are) that the poset isomorphism problem is just as hard as graph isomorphism. State of the art is Brinkmann and McKay [BM02] which reports generating isomorphism classes of posets on up to sixteen points.

Also counting posets up to isomorphism is difficult and has been achieved up to sixteen points. On the other hand, both sp-posets and interval orders admit generating functions, so counting these is trivial. Table 1 shows the numbers of posets, sp-posets and interval orders on $n$ points up to isomorphism for $n\leq 11$, as well as the numbers of posets which are sp-or-interval and those which are series-parallel compositions of interval orders.

Let $[n]=\{1,\dotsc,n\}$ for $n\geq 1$ and $[0]=\emptyset$. We write $P^{\min}$ for the set of minimal and $P^{\max}$ for the set of maximal elements of poset $P$.

An iposet as above is denoted $(s,P,t):n\to m$. We let iPos be the set of iposets and define the identity iposets $\textup{{id}}_{n}=(\textup{{id}}_{[n]},[n],\textup{{id}}_{[n]}):n\to n$ for $n\geq 0$. For notational convenience we also define source and target functions $\textit{src},\textit{tgt}:\text{{{iPos}}}\to\mathbbm{N}$ which map $P:n\to m$ to $\textit{src}(P)=n$ and $\textit{tgt}(P)=m$. Any poset $P$ is an iposet with trivial interfaces, $\textit{src}(P)=\textit{tgt}(P)=0$.

Iposets $(s_{1},P_{1},t_{1}):n_{1}\to m_{1}$ and $(s_{2},P_{2},t_{2}):n_{2}\to m_{2}$ are isomorphic if there is a poset isomorphism $f:P_{1}\to P_{2}$ such that $f\circ s_{1}=s_{2}$ and $f\circ t_{1}=t_{2}$; this implies $n_{1}=n_{2}$ and $m_{1}=m_{2}$. The mappings src and tgt are invariant under isomorphisms.

We extend the serial and parallel compositions to iposets. Below, $\phi_{n,m}:[n+m]\to[n]\otimes[m]$ are the isomorphisms given by

and $(P_{1}\sqcup P_{2})_{/t_{1}\equiv s_{2}}$ denotes the quotient of the disjoint union obtained by identifying $(t_{1}(k),1)$ with $(s_{2}(k),2)$ for every $k\in[m]$.

Thus $P_{1}\mathbin{\triangleright}P_{2}$ is defined precisely if $\textit{tgt}(P_{1})=\textit{src}(P_{2})$, and in that case, $\textit{src}(P_{1}\mathbin{\triangleright}P_{2})=\textit{src}(P_{1})$ and $\textit{tgt}(P_{1}\mathbin{\triangleright}P_{2})=\textit{tgt}(P_{2})$. Isomorphism classes of iposets form the morphisms in a category with objects the natural numbers and gluing as composition, or equivalently, a local partial $\ell r$-semigroup [CFJ⁺21, FJSZ21a]. For the parallel composition, $\textit{src}(P_{1}\otimes P_{2})=\textit{src}(P_{1})\otimes\textit{src}(P_{2})$ and $\textit{tgt}(P_{1}\otimes P_{2})=\textit{tgt}(P_{1})\otimes\textit{tgt}(P_{2})$, extending iPos to a partial interchange monoid [CDS20].

A composition $P=P_{1}\mathbin{\triangleright}P_{2}$ or $P=P_{1}\otimes P_{2}$ is trivial if $P=P_{1}$ or $P=P_{2}$ as posets; see also Lemma 3 below. As before, we are interested in iposets and posets which can be obtained from elementary iposets by finitely many (nontrivial) gluing and parallel compositions. Let

be the set of iposets on the singleton poset (the source and target maps are uniquely determined by their type here).

We are interested in generating and counting iposets and gp-iposets up to isomorphism, but also in doing so for gluing-parallel posets: those posets which are gp-as-iposets. The following property defines a class in-between iposets and gp-iposets.

Here $<$ is the (implicit) natural ordering on $[n]$ and $[m]$. It is clear that gluing and parallel compositions of interface consistent iposets are again interface consistent, hence any gp-iposet is interface consistent. Table 2 shows the numbers of posets, sp-posets and gp-posets up to isomorphism, as well as of iposets, interface consistent iposets, and gp-iposets. In the appendix, Tables A.1 to A.6 show the numbers of the three classes of iposets split by the numbers of their sources and targets.

Before we continue with our exploration, we describe the software we have used to generate most numbers in the tables contained in this paper and to explore the structural properties of (i)posets.¹¹1Our software is available at https://github.com/ulifahrenberg/pomsetproject/tree/main/code/20220303/, and the data at https://github.com/ulifahrenberg/pomsetproject/tree/main/data/. This started as a piece of Python code written to confirm or disprove some conjectures, but did not allow us to compute the $\textup{{GP}}(n)$ and $\textup{{GPI}}(n)$ sequences beyond $n=6$. During the BSc internship of the first author of this paper, it was converted to Julia, using the LightGraphs package [FBS⁺21]. This conversion, and major improvements in candidate generation and isomorphism checking (see below), allowed us to generate all gp-posets on $n=9$ points and all gp-iposets on $n=7$ points. Afterwards we managed to compute $\textup{{GP}}(10)$ and $\textup{{GPI}}(8)$ using massively parallelized computations.²²2 We have used several ARM based servers running Linux with processor from High Silicon, model Hi1616, 64 cores, 256 GiB memory, 36 TiB of local disk, provided by the University of Oslo HPC services https://www.uio.no/english/services/it/research/hpc/.

Let $G_{n}$ denote the set of isomorphism classes of gp-iposets on $n$ points for $n\geq 0$ and

for $k,\ell\in\{0,\dotsc,n\}$. That is, $G_{n}(k,\ell)$ is the set of iposets on $n$ points with $k$ points in the starting interface and $\ell$ in the terminating interface. Then $G_{n}=\bigcup_{k,\ell}G_{n}(k,\ell)$, $\textup{{GPI}}(n)=|G_{n}|$, and $\textup{{GP}}(n)=|G_{n}(0,0)|$. Our algorithm for generating $G_{n}$ is recursive and based on the following property, where we have extended $\mathbin{\triangleright}$ and $\otimes$ to sets of iposets the usual way.

Listing 1 shows part of the recursive Julia function which implements the above algorithm. The multi-dimensional array iposets is used for memoization and initiated with the four singletons in $\mathcal{S}$, filled is used to denote which parts of iposets have been computed, and locks is used for locking. The heart of the procedure is the call to pushuptoiso! in line 23 which checks whether iposets already contains an element isomorphic to ip and, if not, pushes it into the array.

Due to the multi-threaded implementation and tight locking, we were able to generate $G_{7}$ in about 4 minutes on a standard laptop. Generating $G_{8}$ took altogether 300 hours in a distributed computation to generate each $G_{8}(k,\ell)$ separately on four different computers: two standard laptops and two Norwegian supercomputers. For generating iposets and analyzing forbidden substructures we have benefited greatly from Brendan McKay’s poset collections.³³3See http://users.cecs.anu.edu.au/~bdm/data/digraphs.html.

Deciding whether iposets are isomorphic is just as difficult as for posets. Brinkmann and McKay [BM02] develop an algorithm to compute canonical representations: mappings $f$ from posets to labeled posets so that $f(P)=f(P^{\prime})$ precisely if $P$ and $P^{\prime}$ are isomorphic. It is clear that if any such algorithm were to run in polynomial time, then poset isomorphism, and thus also graph isomorphism, would be in P.

Canonical representations are complete isomorphism invariants. In our software we are instead using an incomplete isomorphism invariant inspired by bisimulation [Mil89] which can be computed in polynomial time. For digraph $G$ and a point $x$ of $G$, denote by $\textup{{ideg}}(x)$ and $\textup{{odeg}}(x)$ the in- and out-degrees of $x$ in $G$.

Note that this is the same as a standard bisimulation [Mil89] between the transition systems (without initial state) given by enriching digraphs with propositions stating each vertex’s in- and out-degree. Digraphs are said to be in-out-bisimilar if there exists an in-out-bisimulation joining them.

By acyclicity these hashes are well defined, and they may be computed in linear time. A hash isomorphism between posets $P$ and $Q$ is a bijection $f:P\to Q$ such that

for all $x\in P$.

Checking for existence of a hash isomorphism can be done in polynomial time, for example by sorting the hashes.

Listing 2 shows our Julia code for checking whether two posets are isomorphic. The hashes are precomputed, so the function isomorphic takes two posets P and Q as arguments as well as their hashes, pv and qv of type Vprof for ‘‘vertex profile’’. After checking whether there is a hash isomorphism, the hashes are used to constrain possible isomorphisms: only bijections pos_isom which are hash isomorphisms are given to the isomorphism checker isomorphic(P,Q, pos_isom). Table 3 also shows the averages for how many bijections are checked whether they are isomorphisms.

Recall that an induced subposet $(Q,\mathord{<}_{Q})$ of a poset $(P,\mathord{<}_{P})$ is a subset $Q\subseteq P$ with the order $<_{Q}$ the restriction of $<_{P}$ to $Q$. We have shown in [FJSZ21c] that gluing-parallel posets are closed under induced subposets: if $Q$ is an induced subposet of a gp-poset $P$, then also $Q$ is gluing-parallel. This begs the question whether gp-posets admit a finite set of forbidden substructures: a set $\mathcal{F}$ of posets which are incomparable under the induced-subposet relation and such that any poset is gluing-parallel if and only if it contains none of the structures in $\mathcal{F}$ as induced subposets.

Listing 3 shows our implementation of the semi-algorithm to find forbidden substructures. These are collected in the array fsubs and printed out as they are found. The function posetsnotgp returns the posets on $n$ points which are not gluing-parallel, using the function diffuptoiso (not shown) which computes the difference between two (i)poset arrays up to isomorphism. The function nosubs returns all elements of posets which have no induced subposet isomorphic to any element of subs; this latter check is carried out in subgraph which we also do not show here. Using McKay’s files of posets and our own precomputed files of iposets, findforbiddensubs finds the forbidden substructures of Proposition 1 almost immediately. After a few seconds it finds another forbidden substructure on 8 points (see below), and after an hour it verifies that there are no new forbidden substructures on 9 points.

In order to find the forbidden substructures on 10 points in Figure 2, we used another, distributed algorithm which took about two weeks to run. We generated 45 separate files containing the gp-iposets on 10 points obtained from gluing elements of $G_{n}(0,k)$ and $G_{m}(k,0)$ for $n\in\{1,\dotsc,9\}$ and $m\in\{10-n,\dotsc,9\}$ (thus $k=10-n-m$), each reduced up to isomorphism, and one file containing all gp-iposets on 10 points obtained as parallel compositions of smaller gp-iposets. Then we took posets10.txt, removed posets containing one of our forbidden substructures on 6 or 8 points, and then successively filtered it through these 46 files, using diffuptoiso.

Whether there are further forbidden substructures (on 11 points or more), and whether $\mathcal{F}$ is a finite set, remains open.

This section explores the ‘‘fine structure’’ of iposets. An iposet $(s,P,t):n\to m$ is discrete if $P$ is, it is a starter if, additionally, $t:[m]\to P$ is bijective, and a terminator if $s:[n]\to P$ is bijective. Any discrete iposet is the gluing of a starter with a terminator and is gluing-parallel if and only if it is interface consistent. The following is clear.

The next proposition shows numbers of some classes of discrete iposets, see also Table 4.

The third term above can be simplified by

using a version of Vandermonde’s identity; we are not aware of any such simplification for the last term.

A discrete iposet $(s,P,t):n\to n$ is a symmetry if it is both a starter and a terminator, that is, $s$ and $t$ are both bijective. All points of $P$ are in the starting and terminating interfaces, but the permutation $t^{-1}\circ s:[n]\to[n]$ is not necessarily an identity. It is clear that there are precisely $n!$ non-isomorphic symmetries on $n$ points, and that any discrete iposet $P$ may be written $P\cong\sigma\mathbin{\triangleright}Q\cong R\mathbin{\triangleright}\tau$ for symmetries $\sigma$, $\tau$ and $Q$ and $R$ interface consistent.

We finish this section by a special case of the interchange property relating parallel and gluing compositions, cf. Remark 1.