{'fraction_non_alphanumeric': 0.05266037477773219, 'fraction_numerical': 0.011899876897825195, 'mean_word_length': 3.55119825708061, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Simplicial models for concurrency

We model both concurrent programs and the possible executions from one state to another in a concurrent program using simplices. The latter are calculated using necklaces of simplices in the former.


Introduction
We develop a discrete model for processes that is useful in the concurrent setting. It is based on the traditional model given by graphs. In this model, vertices of the graph represent states and edges represent transitions. The edges may be directed or undirected. A more sophisticated model appropriate for concurrency is given by simplicial complexes. For example, the following triangle, For three processes, the analogous model is a cube that is subdivided into six tetrahedra.
The combinatorial versions of simplicial complexes are simplicial sets. These consist of sets of abstract vertices, edges, triangles, tetrahedra, and higher dimensional simplices. For a simplicial set, the corresponding simplicial complex is its geometric realization. Our figures will consist of simplicial complexes, but we intend these to represent the corresponding simplicial set.
Using Dijkstra's formalism for concurrent programs [4], we give an explicit construction of a simplicial model for a concurrent program using filtered simplicial sets. The vertices of this simplicial model give states of the concurrent program. The executions between states are modeled by paths between vertices in the simplicial model. There is a growing literature of related models, which are mostly continuous. For some examples, see [7,8,2,3,12,11,6].
In concurrency, understanding the possible execution paths is one of the main sources of difficulty. In a simplicial set, the equivalence classes of paths can be described by a category called the fundamental category [10] or the path category [9]. In this category the objects are the vertices of the simplicial set, and between objects there is a set of equivalence classes of paths.
We consider a related but more sophisticated construction in which the objects are vertices of the simplicial set, but the executions from one state to another are described by a simplicial set. That is, our model is a simplicial category (i.e., a category enriched over simplicial sets). This construction can detect higher order structure that is invisible to the path category. To calculate it, we consider necklaces of simplices in our simplicial set models. In a related paper [14], Raussen constructs simplicial models of execution spaces for continuous models.
Outline of the paper: In Section 2, we discuss simplicial sets, filtered simplicial sets, necklaces, simplicial categories, and some of the other necessary mathematical machinery. In Section 3, we apply these constructions to construct simplicial models of concurrent systems and also of their execution spaces. Our examples include an example in which the structure of the executions is not detected by the path category, but is captured by our methods. In Section 4, we discuss a suitable model structure for this setting and we remark that one may try to apply these methods using cubical sets instead of simplicial sets.

Mathematical machinery
2.1. Simplicial sets. A simplicial set, X, consists of a sequence of sets, {X 0 , X 1 , X 2 , . . .} together with face maps d i : X k → X k−1 for 0 ≤ i ≤ k and degeneracy maps s i : X k → X k+1 for 0 ≤ i ≤ k satisfying the following simplicial identities.
The elements of X k are called k-simplices. The 0-simplices are called vertices and the 1-simplices are called edges. A morphism of simplicial sets, f : X → Y consists of a sequence of functions f k : X k → Y k that commute with the face and degeneracy maps. The geometric realization of a simplicial set is a simplicial complex.
For example, for each n there is a simplicial set ∆ n whose geometric realization is the standard geometric n-simplex. ∆ 0 is the simplicial set with one element in each X k and all of the face and degeneracy maps given by the identity. The k-simplices that are not in the image of a degeneracy map are called nondegenerate. Thus, ∆ 0 has only one nondegenerate simplex, which is a 0-simplex. The only nondegenerate simplices in ∆ 1 are a, b ∈ ∆ 1 0 and e ∈ ∆ 1 1 where d 0 (e) = b and d 1 (e) = a. Note that the initial vertex is d 1 (e) and the final vertex is d 0 (e).
Simplicial sets and their morphisms form a category. Geometric realization is a functor from this category to the category of topological spaces. A more elegant but more sophisticated way of defining simplicial sets is as contravariant functors from the category of finite ordinals and order preserving maps to the category of sets.

Filtered simplicial sets.
A sub-simplicial set A ⊆ X is a sequence of subsets A i ⊆ X i that are closed under the restrictions of the face and degeneracy maps. A filtration on a simplicial set X is an increasing sequence For simplicial sets X and Y , their product X × Y is given by (X × Y ) n = X n × Y n with face and degeneracy maps d i = d i × d i and s i = s i × s i . Note that the nondegenerate simplices of X × Y are not necessarily products of nondegenerate simplices of X and Y . A standard example is ∆ 1 × ∆ 1 which is a triangulation of the square. For filtered simplicial sets X and Y , X × Y has an induced filtration where (X × Y ) (k) is the union of the sub-simplicial sets Similarly, products of m-filtered simplicial sets have an induced m-filtration.

2.3.
The path category of a simplicial set. Given a simplicial set X, we can define the path category, P (X), as follows. For a thorough exposition see [9]. The path category is also called the fundamental category.
Definition 2.1. Let the path category P (X) of the simplicial set X be the category whose objects are the vertices of X and whose morphisms are concatenations of edges in X modulo the equivalence relation generated by the following relations s 0 (a) ∼ Id a , for all a ∈ X 0 , and 2.4. The simplicial category of an ordered simplicial set. Since the path category only depends on the k-simplices for k ≤ 2, it does not detect higher order structure.
For this purpose, we consider the following construction of a category enriched over simplicial sets. In such a category, between two objects, instead of set of morphisms, we have a simplicial set of morphisms. For brevity, this is also called a simplicially enriched category, or a simplicial category. For a thorough exposition of the simplicial category of a simplicial set see [5].
A necklace is a simplicial set, T , of the form where the final vertex of ∆ n i is glued to the initial vertex of ∆ n i+1 . The simplicial set ∆ n i is called a bead of T . Vertices of T that are initial or final vertices of any of the beads are called joints of T . The set of joints of T is denoted J T . Call the initial vertex of ∆ n 1 the initial vertex of T and the final vertex of ∆ n k the final vertex of T .
A simplicial set X is ordered if for each a ∈ X 0 , P (X)(a, a) consists of only the identity morphism, and no two simplices have the same set of vertices. The simplicial sets arising in our models in Section 3 will all be ordered. One can define the simplicial category for a simplicial set without this condition, but for ordered simplicial sets we have the following nice explicit construction from [5].
Definition 2.2. For an ordered simplicial set X, let C(X) be the category enriched in simplicial sets whose objects are vertices in X, and such that for vertices a and b, C(X) (a, b) is the simplicial set given as follows. Let C(X)(a, b) n be the set of triples (T, f, − → T ) where T is a necklace, f : T → X is a injective map of simplicial sets such that the images of the initial and final vertices of T are a and b respectively, and − → T is a flanked flag of length n. The degeneracy maps, s i , for 0 ≤ i ≤ n are given by The face maps, d i , for 0 < i < n are given by For i = 0, let T ′ the unique subnecklace of T whose set of joints is T 1 and whose set of vertices is T n . Similarly, for i = n, let T ′′ be the unique subnecklace of T whose set of joints is T 0 , and whose set of vertices is T n−1 . Then d 0 ((T, f, T 0 ⊆ · · · ⊆ T n )) = (T ′ , f, T 1 ⊆ · · · ⊆ T n ), and d n ((T, f, T 0 ⊆ · · · ⊆ T n )) = (T ′′ , f, T 0 ⊆ · · · ⊆ T n−1 ).

Concurrency
We use Dijkstra's abstraction of concurrent programming in which semaphores are used to control access by multiple processes to a common resource [4]. More precisely, a resource that may be used by only k processes at once is controlled by a k-semaphore. This is simply a nonnegative counter which starts at k. When a process wants to use the resource it tries to decrement the counter and when it is finished using the resource it increments the counter. 1-semaphores are also called binary semaphores.
A concurrent program can be abstractly written as a sequence of operations on semaphores. Following Dijkstra's original notation, for a semaphore a, let P a denote decrementing a and let V a denote incrementing a. We consider programs that are finite sequences of these operations. Abstractly a program for one process is given by where O j is either operator P or V and a i j is one of the semaphores. Let s 0 be the initial state of the program P and let s j be state of the program after the operation O j a i j .

Simplicial models of concurrent programs.
Definition 3.1. The simplicial model for the program P for a single process in (3.1) is modeled by the simplicial set X that is the necklace of N 1-simplices. The vertices of the necklace correspond to states of the program. If there are m shared resources a 1 , . . . , a m we define an mfiltration on this necklace. The initial vertex has degree (0, . . . , 0). The operation P a i increases by one the a i degree of the corresponding edge and the subsequent vertices and edges in the necklace. The operation V a i decreases by one the a i degree of the vertices and edges in the necklace following the corresponding edge. Assume programs P 1 , . . . , P n with shared resources a 1 , . . . , a m have as simplicial models the m-filtered simplicial sets X 1 , . . . X n . We want a model for the concurrent program P = (P 1 | · · · |P n ). The simplicial set X 1 × · · · × X n has an induced m-filtration (see Section 2.2). A state of P is a vertex x = (x 1 , . . . , x n ) ∈ X 1 × · · · × X n . Definition 3.3. We call a state x = (x 1 , . . . , x n ) of P valid if across 1 ≤ i ≤ n the uses of resources by P i at s j i are compatible, where s j i is the state of P i corresponding to the vertex x i of the model X i . More precisely, for 1 ≤ i ≤ n, 1 ≤ j ≤ m and x i ∈ P i , let D ij (x i ) be the amount that a j has decreased from k j if the program for the process P i runs from its initial state to the state Lemma 3.4. The set of valid states of P is given by the vertices in (X 1 × · · · × X n ) (k 1 ,...,km) .
Proof. Consider x = (x 1 , . . . , x n ) ∈ X 1 × · · · × X n . Let 1 ≤ i ≤ n and 1 ≤ j ≤ m. From the definition of the grading on X i , x i has a j degree Therefore x is valid if and only if x ∈ (X 1 × · · · × X n ) (k 1 ,...,km) .
An edge of X 1 × · · · × X n is of the form (e 1 , . . . , e n ) where e i is an edge of X i . Note that e i may be degenerate. That is e i = sx i where x i is a vertex of X i . Definition 3.5. Define an edge e = (e 1 , . . . , e n ) to be valid if across 1 ≤ i ≤ n the uses of resources by P i from s j i to s j ′ i are compatible, where s j i and s j ′ i are the states corresponding to d 1 (e i ) and d 0 (e i ), respectively. More precisely, using the notation of Definition 3.3, e is valid if for each 1 ≤ j ≤ m, Lemma 3.6. The set of valid edges of P is given by the edges in (X 1 × · · · × X n ) (k 1 ,...,km) .
Proof. Consider e = (e 1 , . . . , e n ) ∈ X 1 × · · · × X n . Let 1 ≤ i ≤ n and 1 ≤ j ≤ m. From the definition of the grading on X i , e i has a j degree equal to the maximum of the a j degree of its vertices d 1 (e i ) and d 0 (e i ). Thus the degree of e is Therefore x is valid if and only if x ∈ (X 1 × · · · × X n ) (k 1 ,...,km) . Definition 3.7. Assume the program P = (P 1 | . . . |P n ) has shared resources a 1 , . . . , a m where a i is a k i -semaphore. The simplicial model for P is given by the simplicial set (X 1 × · · · × X n ) (k 1 ,...,km) . Here the unlabeled vertices and edges are in filtration (0, 0). The vertices and edges labeled a, b and ab are in filtration (1, 0), (0, 1) and (1,1) respectively. Now consider the concurrent execution of A and B, denoted (A|B). It is modeled by the following simplicial set (A × B) (1,1) . Example 3.9. Let a be a 2-semaphore. Consider the three identical programs, A, B and C given by This program is modeled by the following filtered simplicial set X. a a a The concurrent program (A|B|C) is modeled by the simplicial set (X × X × X) (2) , which is a triangulation of the boundary of the cube.
Remark 3.10. One can also define analogous cubical models for concurrent programs. The simplicial models presented here are the triangulations of those cubical models.

3.2.
Simplicial models of execution spaces. Next we construct simplicial models for the space of executions from one state to another in the simplicial models in Section 3.1.  Then Map X (0, 7) is given by the following simplicial set.
Thus Map X (0, 7) is homotopy equivalent to the circle. We remark that this is an example of higher order structure that is not detected by the path category [9]. Thus Map X (a, l) is homotopy equivalent to S 1 ∨ S 1 , the wedge of two circles.

Future directions
It would be very nice to have a Quillen model structure on simplicial categories appropriate to their use as models for concurrency. A natural candidate is J. Bergner's model structure on simplicial categories [1], which is closely related to A. Joyal's quasi-category model structure on simplicial sets [10]. However this model structure is too strong, since the weak equivalences induce equivalences of path categories. Thus a weaker notion of equivalence is needed. For some recent ideas in this direction, see [13].
The simplicial set models in this paper are in fact triangulations of cubical set models. When constructing models of the execution spaces from one state to another, we used (simplicial) necklaces on the simplicial models. Instead, one could use cubical necklaces on the cubical models, if one understood such things from a homotopy-theoretic point of view. These models would be more economical. For example, we should be able to redo Example 3.13 using cubical sets and cubical necklaces to obtain the following cubical set for Map X (a, l).