In this paper we revisit the so-called computation rules for calculus using a single nonassociative binary operation over possibly infinite sequences of integers. In this paper we focus on the symmetric maximum 6 that is an extension of the usual maximum _ so that 0 is the neutral element, and x is the symmetric (or inverse) of x, i.e., x 6( x) = 0. However, such an extension does not preserve the associativity of _ . This fact asks for systematic ways of bracketing terms of a sequence using , 6 and which we refer to as computation rules. These computation rules essentially reduce to deleting terms of sequences based on the condition x 6( x) = 0, and they can be quasi-ordered as follows: say that rule 1 is below rule 2 if for all sequences of numbers, rule 1 deletes more terms in the sequence than rule 2. As it turns out, this quasi-ordered set is extremely complex, e.g., it has infinitely many maximal elements and atoms, and it embeds the powerset of natural numbers by inclusion. Local properties of computation rules have also been presented by the authors, in particular, concerning their canonical representations. In this paper we address the problem of determining those computation rules that preserve the monotonicity of _ , and present an explicit description of monotonic computation rules in terms of their factorized irredundant form.
Motivation
This short contribution is the continuation of the work initiated in [1, 2], and we refer the reader to these references
for further motivation. Let L be a totally ordered set with bottom element 0, and let L := { a : a 2 L} be its
“symmetric” copy endowed with the reversed order. Consider the symmetric ordered structure L˜ := L [ ( L) \ { 0}, a
bipolar scale analogous to the real line where the zero acts as a neutral element and such that a + ( a) = 0 (symmetry).
In particular, ( a) = a.
a 6 b = 0 (
|a| _ | b| In other words, if b 6= a, then a 6 b returns the element that is the larger in absolute value among the two elements a and b. Moreover, it is not difficult to see that 6 satisfies the following properties: Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). (C1) 6 coincides with the maximum on L2; (C2) a 6( a) = 0 for every a 2 L˜; (C3) (a 6 b) = ( a) 6( b) for every a, b 2 L˜.
FHoernicnes,t6ancaelm,woset hbaevhea:v(es3like3+) 6on1t=he 0re6al1lin=e,1ebxucetpt 3fo6r (a3ss6oc1ia)ti=vity 3a663(b=60c.) H=ow(aev6erb,)i6twca,sfosrhoevwenryina[,3b], cth2 at L˜if.
one requires that (C1), (C26)and (C3) hold, then (
is associative on an 6Vn i=1 ai. Sequences To remove the ambiguity when evaluating 6 on nonassociative sequences, Grabisch [3] suggested ways of making 6 associative. The solution proposed was to define a rule of computation, that is, a systematic way of putting parentheses so that the result is no longer ambiguous. Let us present here informally three of these rules1 that are rather natural: (i) aggregate separately positive and negative terms, then compute their symmetric maximum. Taking the sequence 3, 2, 3, 1, 3, 2, 1, we obtain
One sees that all results differ, and that many other rules can be created. In fact, it is more convenient to define a rule as a systematic way of deleting terms in a sequence of numbers, so as to make it associative, provided the way of deleting terms corresponds to some arrangement of parentheses. Indeed, the first rule consists in deleting all terms whenever the sequence does not fulfill the condition of associativity. The second rule consists in deleting recursively all pairs of extremal opposite elements, and the third rule deletes recursively all occurrences of extremal opposite elements. However, one has to be careful that any systematic way of deleting elements making any sequence associative does not necessarily correspond to an arrangement of parentheses. For example, deleting the maximal element 3 in the above sequence makes it associative, however no arrangement of parentheses can produce this.
This framework based on rules of computation was formalized in [1], and we will recall it in the next section. We will also recall equivalent, yet semantically rather different, quasi-orderings of rules, and briefly survey the main characteristics of the resulting partially ordered set of (equivalent classes) of computation rules. Denoting a computation rule by R, 6R is an unambiguously defined operator acting on any sequence of L˜, by first making the sequence associative by means of R, and then computing the result by 6. Then, to any given computation rule R corresponds an aggregation operator 6R, aggregating all ”numbers” of a sequence into a single number in L˜. In the sequel, we only deal with countable sets L, so that L˜ can be thought to be Z. It follows that such a study is related to the aggregation of integers, in particular to the so-called integer means or Z-means, see [4]. In the latter work, it is shown that the decomposability property introduced by Kolmogoroff [5] imposes a very limitative form of integer means, namely that the output depends only on the smallest and greatest entries. In [2], we have weakened the decomposability property and shown that a whole family of operators 6R can serve as integer means. The main objective of this paper is to study monotonic computation rules R, that is, leading to an aggregation operator 6R which is monotonically nondecreasing w.r.t. all terms of the sequence. This property is a basic requirement in most fields of application, and this is why aggregation operators, defined on either real numbers or integers, are always required to be nondecreasing (see, e.g., any kind of means, median, order statistics, etc.). As it will be shown, not all computation rules are monotonic. The main result of this paper, shown in Section 3, is to give a characterization of the set of monotonic computation rules.
1These will be revisited in Section 2 and formally defined in the proposed language formalism of [1].
Rules of Computation We now recall the formalism of [1]. As we will only consider countable sequences of elements of L˜, without loss of generality, we may assume that L˜ = Z. In this way, elements of L˜⇤ are (finite) sequences of integers, denoted by = ( i)i2 I for some finite index set I, including the empty sequence ", i.e.,
L˜⇤ = ⇣ [ (L˜)n⌘ [ { "}.
n2 N
This convention will simplify our exposition and establish connections to the theory of integer means.
Also, as 6 is commutative, the order of symbols in the word does not matter, and we can consider the decreasing order
of the absolute values of the elements in the sequence (e.g., 5, 5, 5, 3, 2, 2, 1, 0). Since sequences are ordered, we
can consider the following convenient formalism for representing sequences. For an arbitrary sequence
m1{tzimes
| p1{tizmes } |
= (n1, . . . , n1, n1, . . . , n1, . . . , nq, . . . , nq, nq, . . . , nq)
} }
| pq{tizmes } |
mq{tzimes
with n1 · · · nq, let ✓ ( ) = (n1, . . . , nq) be the sequence of absolute values (magnitudes) of integers in , and let
( ) = ((p1, m1), . . . , (pq, mq)) be the sequence of pairs of numbers of occurrence of these integers. For instance, if
= (
( ) = ((
Let S denote the set of all integer sequences in this formalism, including the empty sequence, and let S0 be the subset of all nonassociative sequences.
To facilitate the precise definition of rules of computation, we proposed [1] a language formalism over a 5-element alphabet made of 5 elementary rules ⇢ i : S ! S that act on in the following way: (i) Elementary rule ⇢ 1: if p1 > 1 and m1 > 0, then p1 is changed to p1 = 1; (ii) Elementary rule ⇢ 2: same as in (i) with p1, m1 exchanged; (iii) Elementary rule ⇢ 3: if p1 > 0, m1 > 0, the pair (p1, m1) is changed into (p1 c, m1 (iv) Elementary rule ⇢ 4: if p1 > 0, m1 > 0, and if p2 > 0, then p2 is changed into p2 = 0; (v) Elementary rule ⇢ 5: same as in (iv) with m2 replacing p2. c), where c = p1 ^ m1; Hence, elementary rules delete terms only in nonassociative sequences, and leave the associative ones invariant. A (well-formed) computation rule R is a word built with the alphabet {⇢ 1, . . . , ⇢ 5}, i.e., R 2 L (⇢ 1, . . . , ⇢ 5), such that R( ) 2 S \ S0 for all 2 S. The set of (well-formed) computation rules is denoted by R. Examples of rules are (words are read from left to right) (i) h·i+ = (⇢ 4⇢ 5)⇤ ⇢ 1⇢ 2⇢ 3, that corresponds to first putting parentheses around all positive terms and all negative terms, and then computing the symmetric maximum of the two results. (ii) h·i0 = ⇢ ⇤3, that corresponds to putting parentheses around each pair of maximal symmetric terms. (iii) h·i= = (⇢ 1⇢ 2⇢ 3)⇤ , that corresponds to putting parentheses around terms with the same absolute value and sign, and then to putting parentheses around each each pair of maximal symmetric resulting terms. It is shown in [1] that each computation rule R 2 R corresponds to an arrangement of parentheses together with a permutation on the terms of sequences. Thus each R 2 R turns the symmetric maximum into an associative operation 6R : L˜⇤ ! L˜ defined by 6R = 6 R, since R( ) 2 S \ S0 for all 2 S 2. Moreover, each computation rule has the form R = T1T2 · · · , where each Ti has the form !⇢ ↵1 ⇢ 2 ⇢ 3, with ! 2 L (⇢ 4, ⇢ 5) and ↵, 2 { 0, 1} (factorization scheme)3 Now, to compute 6R( ) one needs to delete symbols in the sequence ✓ ( ) exactly as they are deleted in ( ). This entails an ordering of R that is discussed below.
Let R, R0 2 R and, for each sequence = (ai)i2 I , let J ✓ I and J 0 ✓ I, be the sets of indices of the terms in deleted by R and R0, respectively. Then, we write R 6 R0 if for all sequences 2 S we have J ◆ J 0 . Clearly, it is ˜ 2For convenience, we assume that 6R(") = 0 and 6R(a) = a, for every a 2 L 3Here, ⇢ 0 = " and ⇢ 1 = ⇢ . reflexive and transitive, and thus it is a preorder. This induces an equivalence relation ⇠ defined as follows: R ⇠ R0 if R 6 R0 and R0 6 R. The following proposition reassembles several results in [1], and provides equivalent definitions of ⇠ .
Proposition 1. Let R, R0 2 R. Then the following assertions are equivalent.
(i) R ⇠
R0. (ii) 6R = 6R0 . (iii) Ker(6R) = Ker(6R0 ), where Ker(6R) denotes the kernel of 6R that is defined by
Ker(6R) = { 2 S | 6R( ) = 0}.
Furthermore, any two equivalent rules have exactly the same “ factorized irredundant form”. Recall that a rule R 2 R is considered in factorized irredundant form (FIF) if the two following conditions are verified: (i) Factorization: R can be factorized into a composition
R = T1T2 · · · Ti · · ·
(
and k2 = min{j : ⇢ 4 and ⇢ 5 alternate infinitely many times in !j }. • If k1 < k2, then R ⇠ T1 · · · Tk1 .
• Otherwise, k2 6 k1, and R ⇠ T1 · · · Tk02 , where Tk02 = (⇢ 4⇢ 5)⇤ ⇢ 1ak2 ⇢ b2k2 ⇢ 3.
Observe that every non-terminal term Tj (i.e., of the form !⇢ 1a⇢ b2⇢ 3) in a rule in FIF has a “certificate”.
Certificates can be defined recursively as follows. A certificate of non-terminal term T = !⇢ 1a⇢ b2⇢ 3 is an element
of Ker(T ) such that no letter of T is left unused (unread or without deleting an element of ) when is deleted.
For instance, consider T = ⇢ 4⇢ 52⇢ 4⇢ 3. Then = (
Monotonic computation rules
In this section we aim to describe those computation rules that are monotonic. Recall that a rule R 2 R is monotonic
if 6R(a1, . . . , an) 6 6R(a01, . . . , a0n), whenever ai 6 a0i for every n 2 N and i = 1, . . . , n. For instance, it is not
difficult to see that both h·i0 and h·i+ are monotonic, however, h·i= is not:
6h·i= (
In order to study monotonicity, first observe the following facts.
(i) 6R is monotonic for every rule R on S \ S0. Hence, we can consider only sequences in S0. 4Note that a certificate exists if and only if ! neither contains ⇢ ⇤4, ⇢ ⇤5 nor (⇢ 4⇢ 5)⇤ .
(ii) It is sufficient to study the effect of increasing one element of the sequence . If we increase nk to n > n1, then the sequence becomes associative, and the value of 6R is n. Hence, it is sufficient to consider an increase to any value at most n1.
Lemma 1. Let 2 S0. Then 6R is monotonic w.r.t. any element n1 or R = T 1T 2 · · · with T 1 = !⇢ 3. n1 of the sequence, for any rule Proof. Suppose that an element n1 is changed to n01 > n1. Then the new sequence 0 becomes associative and 6R( 0) = n01 > 6R( ). Suppose now that an element n1 is changed to n1 + ✏ n2. Then (p1, m1) is changed to (p1, m1 1), which can only increase the result of 6R, as ⇢ 1, ⇢ 2 are not present in T 1.
Let us start with computation rules with a single term.
Lemma 2. If R has the form (⇢ 4⇢ 5)⇤ ⇢ 1a⇢ b2⇢ 3 then 6R is monotonic.
Proof. Let 2 S0. After the application of (⇢ 4⇢ 5)⇤ only the first term (p1, m1) remains, so that it is enough to study the effect of increasing ±n1. If n1 is increased to n01, then 6R( 0) = n01, and if n1 is increased, this can only increase the result of 6R.
(i) Suppose that R has the form !⇢ 1a⇢ b2⇢ 3 for ! = !0⇢ ⇤4 with !0 2 L (⇢ 4, ⇢ 5). Then R is monotonic if and only if (a, b) = (a, 0), for a 2 { 0, 1}, and !0 = ". (ii) Suppose that R has the form !⇢ 1a⇢ b2⇢ 3 for ! = !0⇢ ⇤5 with !0 2 L (⇢ 4, ⇢ 5) . Then R is monotonic if and only if (a, b) = (0, b), for b 2 { 0, 1}, and !0 = ".
Proof. We show that (i) holds; the proof of (ii) is analogous. To see that the condition is necessary, suppose that (a, b) = (a, 1), where a 2 { 0, 1}. Consider the sequence
1 = (
To see that we must have !0 = ", suppose to the contrary that !0 6= ". Hence, !0 has the form !0 = !00⇢ 5, otherwise we would have !0⇢ ⇤4 = ⇢ ⇤4. Consider the sequences
= (
We now extend our study to rules made of several terms, and we will make use of the two following auxiliary results to simplify our search for nonmonotonic rules.
Lemma 4. Suppose that 6R is not monotonic, and let T 2 L (⇢ 1, . . . , ⇢ 5) such that T R 2 R be in FIF. Then 6T R also is not monotonic.
Proof. Since T R 2 R is in FIF, T = T1T2 · · · Ti · · · is finite and each term Tj has a certificate j . Hence, the composition = 1 2 · · · i · · · is a certificate of T .
Suppose that 6R is not monotonic, and let 0 and 00 be sequences such that 0 < 00 and 6R( 0) > 6R( 00). Consider
the two composite sequences 0 and 00. Clearly, 0 < 00 but
6T R(
0) = 6R( 0) > 6R( 00) = 6T R(
00).
obtained from
but 6R(
n1 to
2 = (
Proof. From Lemma 4 it follows that the condition is sufficient. Conversely, suppose that 6R is monotonic. It suffices to prove that 6⇢ 3R is monotonic and apply k times the result. Consider any sequence = (p1, m1) 1 2 S0. By Lemma 1, 6⇢ 3R is monotonic w.r.t. ±n1. Now, consider 0 obtained by increasing any element in 1. Then
6⇢ 3R( ) when p1 6= m1, otherwise 6⇢ 3R( 0) = 6R( 10)
In the second case, we have 6⇢ 3R( 0) > 6⇢ 3R( ) if p1 = m1 or p1 = m1 1, otherwise 6⇢ 3R( 0) = 6⇢ 3R( ).
Lemma 6. Let R = T 1T 2 · · · be in FIF where T i = !i⇢ 1ai ⇢ b2i ⇢ 3. If there exists k such that
• (ak, bk) = (
Proof. Assuming that R is in FIF, by Lemma 4, we may assume that k = 1.
• Suppose that (a1, b1) = (
6R(
1 by increasing the value n1 to
n|!1|⇢ 5 +2 = 6R(
• The remaining case (a1, b1) = (
Lemma 7. Suppose R = T 1T 2 · · · is in FIF, and that no term contains ⇢ 1 nor ⇢ 2. If there is k
is of the AFT type or equal to ⇢ ↵4 or ⇢ 5 , then 6R is not monotonic.
n|!1|⇢ 5 +2. Clearly, 1 <
2 but 6R(
Proof. By Lemma 4, it suffices to consider the case k = 1. Suppose first that R = !⇢ 3R0 with ! of the AFT type, say ! = ⇢ ↵4 1 ⇢ 51 · · · ⇢ ↵4 t ⇢ 5t . Consider the sequence
= (
In this case, we get 6R( ) = n↵ +2 > n↵ +3 = 6R( 0).
5Here i = 1 if ↵ i > 0, otherwise i = 0. Similarly, ⇠ i = 1 if i > 0, otherwise ⇠ i = 0.
We can now provide a complete description of monotonic rules.
Theorem 2. Let R 2 R be in FIF. Then 6R is monotonic if and only if either
(i) R = ⇢ ⇤3, or
(ii) R = ⇢ 3kT , where T = !⇢ 1a⇢ b2⇢ 3 satisfies the following conditions
• if (a, b) = (
Proof. Let us prove that all rules in (i) and (ii) are monotonic. It was already established that 6⇢ ⇤3 = h·i0 is monotonic. As for (ii), by using Lemma 5, it suffices to prove monotonicity for R = T , which is obtained by Lemmas 2 and 3. It remains to prove that no other rule is monotonic. As rules are in FIF, no term can exist after T . Moreover, by Lemmas 6 and 7, no term of the form T 0 = !0⇢ 1a0 ⇢ b20 ⇢ 3 with !0 2 L (⇢ 4, ⇢ 5) finite can occur before T or before ⇢ 3k. Furthermore, by Lemma 3, it is not possible to add a finite !0 2 L (⇢ 4, ⇢ 5) before T . Thus, every monotonic rule must be of one of the stated forms, and the proof of Theorem 2 is now complete.