BRICS RS-01-38 Z. Ésik: Free De Morgan Bisemigroups and Bisemilattices BRICS

Basic Research in Computer Science

Free De Morgan Bisemigroups and Bisemilattices

Zoltán Ésik BRICS Report Series RS-01-38 ISSN 0909-0878 October 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Zoltán Ésik.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/01/38/

Free De Morgan Bisemigroups and Bisemilattices

Z. Ésik ^{∗}

Dept. of Computer Science University of Aalborg Denmark

                           esik@inf.u-szeged.hu

September, 2001

Abstract

We give a geometric representation of free De Morgan bisemigroups, free commutative De Morgan bisemigroups and free De Morgan bisemilattices, using labeled graphs.

Keywords: bisemigroup, bisemilattice, free algebra, De Morgan’s laws, cograph, series-parallel graph.

AMS classification: 08A70, 08B20

1 Introduction

J. A. Brzozowski and Z. Ésik have introduced in [?] an algebra C capable of representing and counting hazards in asynchronous circuits. The algebra C has two binary operations ⊕ and ⊗, a unary operation ^{−}, called quasi-complementation, and the constants 0 and 1 such that both (C, ⊕, 0) and (C, ⊗, 1) are commutative monoids, ^{−} is an involution satisfying De Morgan’s laws with respect to the operations ⊕ and ⊗, and such that \overline{0} = 1. In [?], such algebras were called commutative De Morgan bisemigroups, a generalization of De Morgan bisemilattices studied, in connection with circuits, in [?]. We conjecture that the variety of De Morgan bisemigroups is in fact generated by the algebra C, so that an equation holds in C if and only if it is provable from the defining equations of De Morgan bisemigroups.

∗This research was supported by BRICS and the National Foundation of Scientific Research of Hungary under grant no. T30511. Permanent address: Dept. of Computer Science, University of Szeged, 6701 Szeged, P.O.B. 652, Hungary.

In this paper, building on the geometric description of free commutative bisemigroups and free bisemigroups [?, ?, ?], we provide a concrete geometric description using labeled graphs and digraphs of the free De Morgan bisemigroups, free commutative De Morgan bisemigroups, and free De Morgan bisemilattices. In particular, we show that the free De Morgan bisemigroup on a set A may be represented as an algebra of isomorphism classes of A ∪ \overline{A}-labeled sets, where \overline{A} is a disjoint copy of A, equipped with two transitive digraph structures, in fact two N-free partial orders, such that any two elements of the set are related by exactly one of the two orders. The two binary operations are the series products with respect to the two orders, and the operation of quasi-complementation exchanges the two orders and complements the labels. The free commutative De Morgan bisemigroup on A has a similar description using A ∪ \overline{A}-labeled graphs. Our study of algebras of labeled graphs, posets and biposets is also related to recent work on two-dimensional extensions of automata theory by Lodaya, Weil, Hashiguchi, Kuske and others, see [?, ?, ?, ?, ?].

2 Preliminaries

Recall that bisemigroup is an algebra B = (B, ⊕, ⊗) equipped with binary associative operations ⊕ and ⊗. (Bisemigroups with a a common neutral element for the two associative operations were called double monoids in [?] and bimonoids in [?]. Some authors use the term binoid.) A commutative bisemigroup is a bisemigroup in which both operations are commutative. A bisemilattice [?] is a commutative bisemigroup in which both operations are idempotent. (Plonka [?] introduced the term quasi-lattice for these structures.) In a bisemilattice, we will sometimes denote the operations by ⊔ and ∧. Morphisms of bisemigroups preserve the operations.

A De Morgan bisemigroup [?] is an algebra D = (D, ⊕, ⊗,^{−} , 0, 1) such that (D, ⊕, ⊗) is a bisemigroup, and the quasi-complementation operation^{−} : D → D and the constants 0, 1 satisfy

x ⊕ 0 = 0 ⊕ x = x  (1)
x ⊗ 1 = 1 ⊗ x = x  (2)
x ⊗ 0 = 0 ⊗ x = 0  (3)
x ⊕ 1 = 1 ⊕ x = 1  (4)

and

