|
This article is cited in 1 scientific paper (total in 1 paper)
Transitivity-preserving operators on relations
L. A. Sholomov
Abstract:
Let $\mathcal T=\mathcal T(A)$ be the class of all transitive relations on
a finite set $A$. We say that an operator $r=F(r_1,\ldots, r_n)$ on the set of relations
preserves transitivity if
$$
r_1,\ldots,r_n\in\mathcal T\quad \Rightarrow\quad r\in\mathcal T.
$$
Let us introduce operators $\tau_n^{(u)}(r_1,\ldots,r_n)$, $u=0,1$, $n\geq 0$,
by setting $\tau_0^{(0)}=\emptyset$, $\tau_0^{(1)}=A^2$,
$$
\tau_n^{(u)}=r_1\cap(\overline{(r_1^{-1})}\cup \tau_{n-1}^{(u)}(r_2,\ldots,r_n)),
\qquad n\geq 1.
$$
Any operator derived from $\tau_n^{(u)}$ by replacing some of $r_i$,
$1\leq i\leq n,$ with $r_i^{-1}$ is called a $\tau$-operator. It is shown that
an operator $F$ representable by means of set-theoretic operations and inversion
of relations preserves transitivity if and only if it is representable
as an intersection of $\tau$-operators.
Received: 05.01.1995
Citation:
L. A. Sholomov, “Transitivity-preserving operators on relations”, Diskr. Mat., 10:1 (1998), 28–45; Discrete Math. Appl., 8:2 (1998), 183–200
Linking options:
https://www.mathnet.ru/eng/dm417https://doi.org/10.4213/dm417 https://www.mathnet.ru/eng/dm/v10/i1/p28
|
Statistics & downloads: |
Abstract page: | 440 | Full-text PDF : | 238 | First page: | 2 |
|