key: cord-0043827-io5d72lm
authors: Amazigh, Amrane; Bedon, Nicolas
title: Equational Theories of Scattered and Countable Series-Parallel Posets
date: 2020-05-26
journal: Developments in Language Theory
DOI: 10.1007/978-3-030-48516-0_1
sha: 3e396a4d226be6253bfb2a8c061e36093fcce1f7
doc_id: 43827
cord_uid: io5d72lm

In this paper we consider two classes of posets labeled over an alphabet A. The class [Formula: see text] is built from the letters and closed under the operations of series finite, [Formula: see text] and [Formula: see text] products, and finite parallel product. In the class [Formula: see text], [Formula: see text] and [Formula: see text] products are replaced by [Formula: see text] and [Formula: see text] powers. We prove that [Formula: see text] and [Formula: see text] are freely generated in their respective natural varieties of algebras [Formula: see text] and [Formula: see text], and that the equational theory of [Formula: see text] is decidable.

In his generalization of the algebraic approach of recognizable languages from finite words to ω-words, Wilke [22] introduced right binoids, that are two-sorted algebras equipped with a binary product and an ω-power. The operations are linked together by equalities reflecting their properties. These equalities define a variety of algebras. This algebraic study of ω-words have since been extended to more general structures, such as for example partial words (or equivalently, labeled posets) or transfinite strings (long words). In [8] , shuffle binoids are right binoids equipped with a shuffle operation that enables to take into consideration N-free posets with finite antichains and ω-chains instead of ω-words. In [3, 5] , the structure of right binoids in two parts is modified in order to enable products to extend over ω, ie. small ordinals (≤ ω n , n ∈ N) and countable ordinals. The latter algebras are enriched in [10, 11] with operations such as for example reverse ω-power in order to take into account countable linear orderings (scattered in some cases). Some of the previous algebraic enrichments were also applied to shuffle binoids [4, 12] . The motivations in [3] [4] [5] 10, 11, 17, 22] are mainly the study of the links between automata, rational expressions, algebraic recognition and monadic second-order logic. In [7] [8] [9] 12, 22] the authors focus essentially on varieties of algebras; for example, free algebras are characterized in the corresponding varieties, and decisions algorithms for equivalence of terms are provided.

Let us denote by ω the reverse ordering of ω. In this paper we focus on algebras equipped with a parallel product, series product, and either ω and ω products or ω and ω powers. For example, the class SP (A) of N-free posets in which antichains are finite and chains are scattered and countable orderings lies in this framework. In [2, 6] this class has been studied from the point of view of automata, rational expression and logic. We prove here that SP (A) is the free algebra in a variety V of algebras equipped with a parallel product, series product, and ω and ω products. By removing the parallel product, it follows that A , the class of scattered and countable words over A, is also a free algebra in the corresponding variety. We also consider the class ω SP (A) where the ω and ω products are replaced by ω and ω powers, and show that it is freely generated in the corresponding variety V . Relying of decision results of [2] we prove that the equality of terms of V is decidable.

We let |E| denote the cardinality of a set E, and [n] the set {1, . . . , n}, for any non-negative integer n ∈ N.

Let J be a set equipped with a strict order <. The ordering J is linear if either j < k or k < j for any distinct j, k ∈ J. We denote by J the backward linear ordering obtained from the set J with the reverse ordering. A linear ordering J is dense if for any j, k ∈ J such that j < k, there exists an element i of J such that j < i < k. It is scattered if it contains no infinite dense sub-ordering. The ordering ω of natural integers is scattered as well as the ordering ζ of all integers (negative, 0 and positive). Ordinals are also scattered orderings. We let N , O and S denote respectively the class of finite linear orderings, the class of countable ordinals and the class of countable scattered linear orderings. We also let 0 and 1 denote respectively the empty and the singleton linear ordering. We refer to [20] for more details on linear orderings and ordinals.

A poset (P, <) is a set P partially ordered by <. For short we often denote the poset (P, <) by P . The width of P is wd(P ) = sup{|E| : Eis an antichain of P } where sup denotes the least upper bound of the set. In this paper, we restrict to posets with finite antichains and countable and scattered chains.