\overline{\overline{x}} = x  (5)
\overline{x ⊕ y} = \overline{x} ⊗ \overline{y}  (6)
\overline{x ⊗ y} = \overline{x} ⊕ \overline{y}.  (7)

It then follows that

\overline{0} = 1  (8)
\overline{1} = 0.  (9)

A commutative De Morgan bisemigroup is a De Morgan bisemigroup which is a commutative bisemigroup, and a De Morgan bisemilattice is a De Morgan bisemigroup which is a bisemilattice. Morphisms of De Morgan bisemigroups, commutative De Morgan bisemigroups and De Morgan bisemilattices also preserve the constants and the quasi-complementation. Note that any De Morgan bisemigroup is determined by the operations ⊕ and ^{−} and the constant 0.

In any bisemilattice B = (B, ⊔, ∧), the binary operations determine two partial orders ⊒ and ≤ defined by x ⊒ y if and only if x ⊔ y = x and x ≤ y if and only if x ∧ y = x, for all x, y ∈ B. The operations are in turn determined by the partial orders in that x ⊔ y is the l.u.b. of x and y with respect to the partial order ⊒, and x ∧ y is the g.l.b. of x and y with respect to ≤. It is known that a bisemilattice is a lattice if and only if the partial orders ⊒ and ≤ coincide. When B is a De Morgan bisemilattice, 0 is least and 1 is greatest with respect to both partial orders. It is clear that any homomorphism of bisemilattices preserves ⊒ and ≤. Moreover, for x, y in a De Morgan bisemilattice,

x ⊒ y ⇔ \overline{x} ≤ \overline{y}.  (10)

This latter property is characteristic: If B is a bisemilattice equipped with a unary operation ^{−} and constants 0 and 1 satisfying (??) – (??), then B is a De Morgan bisemilattice if and only if (??) and (??) hold.

Lemma 2.1 Suppose that S and S′ are De Morgan bisemigroups. Suppose that X ⊆ S is closed with respect to quasi-complementation.

1. Then X generates S if and only if every s ∈ S − {0, 1} can be generated from X by ⊕ and ⊗.

2. Suppose that S is generated by X. Then a function h : S → S′ is a De Morgan bisemigroup homomorphism if and only if h preserves 0, 1, the quasi-complementation on the elements of X, and the operations ⊕ and ⊗.

For all undefined notions of universal algebra, see any standard text such as [?, ?].

3 Labeled graphs

We take a graph to be a pair (G, ∼_{G}) consisting of a finite nonempty set and an irreflexive symmetric relation ∼_{G} on the set G of vertices. The elements of ∼_{G} are called edges. Suppose that A is a set. An A-labeled graph is a graph (G, ∼_{G}) equipped with a labeling function ℓ_{G} : G → A. A morphism of A-labeled graphs is a function which preserves the edges and the labeling. An isomorphism is a bijective morphism whose inverse is also a morphism. We identify any two isomorphic A-labeled graphs.

Suppose that G and H are A-labeled graphs. Since we work with isomorphism classes of labeled graphs, in the definitions of the operations ⊕ and ⊗, below we may without loss of generality assume that G and H are disjoint. We define

G ⊕ H = (G ∪ H, ∼_{G⊕H}, ℓ_{G⊕H}),

where