Let (P, < P ) and (Q, < Q ) be two disjoint posets. The union (or parallel composition) P ∪Q of (P, < P ) and (Q, < Q ) is the poset (P ∪Q, < P ∪ < Q ). The sum (or sequential composition) P + Q is the poset (P ∪ Q, < P ∪ < Q ∪ P × Q). The sum of two posets can be generalized to a J-sum of any linearly ordered sequence ((P j , < j )) j∈J of pairwise disjoint posets by j∈J P j = ( j∈J P j , ( j∈J < j ) ∪ ( j,j ∈J, j<j P j × P j )). The sequence ((P j , < j )) j∈J is called a J-factorization, or (sequential) factorization for short, of the poset j∈J P j . A poset P is sequential if it admits a J-factorization where J contains at least two elements j = j with P j , P j = 0, or P is a singleton. It is parallel when P = P 1 ∪ P 2 for some P 1 , P 2 = 0. A poset is sequentially irreducible (resp. parallelly irreducible) when P is either a singleton or a parallel poset (resp. a singleton or a sequential poset). A sequential factorization ((P j , < j )) j∈J of P = j∈J P j is irreducible when all the P j are sequentially irreducible. It is non-trivial if all the P j are non-empty.

The notions of irreducible and non-trivial parallel factorization are defined similarly. A poset is scattered if all its chains are scattered. The class SP of seriesparallel scattered and countable posets is the smallest class of posets containing 0, the singleton, and closed under finite parallel composition and sum indexed by countable scattered linear orderings. By extension of a well-known result on finite posets [18, 21] , it has a nice characterization in terms of graph properties: SP coincides with the class of scattered countable N-free posets without infinite antichains [6] . Recall that (P,

When P ∈ SP and P = R + P + S or P = P ∪ R for some R, S, P ∈ SP then P is a factor of P ; the factors of P , R and S are also factors of P .

F. Hausdorff proposed in [16] an inductive definition of scattered linear orderings. In fact, each countable and scattered linear ordering is obtained using sums indexed by finite linear orderings, ω and ω. This has been adapted in [6] to SP .

We let C ∪,+ (E) denote the closure of a set E of posets under finite disjoint union and finite disjoint sum. Definition 1. The classes of countable and scattered posets (equivalent up to isomorphism) V α and W α are defined inductively as follows:

and the class S sp of countable and scattered posets by S sp = α∈O W α .

The following theorem extends a result of Hausdorff on linear orderings [16] .

For every α ∈ O, W α can be decomposed as the closure of V α by finite disjoint union and finite disjoint sum:

Example 1. W 0 is the set of all finite N-free posets. Its subset Y 0,0 is the set of all finite linear orderings. The linear orderings ω and ω are contained in V 1 . Each poset of V 1 \ W 0 has some chain isomorphic to either ω or ω, but can not have a chain isomorphic to ω and another isomorphic to ω. The ordering ζ of all integers is in

Define a well-ordering on O × N by (β, j) < (α, i) if and only if β < α or β = α and j < i. As a consequence of Theorems 1 and 2, for any P ∈ SP there exists a unique pair (α, i) ∈ O × N as small as possible such that P ∈ X α,i .

The linear ordering ζ has rank r(ζ) = (1, 1). Each linear ordering I of S has rank r(

This implies that, for all j ∈ J, j ≥j P j (resp. j ≤j P j ) is of rank (α, 0).

Let P ∈ SP be a sequential poset such that r(P ) = (α, 0), α > 0. Let j∈J P j and j∈J P j be some non-trivial J-and J -factorizations of P where J, J ∈ {ω, ω}. Then J = J .

Proof. Assume by contradiction that J = J . Assume wlog that J = ω and J = ω. Let L = j≤k P j and R = k<j<ω P j for some k ∈ ω. Then P = L+ R. As a consequence of Remark 1, r(R) = (α, 0). Observe that there exists k ∈ ω such that R is a sequential factor of R = j ≥k P j . Let L = ω<j <k P j . As a consequence of Remark 1, r(L ) = r(R) = (α, 0). Furthermore, r(R) ≤ r(R ) ≤ r(P ). Thus r(R ) = (α, 0) too. We have P = L + R , and by Theorem 2, r(P ) = (α, 1), which is a contradiction.

In [6] an equivalence relation ∼ over the elements of a poset of SP is given, such that P/∼ is isomorphic to a countable and scattered linear ordering (Lemma 9), and such that each equivalence class is a sequentially irreducible factor of P (Lemma 10). This leads to the following proposition.

Definition 1 and Theorem 1 provide a well-founded definition of SP which we consider from now as a set, although originally defined as a class.

An alphabet A is a non-empty set (not necessarily finite) whose elements are called letters or labels. In the literature a word over A is a totally ordered sequence of elements of A. The sequence may have properties depending on the context, for example it can be finite, an ordinal, or a countable scattered linear ordering. The notion of a finite word has early been extended to partial orderings (finite partial words or pomsets [14, 15, 23] ). In this paper we consider a mixture between the notions of finite partial words and words indexed by scattered and countable linear orderings.

A poset P is labeled by A when it is equipped with a labeling total map l : P → A. Also, the finite labeled posets of width at most 1 correspond to the usual notion of words. We let denote the empty labeled poset. For short, the singleton poset labeled by {a} is denoted by a, and we often make no distinction between a poset and a labeled poset, except for operations.

The sequential product (or concatenation, denoted by P · P or P P for short) and the parallel product P P of two labeled posets are respectively obtained by the sequential and parallel compositions of the corresponding (unlabeled) posets. By extension, the sequential product j∈J P j of a linearly ordered sequence of labeled posets is the poset j∈J P j in which the label of the elements is kept. In particular, the ω-product (resp. ω-product) of an ω-sequence (resp. ω-sequence) of labeled posets (P i ) i∈ω (resp. (P i ) i∈ω ) is denoted by i∈ω P i (resp. i∈ω P i ).

The ω-power (resp. ω-power ) P ω (resp. P ω ) of the poset P is the ω-product (resp. ω-product) of an ω-sequence (resp. ω-sequence) of posets that are all isomorphic to P . As usual, in this paper we consider two labeled posets to be identical if they are isomorphic. By extension, the rank r(P ) of a labeled poset P is the rank of its underlying unlabeled poset.

Let A and B be two alphabets and let P be a poset labeled by A. For all a ∈ A, let G a be some poset labeled by B, and let G = (G a ) a∈A . The poset labeled by B consisting of P in which each element labeled by the letter a is replaced by G a , for all a ∈ A, is denoted by G • A P . If the underlying posets of P and of all the G a are in SP , then so is G • A P . 

In this section we define the different varieties studied throughout this paper by listing the axioms they satisfy. The usual notions and results of universal algebra apply to our case, even if we use here for example operations of infinite arity. For more details about universal algebra, we refer the reader to [1] . In the following 1 is considered as a neutral element (the interpretation of a constant).

for all ω-sequences x 0 , x 1 , . . . , x i , . . . and all decompositions (x 0 , . . . , In order to simplify the notation, an algebra whose set of elements is S is sometimes denoted by S when there is no ambiguity.

Throughout this section, A denotes an alphabet. We start by proving the freeness of SP (A). 

where J ∈ {ω, ω} (see Remark 1) and r(P j ) < r(P ) for all j ∈ J. Define

• if P is a sequential poset then it has a factorization P =

P j (20) where each P j is a non-empty poset of rank lower than (α, i) and n ∈ N \ {0, 1}. Define h α,i (P ) by

• otherwise, P is a parallel poset. Write

where each P s is a sequential poset and n ≥ 2. Then, define h α,i (P ) by

By Theorem 2, the factorizations used in the definition of h α,i exist. However, observe that the sequential ones ( (19) and (20)) are not unique. This would question the fact that h α,i is a well-defined function. For all P ∈ SP (A) of rank (α, i), we show that:

1. h α,i (P ) does not depend on the factorization of P and thus is well-defined; 2. h α,i commutes with all the operations of V:

We proceed by induction on (α, i). Let us start by proving that h α,i maps P ∈ X α,i to the same element of M regardless of the factorization of P . If (α, i) = (0, 0) the theorem follows immediately. Otherwise, assume first that i = 0. By Lemma 1, all the possible factorizations of P as in (19) are either all ω-factorizations or all ω-factorizations. Assume wlog that P admits only ωfactorizations as in (19) . Let P = j∈ω P j and P = j∈ω Q j be two different such ω-factorizations. By definition of h α,i

There exists a sequence (R j ) j∈ω of non-empty posets such that P = k∈ω R k and for all j ∈ ω there exist k Pj , k Pj , k Qj , k Qj ∈ ω such that

By induction hypothesis h <(α,i) commutes with all the operations of V. Then, we have for all j ∈ ω:

Thus j∈ω h <(α,i) (P j ) can be written as

We have j∈ω h <(α,i) (P j ) = j∈ω h <(α,i) (Q j ). The case where P admits only ω-factorizations as in (19) is proved symmetrically using (A 16 ) instead of (A 13 ). In addition, using (A 1 ) instead of (A 13 ) and arguments similar to those of the previous case, we prove that when P is sequential and i > 0, h α,i (P ) does not depend on the factorization of P .

Thus, we have proved that h α,i is well-defined for sequential posets of rank (α, i) ∈ O×N. In addition, the irreducible parallel factorization is unique modulo the commutativity of . Thus h α,i is well-defined for all posets of rank (α, i), for all (α, i) ∈ O × N. Furthermore, proving that h α,i commutes with all the operations in X α,i can be done by induction on r(P ) too. The arguments are very similar to those used to prove that h α,i is well-defined. It follows that h is a homomorphism of V-algebras. In addition, since h relies on h then h is unique.

The proofs of the following theorems rely on the same arguments. It suffices to restrict h to the operations of the corresponding variety. In particular, this provides a new proof of Theorem 5.

A in V 0 .

In the remainder of this section, we prove the freeness of ω SP (A) in V . The arguments are similar to those of the proof of Theorem 6.1 in [12] in which the variety considered is V without ω-power. We need the following result. A and B be two alphabets. Let S ⊆ ω SP (B) such that S is closed under sequential product, ω-power and ω-power. Let f : A → G be some function defined by f (a) = G a ∈ G for some G ⊆ S. Then, the function f : ·, ω , ω , 1) .

A in V 0 .

Furthermore, if f is bijective, S is generated by G, and G contains only sequentially irreducible posets then f is bijective.

Proof. Let u ∈ ω A whose irreducible sequential factorization is j∈J u j for some J ∈ S, where each u j ∈ A. Note that

Let v · w, x ω and y ω be some sequential factorizations of u. Then, one can prove easily that

relying on the uniqueness of the irreducible sequential factorization of u (Proposition 1). Let us prove now that when f is bijective and S is generated by a set of sequentially irreducible posets then f is bijective. Let u, v ∈ ω A and assume that f (u) = P and f (v) = Q. Let i∈I u i and j∈J v j be the irreducible sequential factorizations of respectively u and v, for some I, J ∈ S, where each u i and v j are in A. By definition of f , P = i∈I P i and Q = j∈J Q j where

Then, for all i ∈ I and for all j ∈ J, P i and Q j are sequentially irreducible posets of G. Assume that P = Q. Then I = J and, for all i ∈ I, P i = Q i . We have, for all i ∈ I, u i = v i since f is injective by hypothesis. In addition, as G generates S, each element P of S can be written as j∈J P j where each P j ∈ G, for some J ∈ S. Since f is surjective by hypothesis, for all j ∈ J there exists u j ∈ A such that f (u j ) = P j . Then f ( j∈J u j ) = P . We are now ready to prove the following theorem. -when i = 0, h 0 is defined by → 1; -when i = 1, h 1 is the unique homomorphism of V 0 -algebras ω A → S extending h (Theorem 6); -when i ≥ 2, h i is defined as follows:

• on posets P of width lower than i, h i (P ) is h i−1 (P );

• on sequential posets P of width i, h i (P ) is h i (P );

• on parallel posets P of width i, h i (P ) is defined relying on the irreducible parallel factorization j∈[n] P j of P , for some n ∈ N, by:

Proving that h is a homomorphism of V -algebras is routine. Furthermore, the uniqueness of h comes from the facts that h extends h and that A is a generating set of ω SP (A).

Throughout this section, A denotes an alphabet. The set of terms of some signature over A is the smallest set of finite words built from A using the operations of the corresponding signature. In this section we prove the decidability of the equational theory of V . Let τ be the signature of V -algebras. We start by defining the set of terms in which we are interested.

The set of terms T A over A is the smallest set satisfying the following conditions:

By equipping T A with the operations of τ , we define a structure called the term algebra T (A) = (T A , ·, , ω , ω , 1) over A. Note that T A can be considered also as the set of trees whose leaves are labeled by A ∪ {1} and whose internal nodes are labeled by the operations of τ where the out-degree of each internal node coincides with the arity of the corresponding operation.

Two terms t, t ∈ T A are equivalent if t can be derived from t using the axioms which V satisfy (denoted t ≡ t ). This equivalence relation is actually a congruence. It is well-known that T (A) is absolutely free i.e. it is freely generated by A in the class containing all the algebras of signature τ . In addition, as a consequence of Theorem 7, T (A)/≡ is isomorphic to ω SP (A) (see eg. [1, Theorem 1.3.2] ). This isomorphism can be defined by 1 = and a = a for all a ∈ A.

Then we have:

As a consequence, proving the decidability of the equational theory of V can be reduced to decide whether t = t .

We now give a quick outline of the proof. The terms t and t can be interpreted as particular forms of rational expressions over languages of SP (A), see [6] . By extension of a well-known result of Büchi on ordinals, it is known from [2] that a language of SP (A) is rational if and only if it is definable in an extension, named P-MSO, of the so-called monadic second-order logic. Two P-MSO formulae ψ t and ψ t such that L(ψ t ) = t and L(ψ t ) = t can effectively be built from t and t . We have L(ψ t ∧ ψ t ) = ∅ if and only if t = t . Theorem 8 follows from the decidability of the P-MSO theory of SP (A) [2, Theorem 6] .

This decision procedure has a non-elementary complexity. Another proof with an exponential complexity (in the size of t, t ) can be derived from the proof of [12, Theorem 7.6] , in which the ω-power is not considered, by replacing the use of [12, Theorem 7.3] by [9, Corollary 3.19] .

Finite Semigroups and Universal Algebra

Logic and rational languages of scattered and countable series-parallel posets

Automata, semigroups and recognizability of words on ordinals

Complementation of branching automata for scattered and countable N-free posets

An Eilenberg theorem for words on countable ordinals

Series-parallel languages on scattered and countable posets

Long words: the theory of concatenation and ω-power

Shuffle binoids. RAIRO-Theor

Axiomatizing omega and omega-op powers of words. RAIRO-Theor

Regular languages of words over countable linear orderings

Complementation of rational sets on countable scattered linear orderings

Two equational theories of partial words

On the construction of free algebras for equational systems

The equational theory of pomsets

On partial languages

Grundzüge einer theorie der geordneten mengen

Towards a language theory for infinite N-free pomsets

Optimal linear extension by interchanging chains

Variations on algebra: monadicity and generalisations of equational theories

Linear Orderings

The recognition of series parallel digraphs

An algebraic theory for regular languages of finite and infinite words

An algebraic approach to concurrence

We would like to thank the anonymous referees for their comments on this work. One of them pointed out that Theorem 3 can be deduced from Theorem 1 using the theory of categories, and in particular works by Fiore and Hur [13] , Robinson [19] , Adámek, Rosicky, Velbil et al.