∼_{G⊕H} = ∼_{G} ∪ ∼_{H}
ℓ_{G⊕H}(u) = \{ \begin{matrix}ℓ_{G}(u) & if u ∈ G \\ ℓ_{H}(u) & if u ∈ H. \end{matrix}

Moreover, we define

G ⊗ H = (G ∪ H, ∼_{G⊗H}, ℓ_{G⊗H}),

where

∼_{G⊗H} = ∼_{G} ∪ ∼_{H} ∪ G × H ∪ H × G,

and where ℓ_{G⊗H} is defined in the same way as ℓ_{G⊕H}. We also define an operation of quasi-complementation:

\overline{G} = (G, ∼\overline{G}, ℓ\overline{G}),

where ℓ\overline{G} = ℓ_{G} and

∼\overline{G} = \{(u, v) ∈ G × G : u ≠ v, (u, v) ∉∼_{G}\}.

The collection of all A-labeled graphs, equipped with the above operations, satisfies all of the defining equations of commutative De Morgan bisemigroups not involving 0 and 1. Thus, if we add elements 0 and 1 such that (??) – (??), (??) and (??) hold, then we obtain a commutative De Morgan bisemigroup G_{A}.

Remark 3.1 The graphs in the smallest subalgebra of G_{A} containing the singletons are called labeled cographs, or complement reducible graphs. Since if G is a singleton graph, G = \overline{G}, it follows that a labeled graph is a cograph if and only if it can be generated from the singletons by any two of the operations ⊕, ⊗ and ^{−}. It is also known, see [?, ?], that a (labeled) graph is a cograph if and only if it is P_{4}-free, i.e., when it contains no subgraph isomorphic to a path on 4 vertices.

Remark 3.2 An A-labeled graph may also be represented as a system (G, ≈_{G} , ∼_{G}, ℓ_{G}) where G is a finite nonempty set, ≈_{G} and ∼_{G} are disjoint irreflexive and symmetric relations on G, and ℓ_{G} is a labeling function G → A. Moreover, it is required that for any two distinct vertices u, v, either u ≈ v or u ∼ v holds, i.e., that (G, ≈_{G} ∪ ∼_{G}) is a complete graph. The ⊕ and ⊗ operations can then be defined so that

G ⊕ H = (G ∪ H, ≈_{G⊕H}, ∼_{G⊕H}, ℓ_{G⊕H}),

where

≈_{G⊕H} = ≈_{G} ∪ ≈_{H} ∪ G × H ∪ H × G
∼_{G⊕H} = ∼_{G} ∪ ∼_{H},

and

G ⊗ H = (G ∪ H, ∼_{G⊗H}, ≈_{G⊗H}, ℓ_{G⊗H}),

where

≈_{G⊗H} = ≈_{G} ∪ ≈_{H}
∼_{G⊗H} = ∼_{G} ∪ ∼_{H} ∪ G × H ∪ H × G,

and where ℓ_{G⊕H} and ℓ_{G⊗H} are defined above. Quasi-complementation is given by

\overline{G} = (G, ≈\overline{G}, ∼\overline{G}, ℓ\overline{G}),

where ℓ\overline{G} = ℓ_{G} and

≈\overline{G} = ∼_{G}
∼\overline{G} = ≈_{G} .

For later use we note:

Lemma 3.3 The following cancellation laws hold in G_{A}, for all H ≠ 0, 1.

1. If G_{1} ⊕ H = G_{2} ⊕ H, then G_{1} = G_{2}.

2. If G_{1} ⊗ H = G_{2} ⊗ H, then G_{1} = G_{2}.

Proof. If G_{1} ⊕ H and G_{2} ⊕ H are isomorphic, then G_{1} and G_{2} have the same number of connected components. Moreover, there is a bijection between the connected components of G_{1}⊕H and G_{2}⊕H which assigns to any component of G_{1} ⊕ H an isomorphic component of G_{2} ⊕ H. But then, by finiteness, there is a similar bijection between the components of G_{1} and G_{2}, proving that G_{1} and G_{2} are isomorphic. The second claim follows from the first by taking complements.

□

In order to represent the free commutative De Morgan bisemigroup by cographs, we modify the operation of quasi-complementation. Suppose that A is a set and \overline{A} = \{\overline{a} : a ∈ A\} is a disjoint copy of A. We define a new quasi-complementation operation on the set of A ∪ \overline{A}-labeled graphs. Given G = (G, ∼_{G}, ℓ_{G}), define \overline{G} = (G, ∼\overline{G}, ℓ\overline{G}), where

∼\overline{G} = \{(u, v) ∈ G × G : u ≠ v, (u, v) ∉∼_{G}\}  (11)
ℓ\overline{G}(u) = \overline{ℓ_{G}(u)}, u ∈ G.  (12)

Here we write \overline{\overline{a}} = a, for all a ∈ A. As before, we define \overline{0} = 1 and \overline{1} = 0. The resulting algebra, denoted G_{A,\overline{A}}, is a again a commutative De Morgan bisemigroup. Let CDBS_{A} denote the least subalgebra of G_{A,\overline{A}} containing the singleton graph labeled a, for each a ∈ A. By Remark ??, an A∪\overline{A}-labeled graph G belongs to CDBS_{A} if and only if G is P_{4}-free. Since G_{A,\overline{A}} is a commutative De Morgan bisemigroup, so is CDBS_{A}. In the next result, we identify each letter in A ∪ \overline{A} with the corresponding labeled graph having a single vertex.

Theorem 3.4 CDBS_{A} is freely generated by A in the variety of all commutative De Morgan bisemigroups.

Proof. Suppose that S is a commutative De Morgan bisemigroup and h is a function A → S. We show how to extend h to a homomorphism h^{♯} : CDBS_{A} → S. First, we define h^{♯}(0) = 0 and h^{♯}(1) = 1. Moreover, we define h^{♯}(a) = h(a) and h^{♯}(\overline{a}) = \overline{h(a)}, for each a ∈ A. Suppose now that G ∈ CDBS_{A} has 2 or more vertices. If G is not connected, write G in the form G = G_{1} ⊕ … ⊕ G_{n}, where the G_{i} are all of the connected components of G. We have G_{i} ∈ CDBS_{A}, for all i = 1, …, n. Define h^{♯}(G) = h^{♯}(G_{1}) ⊕ … ⊕ h^{♯}(G_{n}). If G is connected, then G can be written as G = G_{1} ⊗ … ⊗ G_{n}, where the G_{i} are disconnected. In this case, define h^{♯}(G) = h^{♯}(G_{1}) ⊗ … ⊗ h^{♯}(G_{n}). That h^{♯} is well-defined follows by the associativity and commutativity of the operations. It is now immediate that h^{♯} preserves ⊕ and ⊗. The fact that h^{♯} also preserves quasi-complementation follows from Lemma ??. □

When A has a single element, G_{A} may be considered to be a commutative De Morgan bisemigroup of unlabeled graphs, and the constants 0 and 1. Let G denote this commutative De Morgan bisemigroup and let CG denote the subalgebra of G determined by the cographs and the constants. It is natural to ask whether there are equations that hold in G but fail to hold in all commutative De Morgan bisemigroups, i.e., whether the variety of commutative bisemigroups is generated by G. Below we answer this question. We will show that both G and CG generate the variety of commutative De Morgan bisemigroups.

Proposition 3.5 When A is a countable set, there is an embedding of the free commutative De Morgan bisemigroup CDBS_{A} into CG.

Proof. Let a_{1}, a_{2}, … be a fixed enumeration of A, and for each n ≥ 1, define

G_{n} = • ⊗ (\overbrace{• ⊕ … ⊕ •}^{(n+1)−times}),

where • denotes the singleton graph. Note that the complement of G_{n} in CG is

\overline{G_{n}} = • ⊕ (\overbrace{• ⊗ … ⊗ •}^{(n+1)−times}).

Let f denote the homomorphism CDBS_{A} → CG determined by the assignment a_{n} ↦ G_{n}, n ≥ 1.

For a graph G ∈ CDBS_{A}, f(G) can be constructed by replacing each vertex of G labeled a_{n} by a copy of G_{n}, and each vertex labeled \overline{a_{n}} by a copy of \overline{G_{n}}. Thus, if u and v are connected by an edge in G, then any vertex of the graph replacing u will be connected in f(G) to each vertex of the graph replacing v. Clearly, each G_{n} and \overline{G_{n}} contains both vertices that are connected by an edge, and disconnected vertices. Using this fact, it follows that when G ∈ CDBS_{A} is connected and G is not a singleton, then f(G) contains both a complete graph on three vertices, and a graph isomorphic to P_{3}, the path on three vertices. Also, if G is connected, then so is f(G), unless G consists of a single vertex labeled \overline{a_{n}}, for some n. Thus, when G is connected and is not a singleton, no connected component of f(G) is isomorphic to any of the G_{n} or to a connected component of any of the \overline{G_{n}}.

We claim that f is injective. To prove this, suppose that H, K ∈ CDBS_{A}, H ≠ K are graphs with the minimum number of vertices such that f(H) = f(K). If H or K is a singleton, then H = K, since there is no nontrivial way of generating any of the G_{n} and \overline{G_{n}} from the graphs G_{m}, \overline{G_{m}}, m ≥ 1 by the operations ⊕ and ⊗. Thus we may assume that neither H nor K is a singleton. Suppose that H is disconnected, say H = H_{1} ⊕ … ⊕ H_{m}, where m > 1 and the H_{i} are connected. Then K is also disconnected, since otherwise f(K) would be connected, but f(H) is not. Let K = K_{1}⊕…⊕K_{n}, where the K_{j} are connected. If one of the H_{i} has a single vertex, then by the preceding argument, there is a j with H_{i} = K_{j}. Removing these components from H and K, the resulting graphs H′ and K′ are distinct and satisfy f(H′) = f(K′), by Lemma ??. Since also H′ ≠ K′, this contradicts our assumption on H and K. We conclude that none of the H_{i} is a singleton. In the same way, none of the K_{j} is a singleton. But then all of the graphs f(H_{i}) and f(K_{j}) are connected, so that f(H) = f(K) only if m = n and there is a permutation i_{1}, …, i_{n} of the integers 1, …, n such that f(H_{j}) = f(K_{i_{j}}), for all j = 1, …, n. But since H ≠ K, there is a j with H_{j} ≠ K_{i_{j}}. This is again a contradiction. If H is connected, consider \overline{H} and \overline{K}. They have the same number of vertices as H and K, and f(\overline{H}) = f(\overline{K}). But since \overline{H} is disconnected, we can derive a contradiction as before. □

Theorem 3.6 The variety of commutative De Morgan bisemigroups is generated by either one of the algebras G and CG.

Proof. Since CG is a subalgebra of G and G is a commutative De Morgan bisemigroup, it suffices to prove that the variety generated by CG contains the free commutative De Morgan bisemigroup CDBS_{A} generated by a countable set A. But this holds by Proposition ??. □

4 Labeled directed graphs

In order to give a representation of the free De Morgan bisemigroups, we will now consider labeled 2-digraphs (G, ρ_{G}, τ_{G}, ℓ_{G}), where G is a finite nonempty set, ρ_{G} and τ_{G} are irreflexive antisymmetric relations on G, and ℓ_{G} : G → A. We also require that for any two distinct vertices u, v ∈ G, either u and v are related by ρ_{G}, or else u and v are related by τ_{G}, but not by both. An isomorphism G → H of A-labeled 2-digraphs G, H is a bijection f : G → H which preserves the labeling and such that for all u, v ∈ G, (u, v) ∈ ρ_{G} if and only if (f(u), f(v)) ∈ ρ_{H} and similarly, (u, v) ∈ τ_{G} if and only if (f(u), f(v)) ∈ τ_{H}. We identify any two isomorphic A-labeled 2-digraphs. The operations ⊕ and ⊗ are defined as follows, where without loss of generality we again assume that G and H are disjoint:

G ⊕ H = (G ∪ H, ρ_{G⊕H}, τ_{G⊕H}, ℓ_{G⊕H}),

where

ρ_{G⊕H} = ρ_{G} ∪ ρ_{H} ∪ G × H
τ_{G⊕H} = τ_{G} ∪ τ_{H},

and

G ⊗ H = (G ∪ H, ρ_{G⊗H}, τ_{G⊗H}, ℓ_{G⊗H}),

where

ρ_{G⊗H} = ρ_{G} ∪ ρ_{H}
τ_{G⊗H} = τ_{G} ∪ τ_{H} ∪ G × H,

and where ℓ_{G⊕H} and ℓ_{G⊗H} are defined above. Quasi-complementation is given by

\overline{G} = (G, ρ\overline{G}, τ\overline{G}, ℓ\overline{G}),

where ℓ\overline{G} = ℓ_{G} and

ρ\overline{G} = τ_{G}
τ\overline{G} = ρ_{G}.

Let D_{A} denote the structure that results by adding 0 and 1 to A-labeled 2digraphs such that (??) – (??) and (??), (??) hold. Clearly, D_{A} is a De Morgan bisemigroup. When \overline{A} is a disjoint copy of A, we may also define the De Morgan bisemigroup D_{A,\overline{A}} which is the same as D_{A∪\overline{A}} except that the labeling function of the quasi-complement is given by (??). Let DBS_{A} denote the subalgebra of D_{A,\overline{A}} generated by the singleton 2-digraphs corresponding to the elements of A.

Remark 4.1 The paper [?] contains a common generalization of the geometric characterization of series-parallel digraphs (or posets) [?, ?] and cographs [?, ?]. It follows from this general result that an A-labeled 2-digraph (G, ρ_{G}, τ_{G}, ℓ_{G}) belongs to the subalgebra of D_{A} generated by the singletons if and only if both ρ_{G} and τ_{G} are transitive (so that they define partial orders), and ρ_{G} is N-free. Thus there are no distinct vertices u, v, w, z such that the order relations between them are given by uρ_{G}w, vρ_{G}w, vρ_{G}z. It then follows τ_{G} is also N-free. (Recall that we are assuming that any two vertices of a 2-digraph (G, ρ_{G}, τ_{G}, ℓ_{G}) are related by exactly one of ρ_{G} and τ_{G}.) The same conditions characterize the 2-digraphs in DBS_{A}.

Theorem 4.2 DBS_{A} is freely generated by A in the class of all De Morgan bisemigroups.

The proof is similar to that of Theorem ??.

Consider now the De Morgan bisemigroup D of unlabeled 2-digraphs, and its subalgebra ND generated by the singleton 2-digraph. We have:

Theorem 4.3 The variety of De Morgan bisemigroups is generated by both D and ND.

This can be proven following the lines of the proof of Proposition ?? and Theorem ??. One shows that when A is a countable set {a_{1}, a_{2}, …}, the homomorphism g : DBS_{A} → ND determined by the assignment

a_{n} ↦ • ⊕ (\overbrace{• ⊗ … ⊗ •}^{n−times}), n ≥ 1

is injective. Indeed, this fact follows from Proposition ??, since the homomorphism f given in the proof of Proposition ?? is the composite of the homomorphism g with a homomorphism CG → ND.

5 Free De Morgan bisemilattices

In order to obtain a geometric representation of the free De Morgan bisemilattices, we will consider labeled graphs with a particular property. We call an A-labeled graph G ⊕-irreducible if G is connected, i.e., when there exist no labeled graphs G_{1} and G_{2} with G = G_{1} ⊕ G_{2}. Similarly, we call G ⊗- irreducible, if \overline{G} is ⊕-irreducible, i.e., when there exist no labeled graphs G_{1} and G_{2} with G = G_{1} ⊗ G_{2}. If G is both ⊕-irreducible and ⊗-irreducible, then we call G irreducible. The ⊕-components of G are the connected components of G. The ⊗-components of G are the quasi-complements of the ⊕-components of \overline{G}. Thus, denoting the ⊕-components by G_{i} and the ⊗-components by H_{j}, where i = 1, …, n and j = 1, …, m, we can write

G = G_{1} ⊕ … ⊕ G_{n}
G = H_{1} ⊗ … ⊗ H_{m},

where each G_{i} is ⊕-irreducible and each H_{j} is ⊗-irreducible.

We say that an A-labeled graph G has inherently nonisomorphic components if it is irreducible, or for each way of writing G = G_{1} ⊕ … ⊕ G_{n} or G = G_{1} ⊗ … ⊗ G_{n}, the labeled graphs G_{i} are pairwise nonisomorphic and have inherently nonisomorphic components. Clearly, if G is not ⊕-irreducible then G has inherently nonisomorphic components if and only if the ⊕-components of G are pairwise nonisomorphic and have inherently nonisomorphic components. And if G is not ⊗-irreducible then G has inherently nonisomorphic components if and only if the ⊗-components of G are pairwise nonisomorphic and have inherently nonisomorphic components.

Suppose that G, H have inherently nonisomorphic components. Up to isomorphism, let C_{1}, …, C_{m} denote all of the ⊕-components of G and H, and D_{1}, …, D_{n} the ⊗-components of G and H. We define

G ⊔ H = C_{1} ⊕ … ⊕ C_{m}
G ∧ H = D_{1} ⊗ … ⊗ D_{n}.

It is easy to see that G has inherently nonisomorphic components if and only if \overline{G} has. It follows that the quasi-complementation operation is well-defined on A-labeled graphs having inherently nonisomorphic components. When we add 0 and 1, there results a De Morgan bisemilattice IG_{A}. In a similar way, we can define the De Morgan bisemilattice IG_{A,\overline{A}}.

For any G, H ∈ IG_{A} or G, H ∈ IG_{A,\overline{A}}, we have G ⊒ H if and only if G = 1 or H = 0 or every ⊕-component of H is a ⊕-component of G, and G ≤ H if and only if G = 0 or H = 1 or every ⊗-component of H is a ⊗-component of G. (The relations ⊒ and ≤ were defined in Section ??.) Thus, G⊓H = inf_{⊒}{G, H} always exists. Moreover, when G ⊓ H is a graph, its set of ⊕-components is the intersection of the sets of ⊕-components of G and H. In the same way, G ∨ H = sup_{≤}{G, H} also exists.

Proposition 5.1 Suppose that G, H ∈ IG_{A}, or G, H ∈ IG_{A,\overline{A}}. If G and H are cographs, then G ⊔ H and G ∧ H are also cographs.

Proof. G ⊔ H contains a P_{4} if and only if G or H does, and similarly for G ∧ H. □

Thus, those A ∪ \overline{A}-labeled cographs that have inherently nonisomorphic components form a subalgebra of IG_{A,\overline{A}}. Let DBSL_{A} denote this subalgebra.

Proposition 5.2 For any G ∈ G_{A,\overline{A}}, we have G ∈ DBSL_{A} if and only if G can be generated from the singletons corresponding to the letters in A and the constants 0, 1 by the operations ⊔, ∧ and ^{−}.

Thus, DBSL_{A} is the subalgebra of IG_{A,\overline{A}} generated by the singletons corresponding to the letters in A.

Theorem 5.3 For each set A, DBSL_{A} is the free De Morgan bisemilattice on A.

Proof. We have already noted that DBSL_{A} is a De Morgan bisemilattice. By Theorem ??, there is a homomorphism h : CDBS_{A} → DBSL_{A} which maps the labeled graph corresponding to each letter in A to itself. By Proposition ??, h is surjective. To complete the proof we need to show that whenever θ is a congruence relation on CDBS_{A} such that the quotient CDBS_{A}/θ is a De Morgan bisemilattice, i.e., such that ⊕ and ⊗ are idempotent on CDBS_{A}/θ, then the kernel of h is included in θ. But this follows from the fact that for all such congruence relations θ and any G ∈ CDBS_{A}, G θ h(G). Indeed, this is clear when G is a singleton. We proceed by induction on the number of vertices of G. When G has two or more vertices, then G is either not ⊕-irreducible or not ⊗-irreducible. We only consider the first case. If G is not ⊕-irreducible, then we can write G = G_{1} ⊕ … ⊕ G_{n}, n > 1, where the G_{i} are ⊕-irreducible labeled graphs in CDBS_{A}. By induction, G_{i} θ h(G_{i}) holds for each i = 1, …, n. Let {i_{1}, …, i_{m}} denote a maximal subset of {1, …, n} such that h(G_{i_{1}}), …, h(G_{i_{m}}) are pairwise nonisomorphic. Since the h(G_{i}) are connected, we have

G = G_{1} ⊕ … ⊕ G_{n}
θ h(G_{1}) ⊕ … ⊕ h(G_{n})
θ h(G_{i_{1}}) ⊕ … ⊕ h(G_{i_{m}})
= h(G_{1}) ⊔ … ⊔ h(G_{n})
= h(G). □

Call a De Morgan bisemilattice S a De Morgan bilattice [?] if x ⊓ y and x ∨ y exist for all x, y ∈ S. Moreover, call a De Morgan bilattice S locally distributive [?] if (S, ⊔, ⊓) and (S, ∧, ∨) are distributive lattices.

Corollary 5.4 Every free De Morgan bisemilattice is a locally distributive De Morgan bilattice.

6 Acknowledgement

Parts of the results were obtained during the author’s visit at the University of Waterloo. The author would like to thank Professor John Brzozowski for his hospitality. In addition the author would like to thank the referees for their comments that helped to improve the paper.

References

[1] S. L. Bloom and Z. Ésik, Free shuffle algebras in language varieties. Theoret. Comput. Sci. 163 (1996) 55–98.

[2] J. A. Brzozowski, De Morgan bisemilattices, in: 30th IEEE International Symposium on Multiple-Valued Logic, Portland, Oregon, May 2000, IEEE Press, Los Alamitos, California, 2000, pp. 23–25.

[3] J. A. Brzozowski and Z. Ésik, Hazard Algebras, Maveric Research Report 00-2, Department of Computer Science, University of Waterloo, available at

the URL http://maveric.uwaterloo.ca/publication.html. Extended

abstract to appear in: Half Century of Automata Theory, London, Ontario, July 26, 2000, World Scientific Publishing Co. Pte. Ltd., Singapore.

[4] S. Burris and H. P. Shankappanavar, A Course in Universal Algebra, Springer, New York, 1981.

[5] D. G. Corneil, H. Lerchs and L. S. Burlinham, Complement reducible graphs, Discr. Appl. Math. 3 (1981) 163–174.

[6] Z. Ésik, Free algebras for generalized languages, in: RIMS Kokyuroku 1166, ed. M. Ito, Kyoto University, Kyoto, 2000, pp. 52–58.

[7] Z. Ésik and Z. L. Németh, Automata on series-parallel biposets, in: Developments in Language Theory 01, Vienna, LNCS, Springer-Verlag, Berlin, to appear.

[8] J. L. Gischer, The equational theory of pomsets, Theoret. Comput. Sci. 61 (1988) 199–224.

[9] J. Grabowski, On partial languages, Fund. Inform. 4 (1981) 427–498.

[10] G. Grätzer, Universal Algebra, Second edition, Springer, Berlin, 1979.

[11] K. Hashiguchi, S. Ichihara and S. Jimbo, Formal languages over free binoids, J. Autom. Lang. Comb. 5 (2000) 219–234.

[12] D. Kuske, Infinite series-parallel posets: logic and languages, in: Internat. Conf. Automata, Languages and Programming ICALP 2000, LNCS 1853, Springer, Berlin, 2000, pp. 648–662.

[13] K. Lodaya and P. Weil, Series-parallel languages and the bounded width property, Theoret. Comput. Sci. 237 (2000) 347-380.

[14] K. Lodaya and P. Weil, Rationality in algebras with a series operation, Inform. and Comput., to appear.

[15] J. Plonka, On distributive quasi-lattices, Fund. Mathematicae 60 (1967) 191–200.

[16] J. Valdes, R. E. Tarjan and E. L. Lawler, The recognition of series-parallel digraphs, SIAM J. Comput. 11 (1982) 298–313.

Recent BRICS Report Series Publications

RS-01-38 Zoltán Ésik. Free De Morgan Bisemigroups and Bisemilattices. October 2001. 13 pp.

RS-01-37 Ronald Cramer and Victor Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. October 2001. 34 pp.

RS-01-36 Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache Oblivious Search Trees via Binary Trees of Small Height. October 2001.

RS-01-35 Mayer Goldberg. A General Schema for Constructing One-Point Bases in the Lambda Calculus. September 2001. 6 pp.

RS-01-34 Flemming Friche Rodler and Rasmus Pagh. Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing. August 2001. 31 pp.

RS-01-33 Rasmus Pagh and Flemming Friche Rodler. Lossy Dictionaries. August 2001. 14 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 300– 311.

RS-01-32 Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hashing. August 2001. 21 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 121– 133.

RS-01-31 Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. July 2001. 37 pp. Extended version of an article to appear in the informal proceedings of the Second International Workshop on Rule-Based Programming, RULE 2001 (Firenze, Italy, September 4, 2001).