Pablo Barenbaum
email: pbarenbaum@dc.uba.ar.

Verónica Becher
email: vbecher@dc.uba.ar.

Alejandro Deymonnaz

Melisa Halsband
email: mhalsband@dc.uba.ar.

Pablo Ariel Heiber
email: pheiber@dc.uba.ar.

Efficient repeat finding in sets of strings via suffix arrays

Keywords: stringology, repeats, suffix array, longest maximal substring

We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O(m) memory, where m is the length of the longest input string, and O(n log m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive part of our algorithms is the computation of several suffix arrays. We give an implementation and experimental results that evidence the efficiency of our algorithms in practice, even for very large inputs.

Introduction

The difficulty of finding repeats within a set of strings, as opposed to within a single string, is that the size of the input can grow significantly. A typical setting happens when the total size of the set exceeds the available memory, while each element in the set fits in it. One would like a solution that does not rely on secondary memory and has an acceptable, close to linear, running time. In this paper we address two problems relative to sets of strings:

(a) Find the largest substrings that occur in every string of a given set. (b) Find the maximal repeats in a given string that occur in no string of a given set. We consider the variants of this second problem for two notions maximality: one is maximality with respect to the substring relation; the other says that a repeat is maximal if any of its extensions occur fewer times.

We define a data structure that allows us to solve these problems efficiently. It stores which substrings of a given string occur in all the elements of a set, and which occur in none. To build this structure no more than two strings are processed at the same time. Our algorithms are based on the suffix array construction [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] and require O(n log m) time and O(m) memory, where n is the size of the input (sum of the all the strings' lengths) and m is the length of the longest input string. The most expensive part of our algorithms is the computation of several suffix arrays. The use of suffix trees instead of suffix arrays may lower the asymptotic time complexity bounds to be linear on n. However, as it is widely known, the large constants associated to the suffix tree construction make the suffix array approach better in most cases. For comparison on the theoretical and practical utility of both structures see [START_REF] Ibrahim Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF][START_REF] Puglisi | A taxonomy of suffix array construction algorithms[END_REF].

To our knowledge, no non-trivial solution has been proposed for this exact problem. However, a very related problem on sets of strings, also solved with suffix arrays, is treated by Babenko and Starikovskaya in [START_REF] Babenko | Computing longest common substrings via suffix arrays[END_REF]. They tackle, in an ingenious way, the problem of finding the longest repeat that appears in at least k strings of a set, for each k. Their algorithm, however, requires to store all strings simultaneously in memory, yielding a O(n) memory requirement and O(n log n) time. In contrast, our algorithms just require the suffix arrays of pairs of strings and thus have lower time and memory bounds.

The problems we solve in this paper were motivated by applications in comparative genomic sequence analysis, where the huge volume of the input data and the abundance of repeated subsequences demand algorithms that are efficient in the trade-off complexity of time and memory. Nevertheless, applications for cross-search on sets of strings arise naturally in the context of text search applications. While heuristics are the usual tool to tackle this problems in massive real life applications like search engines, research of efficient exact solutions is of interest, at least to provide a basis for comparison, but also to eventually combine the new techniques and ideas found with the methods used in practice. Applications in genomics also rise interesting open questions regarding how to incorporate the possibility of errors in the data, thus requiring inexact matching algorithms.

In the last section, we describe an implementation of our algorithms and their performance on real datasets, including various possible scenarios such as genomic data, source code and literary work.

Notation and definitions

Notation. Assume the alphabet A, a finite set of symbols. A string is a finite sequence of symbols in A. The length of a string w, denoted by |w|, is the number of symbols in w. We address the positions of a string w by counting from 1 to |w|. The symbol in position i is denoted w[i], and w[i..j] represents the substring of length j -i + 1 that starts in position i of w. We say u is a substring of w if u = w[i..j] for some i, j. If u is a substring of w we say that u occurs in w at position

i if u = w[i..i + |u| -1]. A prefix of a string w is an initial segment of w, w[1..i]; a suffix of w is a final segment w[i..|w|].
When u is a substring of w we call w an extension of u. Given a string w and a set of strings X, we say that w occurs in X if w is a substring of some x ∈ X.

Maximal repeats

We use the nomenclature given by Gusfield [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF], and extend it to definitions over sets of strings. We use a different language than that on Gusfield's book, however, the definitions are equivalent.

Definition 1 (Maximal and supermaximal repeats [5])

1. A maximal repeat in a string w is a substring that occurs more than once in w, and each of its extensions occur fewer times in w. 2. A supermaximal repeat in a string w is a substring that occurs more than once in w, and each of its extensions occur at most once in w.

Definition 2 (Supermaximal repeat in a set, exclusive maximal and supermaximal repeat)

1. Given a set X with at least two strings, a supermaximal repeat in X is a substring of each x ∈ X, such that none of its extensions occur in every x ∈ X. 2. Given a string w and a set of strings X, an exclusive maximal (respectively supermaximal) repeat in w with respect to X is a maximal (respectively supermaximal) repeat in w that does not occur in X.

Example 3

The maximal repeats in w = abcdeabcdf bcde are abcd, bcde, and bcd. Clearly abcd and bcde are maximal repeats, occurring twice. But also bcd is a maximal repeat because it occurs three times in w, and every extension of bcd occurs fewer times. There are no other maximal repeats in w (bc, for example, occurs three times, but since bcd occurs the same number of times, bc is not a maximal repeat). Of these, only abcd and bcde are supermaximal repeats. The only exclusive maximal repeat in w = abcdeabcdf bcde with respect to S = {f abcd, bcdf, abce} is bcde, which is also the only exclusive supermaximal repeat.

There is just one supermaximal repeat in S, the string bc.

This example already shows that maximal repeats can be nested and overlapping, and the same applies to exclusive maximal repeats. Supermaximal repeats (in a set and exclusive), however, can be overlapping but not nested. Theorem 4 ([5], Theorem 7.12.1) The number of supermaximal repeats in a string is less than or equal to the number of maximal repeats in a string, which is, in turn, less than or equal to the string length.

Proposition 5

The set of exclusive maximal (respectively supermaximal) repeats in a given string w with respect to any set of strings, is included in the set of maximal (respectively supermaximal) repeats of w.

Proof: Immediate from the definitions. ✷ Proposition 6

1. The number of supermaximal repeats in a set of strings is not greater than the minimum of all string lengths. 2. The number of exclusive maximal (respectively supermaximal) repeats in a given string with respect to a set is not greater than the string length.

Proof: Supermaximal repeats occur in every string in the given set, and they can not be nested with other supermaximal repeats. This means that at each position in a given string in the set, at most one supermaximal repeat starts. Hence, the length of a shortest string in the set gives an upper bound to the total number of supermaximal repeats; this proves point 1. Point 2 is immediate from Theorem 4 and Proposition 5. ✷

Suffix array and Longest Common Prefix

Let w be a string of length n = |w|. The suffix array [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] of w is a permutation r of the indices 1...n such that for each i < j, w[r[i].

.n] is lexicographically less than w[r[j]..n]. Thus, a suffix array represents the lexicographic order of all suffixes of the input w. For convenience, sometimes we also store the inverse permutation of r and call it p, namely, p[r[i]] = i. In our procedures, we use the fast algorithm of Larsson and Sadakane [START_REF] Larsson | Faster suffix sorting[END_REF] to build suffix arrays of some of the strings of the input. This algorithm profits from the fact that the elements to be ordered are suffixes. Its worst case time complexity is O(n log n).

Each substring of w can be seen as a prefix of a suffix of w. Suppose a maximal repeat u occurs k times in w; then, it is a prefix of k different suffixes of w. Since the suffix array r records the lexicographical order of the suffixes of w, the maximal repeat u can be seen as a string of length |u| addressed by k consecutive indices of r. Namely, there will be an index i such that u occurs at positions r[i], r[i + 1],..., and r[i + k -1] of w (see [START_REF] Becher | Efficient repeat finding via suffix arrays[END_REF] for a detailed analysis of this point).

We write lcp(u, v) to denote the length of the longest common prefix of the strings u and v. We use the linear time algorithm of Kasai et al. [START_REF] Kasai | Linear-time longestcommon-prefix computation in suffix arrays and its applications[END_REF] to compute the lcp value of each pair of consecutive suffixes of w in the lexicographic order. This elegant algorithm builds the LCP (Longest Common Prefix) array by examining the suffixes of the input w in decreasing length order, and by comparing each suffix to its adjacent entry on the suffix array.

Definition 7 For each position 1 ≤ i < n, LCP [i] = lcp(w[r[i]..n], w[r[i + 1]..n]). Proposition 8 For any i, j such that 1 ≤ i < j ≤ n, lcp(w[r[i]..n], w[r[j]..n]) = min{LCP [k] : i ≤ k < j}. Proof: Let t = lcp(w[r[i]..n], w[r[j]..n]). Since r is lexicographically sorted, the longest common prefix of w[r[i]..n] and w[r[j]..n] is also a prefix of each suffix in between. Therefore, LCP [k] ≥ t for each k in range [i, j]. By way of contradiction, assume that for all such k, LCP [k] > t. Consider the pairs of strings w[r[k]..r[k]+t] and w[r[k +1]..r[k +1]+t] of length t+1. Since LCP [k] ≥ t+1, all these pairs are equal, so, the strings w[r[i]..r[i]+t] = w[r[j]..r[j]+t] are equal, which contradicts t = lcp(w[r[i]..n], w[r[j]..n]).
Thus, the fact that for all k, LCP [k] > t is false, hence, there is at least one k for which LCP

[k] = t. ✷ Proposition 9 1. If lcp(w[r[i]..n], w[r[i + k]..n]) < lcp(w[r[i]..n], w[r[i + j]..n]) then j < k. 2. If lcp(w[r[i]..n], w[r[i -k]..n]) < lcp(w[r[i]..n], w[r[i -j]..n]) then j < k. Proof: For point 1, by Proposition 8, lcp(w[r[i]..n], w[r[i + j]..n]) = min{LCP [t] : i ≤ t < j} and lcp(w[r[i]..n], w[r[i + k]..n]) = min{LCP [t] : i ≤ t < k}. If j ≥ k,
the set in the second equality is included in the set in the first one, so the minimum of the first set is not greater than the minimum of the second. Point 2 is analogous. ✷

The base algorithm

The two problems, supermaximal repeats in a set and exclusive supermaximal/maximal repeats in a string with respect to a set, are dual in the sense that the first requires a maximal string occurring in each string in the set, while the second requires a maximal string occurring in no string in the set. To solve both problems we use a base algorithm longest common substring, which takes two input strings w and s and outputs an integer array of length |w|. This array indicates for each suffix of w, the length of its longest prefix occurring in s.

Definition 10 Given two strings w and s, for

1 ≤ i ≤ |w|, m[i] = max{ℓ : w[i..i + ℓ -1] occurs in s}.
Proposition 11 Given two strings w and s, for

1 ≤ i ≤ |w|, m[i] = max{lcp(w[i..|w|], s[j..|s|]) : 1 ≤ j ≤ |s|}.
Proof: Immediate from the definitions. ✷

We write w$s for the concatenation of w and s having a separator symbol $ not in alphabet A, and let r now be the the suffix array of w$s. We use Proposition 9 applied to w$s to find the suffix of s having the longest common prefix with the suffix of w addressed by index i in r: it is addressed by closest index to i (upwards or downwards) that corresponds to a suffix of s.

Proposition 12 Let r be the suffix array of w$s. If i is an index of w in r then m[r[i]] = max(up i , down i ) where

up i = lcp(w$s[r[i]..|w|], w$s[r[i -j]..|w| + |s| + 1]) for j the lowest value such that i -j is an index of s in r. down i = lcp(w$s[r[i]..|w|], w$s[r[i + k]..|w| + |s| + 1]
) for k the lowest value such that i + k is an index of s in r (let each of them be 0 when such j or k does not exist).

Proof: Follows directly by Proposition 9 and Proposition 11. ✷ Algorithm 1 computes the array m by scanning the LCP array built from the suffix array of the string w$s. Observe that the longest common substrings between w and s can be obtained by iterating over the array m, reporting the positions that these common substrings have in string w.

An algorithm for supermaximal repeats in a set

Since supermaximal repeats in a set of strings X (cf. Definition 2) are substrings occurring at least once in each x ∈ X, it is convenient to select a shortest string in X, called w from now on, and use it as base string for the algorithm. The idea is to iterate through each position of w checking whether a maximal repeat starts or not in the current position (see Proposition 6). From now on, we will then work on a set of the form X ∪ {w} where we assume the set X does not include w and that w is not longer than any of the strings on X. We will compute the supermaximal repeats in the set X ∪ {w}.

Each supermaximal repeat is a prefix of a suffix of w, that also occurs in every x ∈ X but such that any extension fails to occur in some x ∈ X. We use an array N of length |w| to indicate, for each position i of w, the length of the longest prefix of the suffix w[i..n] that also occurs in every x ∈ X.

Definition 13 For 1 ≤ i ≤ |w|, N [i] = max{ℓ : w[i...i + ℓ -1] occurs in every x ∈ X}.
The pseudocode to construct this array is given in Algorithm 2, and we call it minimum length. It calls the previously introduced longest common substring (Algorithm 1) for the base string w and each element of X, keeping always the smaller values. The whole N array is initialized with the length of each suffix of w, that is |w| -i + 1.

For notational convenience we introduce this definition.

Definition 14 Let w (i) = w[r[i]...r[i] + N [r[i]] -1].
Clearly, all supermaximal repeats are among the w (i) 's. In order to find the actual supermaximal repeats we will filter out the w (i) 's that are not.

i := 2 to |w$s| -1 such that r[i] is an index in w do if r[i -1] is an index in w then m[r[i]] := min(m[r[i -1]], LCP [i -1]) else -r[i -1] is an index in s- m[r[i]] := LCP [i -1] end if
end for -calculate acc = up i as before and then update m 1. For all i, w (i) occurs in every x ∈ X ∪ {w}. 2. Every supermaximal repeat in X ∪ {w} is of the form w (i) for some i, 1 ≤ i ≤ |w|.

for i := |w$s| -2 to 1 such that r[i] is an index in w do if r[i + 1] is an index in w then acc := min(acc, LCP [i])) else -r[i + 1] is an index in s- acc := LCP [i] end if m[r[i]] := max(m[r[i]],
Proof: Immediate from Definitions 2, 13 and 14. ✷

Given the array N for the selected w, we define an equivalence relation on the indices of the suffix array r of w, such that contiguous indices with the same value in N define an equivalence class.

Definition 16 i ≡ † j ⇔ ∀k ∈ [min(i, j), max(i, j)] N [r[i]] = N [r[k]].
Proposition 17 ≡ † is an equivalence relation on [1..n].

Proof: Reflexivity and Symmetry: Immediate from definition. Transitivity: Suppose i ≡ † h and h ≡ † j. If h ∈ [i, j] then transitivity follows directly. Otherwise, without loss of generality assume i ≤ h ≤ j.

Then N [r[i]] = N [r[k]] ∀k ∈ [i, h] and N [r[h]] = N [r[k]] ∀k ∈ [h, j]. Since h is in both intervals, N [r[i]] = N [r[h]] = N [r[k]], ∀k ∈ [i, j].
✷

We now refine the relation ≡ † and define the relation ≡ ‡ . It groups the indices that address consecutive suffixes of w in r whose longest common prefix is greater than the maximum allowed by the values of N . It will sub-partition each equivalence class of ≡ † so that the longest common prefix of any two elements in the new partition is longer than the N value of the class, keeping all the elements in the new equivalence classes consecutive in r.

Definition 18 i ≡ ‡ j ⇔ i ≡ † j and ∀k ∈ [min(i, j), max(i, j) -1] LCP [k] ≥ N [r[i]].
Proposition 19 ≡ ‡ is an equivalence relation on [1..|w|].

Proof: Reflexivity and Symmetry: Immediate from definition. Transitivity: Suppose i ≡ ‡ h and h ≡ ‡ j. If h ∈ [i, j] then transitivity follows directly. Otherwise, without loss of generality assume i ≤ h ≤ j. This implies i ≡ † h and h ≡ † j, therefore i ≡ † j. Thus, the value of

N [r[k]] is the same for every k ∈ [i, j]. Since ∀k ∈ [i, h -1], LCP [k] ≥ N [r[k]] and ∀k ∈ [h, j -1], LCP [k] ≥ N [r[k]], then ∀k ∈ [i, h -1] ∪ [h, j -1], LCP [k] ≥ N [r[k]]. We conclude i ≡ ‡ j. ✷
Observation 20 Each equivalence class defined by ≡ † or ≡ ‡ is an integer interval.

From the previous observation, we can name the equivalence classes as integer intervals.

Lemma 21 For each equivalence class

[i, j] of ≡ ‡ , w (i) = w (k) , ∀k ∈ [i, j]. Proof: If i ≡ ‡ j then N [r[i]] = N [r[k]], ∀k ∈ [i, j]. Furthermore, if i ≡ ‡ j, LCP [k] ≥ N [r[i]], for i ≤ k < j.
Therefore, all the suffixes addressed by the interval r[i...j] share, at least, their first N [r[i]] symbols. ✷

We base our algorithm on the following characterization.

Definition 22 A substring of w is supermaximal to the left (respectively right) iff it occurs in every x ∈ X ∪ {w} and none of its extensions to the left (respectively right) occur in every x ∈ X ∪ {w}.

Observation 23 A substring of w is supermaximal iff it is supermaximal to the left and supermaximal to the right.

Lemma 24 For an equivalence class [i, j] defined by ≡ ‡ , w (i) is supermaximal to the right if and only if the following two conditions hold:

1. i = 1 or LCP [i -1] < N [r[i]] 2. j = n or LCP [j] < N [r[j]] Proof: If w (i) is supermaximal to the right, it is not a prefix of any other string w (k) with k ∈ [i, j].
In particular, it is not a proper prefix of w (i-1) nor w (j+1) (when they exist). It is also not equal to w (i-1) nor w (j+1) , because otherwise they would be in the same equivalence class. Therefore, the length of the common prefix of w (i) with w (i-1) or w (j+1) is strictly less than its length. Now, if w (i) is not supermaximal to the right, then there is some extension to the right. This extension is either supermaximal, or can be extended to a supermaximal substring. Therefore, there is some supermaximal repeat that extends w (i) to the right. By Observation 15, there is some k such that w (k) extends w (i) to the right, so its length

N [r[k]] > N [r[i]]. By Lemma 21, k ∈ [i, j]. Since w (k) extends w (i) , lcp(w (k) , w (i) ) = N [r[i]]. There are two cases: Case k < i. Since k < i, we have i = 1. Using Proposition 8 we get N [r[i]] = lcp(w (k) , w (i) ) and lcp(w (k) , w (i) ) ≤ lcp(w[r[k]..|w|], w[r[i]..|w|]) = min{LCP [l] : k ≤ l < i}, so LCP [i -1] ≥ N [r[i]].
This case, then, implies the negation of the first condition.

Case k > j analogously implies the negation of the second condition. ✷ Lemma 25 For an equivalence class [i, j] defined by ≡ ‡ , let w (i) be supermaximal to the right. Then, w (i) is also supermaximal to the left if and only if ∀k ∈ Proof: The equivalence between 1 and 2 follows from the definition of M and the already mentioned properties of the occurrences of a maximal (respectively supermaximal) repeat. It is trivial that 2 implies 3, because it is a particular case. We can also see that 3 implies 2, because if M [r[i]] < |s|, then s does not occur in any x ∈ X, and then M [k] < |s| for any position k at which s occurs in w. ✷

[i, j], r[k] = 1 or N [r[k] -1] ≤ N [r[k]].
Our algorithms findmaxr and findsmaxr, presented in [START_REF] Becher | Efficient repeat finding via suffix arrays[END_REF][START_REF] Becher | Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome[END_REF], report each repeat (respectively maximal and supermaximal) in a concise way, indicating the index in r of its first occurrence i, the number of repetitions k and the length of the repeat ℓ. Given the aforementioned results, to filter out the non exclusive repeats, all that is needed is to report the repeats such that M [i] < ℓ.

Correctness of the two modified algorithms follow directly from the correctness of the cited algorithms and the results above.

Complexity of the algorithms

As it is usual in the literature on algorithms, we express the time and space complexity assuming integer values can be stored in a unit, and integer additions and multiplications can be done in O(1). These assumptions make sense because the integer values involved in the algorithms fit into the processor word size for practical cases. Although our algorithms are scalable for any input size, the derived complexity bounds are guaranteed only if the input size remains under the machine addressable size. Otherwise, the classical logarithmic complexity charge for each integer operation becomes mandatory.

We now prove that the algorithms presented in the previous sections, supermaximal repeats in a set and exclusive maximal/supermaximal repeats in a string with respect to a set, require O(n log m) time and O(m) memory, where n is the sum of the all strings' length in the input, and m is the length of the longest input string.

To bound the time complexity of our algorithms we use that the output can be represented in a concise way, as follows:

Proposition 29 Given a set of strings X.

1. The set of all supermaximal repeats in X is representable in space O(min{|x| : x ∈ X}).

The set of all exclusive maximal or supermaximal repeats in w with respect to X and all their occurrences is representable in space O(|w|).

Proof: We argue first for Point 2. As stated in Proposition 6, exclusive maximal/supermaximal repeats in w are a subset of the maximal/supermaximal repeats in w, which are representable in space O(|w|), cf. [START_REF] Becher | Efficient repeat finding via suffix arrays[END_REF].

For the sake of completeness in the complexity argument we include the proof. Each reported maximal repeat and all its occurrences can be represented with three unsigned integers: an index i in the suffix array r, a length ℓ, and the number of occurrences k. The reported maximal repeat is the prefix of length ℓ of the suffix at position r[i]. Its k occurrences are respectively in positions r[i],..,r[i + k -1]. Each of these integers is at most |w| (where |w| is at most the maximum addressable memory) and we need at most |w| of them (Proposition 6). Assuming that these integer values can be stored in fixed number of bits, this output requires size O(|w|). Finally, we need to store the suffix array r, which contains |w| integer values that are a permutation of 1..|w|, so it also requires O(|w|). The input w also takes O(|w|) space, since each symbol in A also takes O(1) because |A| ≤ |w|.

Point 1 is analogous, each repeat is reported by giving an interval in the suffix array (two integers) and a length. Notice that to report the repeats in a set X our algorithm mrset uses a witness string in X, and only reports the lengths and positions of maximal repeats in it, instead of reporting also the occurrences in each of the strings in X. ✷

Of course, if instead of charging a fixed number of bits to store an integer, we count the length of its bit representation, the total needed output space to report all maximal repeats and occurrences in a given input string of length n bits becomes O(n log n). The input in this case would have an O(n log |A|) bound, which has O(n log n) as worst case, but probably takes a lot less because alphabet sizes are usually small compared with n. For maximum length, on the other hand, while |w| could be greater than |x| for some x ∈ X, we can ensure the given bounds by considering a variant of the set X: Group the elements in X in a greedy way to define a new set Y composed of the concatenation (with a separator) of as many as possible elements of X up to length at most m. It is easy to see that at most one element of Y will have a length lower than m/2 (otherwise, we can still concatenate those elements). It is also clear that occurring in X is equivalent to occurring in Y , so the problems of computing the algorithms with respect to X or to Y are equivalent. (sum of all needed constructions), LCP array calculation, minimum/maximum array calculation (both take the same time), findmaxr and findsmaxr each with the filter maximum length, and mrset.

The experiments confirm the theoretical complexity bounds. The times in first three columns of Table 2 are bounded by the total size of the set, while the last three are bounded by the size of the base (considerably smaller in most cases). The first column, suffix array constructions, accounts for most of the total time because it is the only superlinear time. Of the last three columns, findmaxr is the slowest, also due to the extra log factor. As a final comment, note in the linux-cs and linux-hs set, the time increase when choosing a large file as the base. This difference in practice illustrates the need to choose a short base (for mrset) or to do the concatenation trick in the complexity bounds proof (for the maximum length filter).

Algorithm 1

 1 longest common substring (input: string w, string s, output: array m) Initialize array m[1..|w|] in 0 r := suffix array of w$s LCP := longest common prefix array of w$s -set M [r[i]] = down i by using Propositions 8 and 12.

  for

  acc) end for Algorithm 2 minimum length(input: string w, set of strings X, output: array N ) Initialize array N [1..|w|] such that N [i] = |w| -i + 1 for each x ∈ X do m := longest common substring(w, x) for i := 1 to |w| do N [i] := min(N [i], m[i]) end for end for Observation 15

Algorithm 4

 4 maximum length(input: string w, set of strings X, output: array M ) Initialize array M [1..|w|] in 0 for each x ∈ X do m := longest common substring(w, x) for i := 1 to |w| do M [i] := max(M [i], m[i]) end for end for 1. A string s is an exclusive maximal (respectively supermaximal) repeat of w with respect to set X. 2. s is a maximal (respectively supermaximal) repeat in w with k occurrences, for some k ≥ 2, in positions r[i], ..., r[i + k -1], and the length of s is greater than each of M [r[i]], .., M [r[i + k -1]]. 3. s is a maximal (respectively supermaximal) repeat in w, one of its occurrences is in position r[i] and the length of s is greater than M [r[i]].

Proposition 30 1 .

 301 For two given strings w and s, longest common substring (Algorithm 1) requires time O(n log n) and space O(n), where n = |w| + |s|. More specifically, the total memory required is bounded by (|w| + |s| + 1)(2 word size + log |A|) + |w|word size + O(1) bits. Proof: Consider Algorithm 1. Its input is stored in exactly (|w| + |s|) log |A| bits. The suffix array r of w$s, and its LCP array require |w$s| word size memory each. The suffix array takes O(n log n) to be calculated, and the LCP array takes O(n). The output array has length |w|. No other data structures are used, and the auxiliary variables are accounted for in the O(1) term. In the for loops the condition of r[i] being an index in s or w can be checked in O(1) by comparing r[i] with |w|. Hence, the total time of Algorithm 1 is O(n log n). ✷ Proposition 31 Let w be a string and let X be a set of strings. If |w| < min{|x| : x ∈ X}, minimum length (Algorithm 2) can be implemented to construct array N in time O(n log m), and requires (|w| + m) (2 word size + log |A|) + 2 |w| word size + O(1) bits of memory, where n = x∈X∪{w} |x| and m = max{|x| : x ∈ X ∪ {w}}. 2. maximum length can be implemented to construct array M with the same time and memory bounds. Proof: The output array N or M and the auxiliary array m require, each, |w| word size bits. For each x ∈ X, the computation of longest common substring temporarily requires constant space for local variables plus (|w| + |x|)(2 word size + log |A|) bits of memory. Thus, total memory space required is (m + |w|) (2 word size + log |A|) + 2 |w| word size + O(1) bits, where m = max{|x| : x ∈ X ∪ {w}}. The upper bound for the needed time is the sum of the time required by Algorithm 1 with arguments w, and x, for each x ∈ X. This is O( x∈X (|w| + |x|) log(|w| + |x|)). For minimum length, the additional hypothesis |w| < min{|x| : x ∈ X} implies a time bound of O(n log m).

  Finally, y∈Y ∪{w} (|w| + |y|) log(|w| + |y|)) = O(|Y |m log m) = O( n m/2 m log m) = O(n log m). ✷ Theorem 32 mrset (Algorithm 3) computes the supermaximal repeats in a set Y in time O(n log m) and O(m) memory, where n = y∈Y |y| and m = max{|y| : y ∈ Y }. More precisely, it requires (m + |w|)(2 word size + log |A|) + 2 min{|y| : y ∈ Y }word size + O(1) bits of memory, where w is a shortest string in the set.

Acknowledgments

We thank the anonymous referees for their comments and suggestions. The group has received support from Biosidus and IBM Argentina.

Proof: Assume w (i) supermaximal to the right. There is no extension to the right of w (i) that occurs in every the element of X. Then, there is no other equivalence class [i ′ , j ′ ] such that w (i) is a proper prefix of w (i ′ ) . Thus, there is also no other class [i ′ , j ′ ] such that w (i) = w (i ′ ) , because those two classes can not be neighbors (otherwise they would be the same class) and can not be separated because of the lexicographic ordering and the previous claim. Then, all the occurrences of w (i) in w are addressed by the indices in r in the equivalence class [i, j].

For the left to right implication assume there is k in k) to the left. Since u occurs in every x ∈ X ∪ {w} (by definition of N ), w (k) is not supermaximal to the left. Conversely, assume w (i) is not supermaximal to the left. Then, there is an extension of one symbol to the left, that occurs in every x ∈ X. Let us call that extension u and assume it occurs at position t in w. Then, w (i) occurs at position t + 1, and therefore, as proved in the first paragraph, there is k

Theorem 26 Algorithm 3, called mrset, computes the supermaximal repeats in a given set.

Proof: Algorithm 3 iterates through all equivalence classes of ≡ ‡ (Definition 18). The first conditional filters out exactly the substrings that are not maximal to the right, and the second the ones that are not maximal to the left, according to Lemmas 24 and 25. Since all supermaximal repeats in a set must be of the form w (i) (by Observation 15), the algorithm reports all possible repeats, as wanted. ✷

An algorithm for exclusive supermaximal/maximal repeats

To obtain the exclusive maximal or supermaximal repeats in a given string w with respect to a set X, we compute the maximal or supermaximal repeats in w and filter out those that occur in some x ∈ X (cf. Definitions 1 and 2). We use an array M to store, for each position i in w, the length of the longest prefix of w[i.

.n] that occurs in some x ∈ X. That is, for each i, w

Algorithm 4, called maximum length, gives the pseudocode of how to construct the array M using longest common substring (Algorithm 1) and updating it for each element of X, keeping always the larger values. It is to dual to minimal length (Algorithm 2), because it replaces min with max, and the whole array M is initialized in 0.

Proposition 28 Let r be the suffix array of a string w, and let M be the array as in Definition 27 for a given set X. The following conditions are equivalent: Proof: Consider Algorithm 3. Let w be the smallest element in Y and let X = Y \ {w}. The total time is the sum of the time to compute the three data structures N , r and LCP , plus the time needed by the for loop. By Proposition 31, minimum length(w, X) computes N in time O(n log m). This subsumes the O(|w| log |w|) time needed for the suffix array r plus the linear time for the LCP . Since equivalence classes in ≡ ‡ are intervals, cf. Observation 20, the for loop can iterate through the indices in increasing order, and check the partitions in linear time. The check for each k inside the for loop has also one check for each index, so it is still linear overall. All the other instructions in the loop take time O(1), hence, the for loop requires only time linear in |w|. The needed memory is the maximum between: the space for the data structures N, r, LCP and the input w, and the memory required by minimum length(w, X). This, using Proposition 31, is constant space plus the maximum between |w| (

Implementation and Experiments

We implemented all algorithms in C (ANSI C99), for a 32 or 64 bits machine. The complete source code of the algorithms and an example tool to run them can be downloaded from http://www.dc.uba.ar/people/profesores/becher/software/findrepset.tar.bz2.

We tested this implementation on large inputs, using an Intel R Core TM 2 Duo E6300 (only one core), running at 1.86GHz with 8GB RAM (DDR2-800) under Ubuntu linux for 64 bits. The programs were compiled with the GCC compiler version 4.2.4, with option -O2 for normal optimization.

We performed tests on the input files described in Table 1. We used the Canterbury corpus (i) and the human genome NCBI 36.49 FASTA files (ii) with headers, enters, and unknown base marks (letter N) removed.

Each run consists on a set with an element selected to be the base. In the case of exclusive maximal or supermaximal repeats, the base is the string in which the repeats are searched. For supermaximal repeats in a set, any element can be selected as the base string and the same result is obtained, but size of the chosen element greatly affects the running time, see the introduction in section 4 and the proof of Theorem 32. We tried both the largest and smallest elements as bases to compare. The reported times are user times, counting only the time consumed by the algorithm, not including the needed time the load the input from disk. In Table 2 we describe each run and the aggregated time for each part of the process: suffix-array constructions (i) http://corpus.canterbury.ac.nz/descriptions/#cantrbry (ii) ftp://ftp.ensembl.org/pub/release-49/fasta/homo sapiens/dna/


Josef Šlapal
email: slapal@fme.vutbr.cz.

Topological structuring of the digital plane

Keywords: digital plane, quotient topology, Khalimsky topology, Jordan curve

We discuss an Alexandroff topology on Z 2 having the property that its quotient topologies include the Khalimsky and Marcus-Wyse topologies. We introduce a further quotient topology and prove a Jordan curve theorem for it.

Introduction

In the classical approach to digital topology (see e.g. [START_REF] Rosenfeld | Digital topology[END_REF] and [START_REF] Rosenfeld | Picture Languages[END_REF]), graph theoretic tools are used for structuring Z 2 , namely the well-known binary relations of 4-adjacency and 8-adjacency. But neither 4adjacency nor 8-adjacency itself allows an analogue of the Jordan curve theorem (cf. [START_REF] Kong | A topological approach to digital topology[END_REF]) and, therefore, one has to use a combination of the two adjacencies. To overcome this disadvantage, a new, purely topological approach to the problem was proposed in [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] which utilizes a convenient topology on Z 2 , called the Khalimsky topology (cf. [START_REF] Khalimsky | On topologies of generalized segments[END_REF]), for structuring the digital plane. At present, this topology is one of the most important concepts of digital topology. It has been studied and used by many authors, see e.g. [START_REF] Eckhardt | Topologies for the digital spaces Z 2 and Z 3[END_REF] and [START_REF] Khalimsky | Boundaries in digital planes[END_REF]- [START_REF] Kopperman | A Jordan surface theorem for three-dimensional digital spaces[END_REF].

The possibility of employing convenient topological structures on Z 2 different from the Khalimsky topology is discussed in [START_REF]Closure operations for digital topology[END_REF]- [START_REF]A Jordan curve theorem in the digital plane[END_REF]. Particularly, in [START_REF]Digital Jordan curves[END_REF], a new topology on Z 2 is introduced and it is shown there that this topology provides certain convenient Jordan curves behaving more advantageously than the Jordan curves in the Khalimsky space. The quotient topologies of the topology from [START_REF]Digital Jordan curves[END_REF] are studied in [START_REF]A quotient-universal digital topology[END_REF] where it is shown that they include, among others, the Khalimsky and Marcus-Wyse topologies. In the present note we continue the investigations from [START_REF]Digital Jordan curves[END_REF] and [START_REF]A quotient-universal digital topology[END_REF]. We discuss a topology on Z 2 which is finer than the topology introduced in [START_REF]Digital Jordan curves[END_REF] but still has the property that the Khalimsky and Marcus-Wyse topologies belong to its quotient topologies. We study another of its quotient topologies on Z 2 , denoted by v, and prove a Jordan curve theorem for it. This Jordan curve theorem differs from the Jordan curve theorems for the Euclidean plane, the Khalimsky plane, and the [START_REF] Engelking | General Topology[END_REF][START_REF] Kiselman | Digital Jordan curve theorems[END_REF] and [START_REF] Kiselman | Digital Jordan curve theorems[END_REF][START_REF] Engelking | General Topology[END_REF] digital planes of "classical" digital topology in the following significant ways:

(i) The paper's Jordan curve theorem only applies to certain simple closed curves in (Z 2 , v). There are arbitrarily long simple closed curves C in (Z 2 , v) for which Z 2 \ C has more than two components.

(ii) Those simple closed curves C in (Z 2 , v) to which the paper's Jordan curve theorem applies will in most cases not be the common boundary of the two components of Z 2 \ C.

Preliminaries

For the topological terminology used we refer to [START_REF] Čech | Topological Spaces (Revised by Z.Frolík and M.Katětov)[END_REF] and [START_REF] Engelking | General Topology[END_REF]. Throughout the note, all topologies dealt with are thought of as being (given by) Kuratowski closure operators. Recall that a topology p on a set X is said to be a T 1 2 -topology if each singleton subset of X is closed or open (so that T 1 2 implies T 0 ), and it is called an Alexandroff topology if pA = x∈A p{x} whenever A ⊆ X. A pair (X, p) where X is a set and p is an Alexandroff topology on X is called an Alexandroff space. Recall also that, given topological spaces (X, p) and (Y, q), a surjection e : X → Y is said to have connected fibres if e -1 ({y}) is connected (in (X, p)) for every point y ∈ Y .

If we omit, in the definition of Kuratowski closure operators (Kuratowski closure spaces), the requirement of idempotency, we obtain the so-called pretopologies (pretopological spaces) -cf. [START_REF] Čech | Topological Spaces (Revised by Z.Frolík and M.Katětov)[END_REF]. We will use some concepts naturally extended from topologies (topological spaces) to pretopologies (pretopological spaces). Given pretopologies p 1 , p 2 on a set X, we say that p 1 is finer that p 2 if p 1 (A) ⊆ p 2 (A) for every subset A ⊆ X. A map f : (X, p) → (Y, q), where (X, p) and (Y, q) are pretopological spaces, is called continuous if f (pA) ⊆ q(f (A)) for every A ⊆ X. Let e : X → Y be a surjection and p be a pretopology on X. Then the finest pretopology q on Y such that e : (X, p) → (Y, q) is continuous is called the quotient pretopology of p generated by e.

Of course, if a quotient pretopology of a topology p (generated by a surjection e) is a topology, then it is a quotient topology of p (generated by e). The proof of our main theorem will be based on a result (Proposition 4.1) about such quotient topologies of Alexandroff topologies.

By a graph on a set V we always mean an undirected simple graph without loops with the vertex set V . Recall that a path in a graph is a finite (nonempty) sequence x 0 , x 1 , ..., x n of pairwise different vertices such that x i-1 and x i are adjacent (i.e., joined by an edge) whenever i ∈ {1, 2, ...n}. Here, x 0 and x n are said to be the end vertices of the path. By a cycle in a graph we understand any finite set of at least three vertices which can be ordered into a path with the end vertices adjacent.

The connectedness graph of a topology p on X is the graph on X in which a pair of vertices x, y are adjacent if and only if x = y and {x, y} is a connected subset of (X, p). Let p be an Alexandroff topology on a set X. Then it is obvious that a subset A ⊆ X is connected in (X, p) if and only if each pair of points of A may be joined by a path in the connectedness graph of (X, p) contained in A. In the sequel, only connectedness graphs of connected Alexandroff topologies on Z 2 will be displayed. In these graphs, the closed points will be ringed and the mixed ones (i.e., the points that are neither closed nor open) boxed. Hence, the points neither ringed nor boxed will be open (note that no points of Z 2 may be both closed and open).

By a (discrete) closed curve in a topological space (X, p) we mean a cycle in the connectedness graph of p. Thus, every closed curve is a nonempty, finite and connected set. In accordance with [START_REF]Digital Jordan curves[END_REF], a closed curve C ⊆ X in (X, p) is said to be simple if, for each point x ∈ C, there are exactly two points of C adjacent to x in the connectedness graph of p. A simple closed curve C in (X, p) is said to be a (discrete) Jordan curve if it separates (X, p) into precisely two components (i.e., if the subspace X \ C of (X, p) consists of precisely two components).

We will need the following statement resulting from [START_REF]A digital analogue of the Jordan curve theorem[END_REF], Corollary 1.5:

Lemma 2.1 Let (X, p), (Y, q) be Alexandroff spaces such that q is the quotient pretopology of p generated by a surjection e : X → Y with connected fibres. Then a subset B ⊆ Y is connected in (Y, q) if and only if e -1 (B) is connected in (X, p).

Note that the statement of the previous Lemma need not be true if q is only the quotient topology and not the quotient pretopology of p -see the following counterexample due to one of the referees of this paper:

Example 2.2 Let (X, p) be the topological space where X = {1, 2, 3, 4}, the closure of {1} is {1}, the closure of {2} is {1, 2, 3}, the closure of {3} is {3}, and the closure of {4} is {3, 4}. Let Y = {a, b, c} and let e : X → Y be the surjection defined by e(1) = a, e(2) = e(3) = b, and e(4) = c (so that e has connected fibers). Then, in the quotient space (Y, q) of (X, p) generated by e, we have that a lies in the closure of c. So, B = {a, c} is connected in (Y, q), but e -1 (B) = {1, 4} is not connected in (X, p).

Let z = (x, y) ∈ Z 2 be a point. We put H 2 (z) = {(x + k, y); k ∈ {-1, 1}}, V 2 (z) = {(x, y + l); l ∈ {-1, 1}}, D 5 (z) = H 2 (z) ∪ {(x + k, y -1); k ∈ {-1, 0, 1}}, U 5 (z) = H 2 (z) ∪ {(x + k, y + 1); k ∈ {-1, 0, 1}}, L 5 (z) = V 2 (z) ∪ {(x -1, y + l); l ∈ {-1, 0, 1}}, R 5 (z) = V 2 (z) ∪ {(x + 1, y + l); l ∈ {-1, 0, 1}}, A 12 (z) = {(k, l) ∈ Z 2 ; k = x and 0 < |l -y| ≤ 3, or l = y and 0 < |k -x| ≤ 3}. Next, we put A 4 (z) = H 2 (z) ∪ V 2 (z), A 8 (z) = L 5 (z) ∪ R 5 (z)(= D 5 (z) ∪ U 5 (z)), and A ′ 4 (z) = A 8 (z) \ A 4 (z)
. Thus, the number of points of each of the nine sets introduced above equals the index of the symbol denoting this set. In the literature, the points of A 4 (z) and A 8 (z) are said to be 4-adjacent and 8-adjacent to z, respectively. It is natural to call the points of H 2 (z), V 2 (z), D 5 (z), U 5 (z), L 5 (z), R 5 (z), A 12 (z) and A ′ 4 (z) horizontally 2-adjacent, vertically 2-adjacent, down 5-adjacent, up 5-adjacent, left 5-adjacent, right 5-adjacent, cross 12-adjacent and diagonally 4-adjacent to z, respectively. Clearly, each of these adjacencies, excluding A 12 (z) implies 8-adjacency.

The union of each of the above ten sets H 2 (z), V 2 (z)... with the singleton {z} is denoted by the corresponding barred symbols, i.e., by H2 (z), V2 (z)....

Recall [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] that the Khalimsky topology on Z 2 is the Alexandroff topology t given as follows:

For any z = (x, y) ∈ Z 2 , t{z} =        Ā8 (z) if x, y are even, H2 (z) if x is even and y is odd, V2 (z) if x is odd and y is even, {z} otherwise.
The Khalimsky topology is connected and T 0 ; a portion of its connectedness graph is shown in Figure 1.

In [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], Khalimsky, Koppermann and Meyer proved the following digital Jordan curve theorem for (Z 2 , t): q q q q q q q q q q q q q q q q q q q q q q q q q

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❞ ❞ ❞ ❞ 0 1 2 3

Theorem 2.3 In the Khalimsky plane, any simple closed curve having at least four points is a Jordan curve.

The Marcus-Wyse topology (cf. [START_REF] Marcus | A special topology for the integers (Problem 5712)[END_REF]) is the connected Alexandroff T 1 2 -topology s on Z 2 given as follows:

For

any z = (x, y) ∈ Z 2 , s{z} = Ā4 (z) if x + y is odd, {z} otherwise.
The Marcus-Wyse topology is quite simple -its connectedness graph coincides with the 4-adjacency graph. The following digital Jordan curve theorem for (Z 2 , s) is proved in [START_REF] Kiselman | Digital Jordan curve theorems[END_REF]: [START_REF] Engelking | General Topology[END_REF] Let C be a cycle in the connectedness graph of s such that, for every point z ∈ C, there are precisely two points of C adjacent to z and card{p ∈ C \ {z}; there exists a point q ∈ Z 2 adjacent to both z and p} = 2. Then C is a Jordan curve in (Z 2 , s).

Theorem 2.
The previous Theorem has been recently generalized to a larger class of curves in [START_REF] Capraro | A notion of continuity in discrete spaces and applications[END_REF]. Note that, at none of its points, can a Jordan curve in the Khalimsky or Marcus-Wyse plane turn to make an acute angle of π 4 (and, in mixed points, a Jordan curve in the Khalimsky plane can not turn at all). In the next section, we will introduce a topology on Z 2 with respect to which Jordan curves may turn, at some points, to make an acute angle of π 4 .

3 Topology w and some of its quotients

We denote by w the Alexandroff topology on Z 2 given as follows (cf. [START_REF]Convenient closure operators on Z 2[END_REF]):

For any point z = (x, y) ∈ Z 2 , w{z} =                            Ā8 (z) if x = 4k, y = 4l, k, l ∈ Z, Ā′ 4 (z) if x = 2 + 4k, y = 2 + 4l, k, l ∈ Z, D5 (z) if x = 2 + 4k, y = 1 + 4l, k, l ∈ Z, Ū5 (z) if x = 2 + 4k, y = 3 + 4l, k, l ∈ Z, L5 (z) if x = 1 + 4k, y = 2 + 4l, k, l ∈ Z, R5 (z) if x = 3 + 4k, y = 2 + 4l, k, l ∈ Z, H2 (z) if x = 2 + 4k, y = 4l, k, l ∈ Z, V2 (z) if x = 4k, y = 2 + 4l, k, l ∈ Z, {z} otherwise.
q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ 0 2 4 6 8 2 4 6 8
Fig. 2: A portion of the connectedness graph of w.

q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Clearly, w is connected and T 0 . A portion of the connectedness graph of w is shown in Figure 2.

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 0 2 4
The Alexandroff topology on Z 2 introduced and studied in [START_REF]Digital Jordan curves[END_REF] is coarser than w -it is obtained from the definition of w by replacing D5 (z), Ū5 (z), L5 (z) and R5 (z) by D5 (z)\{(x, y -1)}, Ū5 (z)\{(x, y + 1)}, L5 (z) \ {(x -1, y)} and R5 (z) \ {(x + 1, y)}, respectively. Because of this fact, some results proved in [START_REF]Digital Jordan curves[END_REF] and [START_REF]A quotient-universal digital topology[END_REF] for the topology studied there may easily be transferred to w. In particular, by Theorem 11 in [START_REF]Digital Jordan curves[END_REF], we get: Theorem 3.1 Every cycle C in the graph a portion of which is shown in Figure 3 is a Jordan curve in (Z 2 , w) having the property that, if C has no acute corners, then for each point z ∈ C the set A 8 (z) contains at least one point in each of the components of Z 2 \ C.

Analogously to [START_REF]A quotient-universal digital topology[END_REF], we define an Alexandroff topology v on Z 2 as follows:

For any z = (x, y) ∈ Z 2 , v{z} =        H2 (z) if
x is odd and y is even, V2 (z) if x is even and y is odd, Ā′ 4 (z) if x, y are odd, {z} if x, y are even. q q q q q q q q q q q q q q q q q q q q q q q q q Evidently, v is connected and T 1 2 . A portion of its connectedness graph is shown in Figure 4. The following three statements are obtained by transferring the results of Theorems 10-12 in [START_REF]A quotient-universal digital topology[END_REF] to the topology w: Proposition 3.2 The Khalimsky topology is the quotient pretopology of w generated by the surjection f : Z 2 → Z 2 given as follows:

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ ❞ 0 1 2
f (x, y) =        (2k, 2l) if (x, y) = (4k, 4l), k, l ∈ Z, (2k, 2l + 1) if (x, y) ∈ Ā4 (4k, 4l + 2), k, l ∈ Z, (2k + 1, 2l) if (x, y) ∈ Ā4 (4k + 2, 4l), k, l ∈ Z, (2k + 1, 2l + 1) if (x, y) ∈ Ā′ 4 (4k + 2, 4l + 2), k, l ∈ Z.
The surjection f is shown in Figure 5 where the corresponding decomposition of the topological space (Z 2 , w) is marked by the dashed lines. All points of a class of the decomposition are mapped by f to the center point of the class expressed in the bold coordinates.

Proposition 3.3

The Marcus-Wyse topology s is the quotient pretopology of w generated by the surjection g : Z 2 → Z 2 given as follows:

g(x, y) =        (k + l, l -k) if (x, y) ∈ Ā8 (4k, 4l), k, l ∈ Z, (k + l + 1, l -k) if (x, y) = (4k + 2, 4l + 2) for some k, l ∈ Z
with k + l odd or (x, y) ∈ Ā12 (4k + 2, 4l + 2) for some k, l ∈ Z with k + l even.

The decomposition of the topological space (Z 2 , w) given by g is shown in Figure 6, similarly to Figure 5, by the dashed lines. Every class of the decomposition is mapped by g to its center point expressed in the coordinates with respect to the diagonal axes (where the first coordinate relates to the axis with only the non-negative part displayed). Proposition 3.4 v is the quotient pretopology of w generated by the surjection h : Z 2 → Z 2 given as follows:

h(x, y) =        (2k, 2l) if (x, y) ∈ Ā8 (4k, 4l), k, l ∈ Z, (2k, 2l + 1) if (x, y) ∈ H2 (4k, 4l + 2), k, l ∈ Z, (2k + 1, 2l) if (x, y) ∈ V2 (4k + 2, 4l), k, l ∈ Z, (2k + 1, 2l + 1) if (x, y) = (4k + 2, 4l + 2), k, l ∈ Z.
The surjection h is demonstrated in Figure 7 in a way analogous to that used to demonstrate f in Figure 5. 4 Jordan curves in (Z 2 , v)

In Theorem 3.1, we have determined Jordan curves in the topological space (Z 2 , w). The following statement enables us to use Theorem 3.1 to determine Jordan curves in a quotient topological space of (Z 2 , w):

Proposition 4.1 Let (Z 2 , p), (Z 2 , q) be Alexandroff spaces such that q is the quotient pretopology of p on Z 2 generated by a surjection e : Z 2 → Z 2 . Let e have connected fibres and let D ⊆ Z 2 be a simple closed curve in (Z 2 , q). Then D is a Jordan curve in (Z 2 , q) if the following two conditions are satisfied:

(1) There is a Jordan curve C in (Z 2 , p) such that e(C) = D.

(2) C i \ e -1 (D) is nonempty and connected in (Z 2 , p) for i = 1, 2 where C 1 and C 2 are the two components of Z 2 \ C.

Proof: Let the conditions of the statement be fulfilled and put

C ′ 1 = C 1 \ e -1 (D) and C ′ 2 = C 2 \ e -1 (D). Since C ′ i is connected for i = 1, 2 (by the assumptions), e(C ′ i ) is connected for i = 1, 2 by Lemma 2.1. On the other hand, since C ′ 1 ∪ C ′ 2 = e -1 (Z 2 \ D) is not connected (by the assumptions), Z 2 \ D = e(C ′ 1 ) ∪ e(C ′ 2 )
is not connected by Lemma 2.1. Hence, e(C ′ 1 ) and e(C ′ 2 ) are the components of Z 2 \ D. ✷ Indeed, Proposition 4.1 may be applied to get a Jordan curve theorem in the spaces (Z 2 , t) and (Z 2 , v) because the maps f and h have connected fibres. This is not true if w is replaced by the topology studied in [START_REF]Digital Jordan curves[END_REF] (because then only f has connected fibres). The map g has connected fibres neither for w nor for the topology from [START_REF]Digital Jordan curves[END_REF]. r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r As for the Khalimsky topology, we have the famous Theorem 2.3 proved in [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] that completely determines Jordan curves among the simple closed ones. For the Marcus-Wyse topology, we have Theorem 2.4 and also Jordan curve theorem proved in [START_REF]Digital Jordan curves[END_REF] (Proposition 13). Therefore, as the main result of this note, we will prove a Jordan curve theorem for v. Theorem 4.2 Let D be a simple closed curve in (Z 2 , v) with more than four points such that every pair of different points z 1 , z 2 ∈ D with both coordinates even satisfies A 4 (z 1 ) ∩ A 4 (z 2 ) ⊆ D. Then D is a Jordan curve in (Z 2 , v).

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ 0
❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ r r r r r r r ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 1
❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ ❡ 0 2 4 6 8
Proof: By Proposition 3.3, v is the quotient pretopology of w generated by h. It may easily be seen that, in the graph a portion of which is shown in Fig. 3, there is precisely one cycle C that satisfies h(C) = D. By Theorem 3.1, C is a Jordan curve in (Z 2 , w). Clearly, every point of C has either two even coordinates or two odd coordinates or a coordinate that is a multiple of four. C consists of the center points of the sets h -1 (z), z ∈ C, (see Fig. 7) and the points lying between the pairs of center points of the sets h -1 (z 1 ) and h -1 (z 2 ) where z 1 , z 2 ∈ D are adjacent points in the connectedness graph of v (clearly, for every pair of points z 1 , z 2 ∈ D adjacent in the connectedness graph of v, there is precisely one point lying between the center point of h -1 (z 1 ) and that of h -1 (z 2 ) -it is the only point adjacent to each of the two center points in the graph shown in Fig. 2). Since D is a simple closed curve in (Z 2 , v), we have card({(x + i, y + j); i, j ∈ {-2, 2}} ∩ C) = 2 for every point (x, y) ∈ C with x = 4k + 2 and y = 4l + 2 for some k, l ∈ Z. Further, we have card C > 8 because C has more than four points. The fact that every pair of different points z 1 , z 2 ∈ h(C) with both coordinates even satisfies

A 4 (z 1 ) ∩ A 4 (z 2 ) ⊆ h(C) implies that (a) (4k, 4l + 2) ∈ C whenever (4k, 4l), (4k, 4l + 4) ∈ C (k, l ∈ Z) and (b) (4k + 2, 4l) ∈ C whenever (4k, 4l), (4k + 4, 4l) ∈ C (k, l ∈ Z).
Let C 1 , C 2 be the two components of the subspace Z 2 \ C of (Z 2 , w) and put

C ′ i = C i \ h -1 (D) for i = 1, 2.
Since C has more than four points, we have C ′ i = ∅ for i = 1, 2. Let (x, y) ∈ D be a point and write h -1 (x, y) briefly instead of h -1 ({(x, y)}). It is evident that h -1 (x, y) ⊆ C if and only if both x and y are odd (then h -1 (x, y) is a singleton). Thus, let (x, y) ∈ D be a point with x or y even.

(1) Suppose that x is even and y is odd. Then h -1 (x, y) = H2 (2x, 2y) where (2x, 2y) ∈ C. The points h(2x, 2y -1) = (x, y -1) and h(2x, 2y + 1) = (x, y + 1) must also lie in D, so that (2x, 2y -1) and (2x, 2y + 1) both lie in C, but h(2x -2, 2y) = (x -1, y) does not lie in D, so that (2x -2, 2y) / ∈ C. Therefore, every path (in the connectedness graph of w) in C i (i ∈ {1, 2}) containing the point (2x-1, 2y) as a non-end vertex contains also the points (2x -1, 2y -1) and (2x -1, 2y + 1) because they are the only points of C i adjacent to (2x -1, 2y) in the connectedness graph of w. Thus, given any path in C i (i ∈ {1, 2}) that contains the point (2x -1, 2y), when we replace the point (2x -1, 2y) by (2x -2, 2y), we obtain another path in C i because (2x-2, 2y) is adjacent to both (2x-1, 2y -1) and (2x-1, 2y + 1). It follows that C i \ {(2x -1, 2y)} is connected for i ∈ {1, 2}. Using analogous arguments, we may show that C i \ {(2x + 1, 2y)} is also connected for i ∈ {1, 2}. Thus,

C i \ h -1 (x, y) is connected for i = 1, 2.
(2) If x is odd and y is even, then h -1 (x, y) = V2 (2x, 2y) where (2x, 2y) ∈ C and the situation is analogous to [START_REF] Capraro | A notion of continuity in discrete spaces and applications[END_REF], so that 1) and (2) imply that C ′′ i is connected for i = 1, 2. We will now deduce from the connectedness of

C i \ h -1 (x, y) is connected for i = 1, 2. Put D 0 = {(m, n) ∈ D; m + n is odd} and C ′′ i = C i \ h -1 (D 0 ). Then (
C ′′ i that C i \ h -1 (D) = C ′′ i \ h -1 (D)
must also be connected (for i = 1, 2). It will then follow from Proposition 4.1 that D is a Jordan curve in (Z 2 , v). In the sequel, the term "path" will mean "path in the connectedness graph of w".

The proof that C i \ h -1 (D) is connected is based on the fact that, if P is any path in C ′′ i whose first and last points lie in C i \ h -1 (D), and z is any point of P in h -1 (D) (so that z ∈ C ′′ i ∩ h -1 (D)), then: (i) The immediate predecessor and the immediate successor of z in the path P both lie in Z 2 \ h -1 (D), and hence in

C i \ h -1 (

D).

(ii) There is a short path (of length at most 4) in C i \ h -1 (D) from the immediate predecessor of z in P to the immediate successor of z in P . Readily, (i) and (ii) imply that C i \h -1 (D) is connected: Indeed, if a and b are any points in C i \h -1 (D) = C ′′ i \ h -1 (D), then (as C ′′ i is connected) there is a path P in C ′′ i from a to b and, since we can use the short path referred to in (ii) as a "detour" in C i \ h -1 (D) around any point z of P that lies in h -1 (D), there is also a path in C i \ h -1 (D) from a to b. So, it remains only to confirm that (i) and (ii) are true.

(i) follows from the observation that no two points of C ′′ i ∩ h -1 (D) are adjacent in w's connectedness graph because each point of C ′′ i ∩ h -1 (D) lies in A 8 (c) for some point c ∈ C whose coordinates are both divisible by four.

(ii) is obviously true if the predecessor and the successor of z in P are the same point; in this case the short path has length 0. In the other cases, (ii) can be verified by inspection of Fig. 7: In view of the symmetries of the connectedness graph of w, we may assume, without loss of generality, that the point z lies in h -1 ({(2, 2)}) = Ā8 ((4, 4)), where (2, 2) ∈ D (so that (4, 4) ∈ C) and, since z = (4, 4) (as z ∈ C ′′ i ), we may further assume that either (A) z = (4, 5), and the predecessor and the successor of z ∈ P are (4,6) and [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] or vice versa; or (B) z = (4, 5), and the predecessor and the successor of z ∈ P are [START_REF] Eckhardt | Topologies for the digital spaces Z 2 and Z 3[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] and [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF]; or (C) z = (5, 5), and the predecessor and the successor of z ∈ P are [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] and [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] or vice versa; or (D) z = (5, 5), and the predecessor and the successor of z ∈ P are [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] and [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | On topologies of generalized segments[END_REF]. In case (A), (ii) holds because [START_REF] Engelking | General Topology[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] is adjacent to [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF]. In cases (B) and (C), we first note that (4, 6) / ∈ h -1 (D) -for otherwise {(3, 6), (4, 6), (5, 6)} = h -1 ({(2, 3)}) ⊆ D 0 and so not all points of P are in q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 2 4 6 8 2 4 6 8 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 0 2 4 6 8
2 4 6 8 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q C ′′ i , which is a contradiction. Thus, in case (B), the path whose points are [START_REF] Eckhardt | Topologies for the digital spaces Z 2 and Z 3[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], [START_REF] Engelking | General Topology[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], and (5,6) satisfies the condition of (ii). In case (C), since (4, 6) / ∈ h -1 (D), we have that (4, 8) / ∈ C (by condition (a) in the first paragraph of this proof), which implies (5, 7) / ∈ h -1 (D); so the path whose points are [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Boundaries in digital planes[END_REF], and [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], or its reverse, satisfies the condition of (ii). In case (D), we can similarly deduce that (5, 7) / ∈ h -1 (D) and (7, 5) / ∈ h -1 (D); moreover, (6, 6) / ∈ C (as [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] cannot be adjacent to two points of the simple closed curve C in the connectedness graph of w because (5, 7) / ∈ C, (7, 5) / ∈ C, and (5, 5) = z / ∈ C), and so (6, 6) / ∈ h -1 (D). Thus, in case (D), the path whose points are [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], [START_REF] Khalimsky | On topologies of generalized segments[END_REF][START_REF] Khalimsky | Boundaries in digital planes[END_REF], [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF], [START_REF] Khalimsky | Boundaries in digital planes[END_REF][START_REF] Khalimsky | On topologies of generalized segments[END_REF], and (6,5) satisfies the condition of (ii). ✷ Example 4.3 Every cycle in any of the four graphs portions of which are shown in Figure 8 is a Jordan curve in (Z 2 , v).

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 0 2 4
❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ 0

Concluding remarks

Jordan curves play an important role in computer image processing because they represent boundaries of regions of digital images. It may therefore be useful to deal with topologies providing a rich enough variety of Jordan curves in the digital plane for the study of digital images. One of the topologies with this property is the well-known Khalimsky topology. In this note, we have introduced two more such topologies, namely w and v. The results obtained suggest that these topologies might be used as background structures on the digital plane to solve problems of digital image processing, especially those closely related to boundaries (image data compression, pattern recognition, boundary detection and contour filling, etc.). The topology w has an advantage over the Khalimsky topology consisting in the fact that Jordan curves in (Z 2 , w) may turn, at some points, to make an acute angle π 4 .

Fig. 1 :

 1 Fig. 1: A portion of the connectedness graph of the Khalimsky topology.

Fig. 3 :

 3 Fig. 3: A portion of a subgraph of the connectedness graph of w.

Fig. 4 :

 4 Fig. 4: The connectedness graph of v.

Fig. 5 :

 5 Fig. 5: Decomposition of (Z 2 , w) given by the surjection f .

3 Fig. 6 :

 36 Fig.6: Decomposition of (Z 2 , w) given by the surjection g.

Fig. 7 :

 7 Fig.7: Decomposition of (Z 2 , w) given by the surjection h.

Fig. 8 :

 8 Fig. 8: Portions of four graphs on Z 2 .

Acknowledgements

The author would like to thank the anonymous referees for their remarks and suggestions, which helped to improve the paper substantially.

This work was supported by the Brno University of Technology, projects no. FSI-S-11-3 and FEKT/FSI-S-11-1. 1365-8050


Shonda Gosselin
email: s.gosselin@uwinnipeg.ca.

† A Szymański

‡ A Paweł Wojda

Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Keywords: Self-complementary hypergraph, Uniform hypergraph, t-complementing permutation, Cyclically t-complementary hypergraph AMS Subject Classification Codes: 05C65, 05E20, 05C25, 05C85

A cyclic q-partition of a hypergraph (V, E) is a partition of the edge set E of the form {F, F θ , F θ 2 , . . . , F θ q-1 } for some permutation θ of the vertex set V . Let Vn = {1, 2, . . . , n}. For a positive integer k, Vn k denotes the set of all k-subsets of Vn. For a nonempty subset K of Vn-1, we let K (K) n denote the hypergraph Vn, k∈K Vn k

. In this paper, we find a necessary and sufficient condition on n, q and k for the existence of a cyclic q-partition of K

In particular, we prove that if p is prime then there is a cyclic p α -partition of K

if and only if p α+β divides n, where β = ⌊log p k⌋. As an application of this result, we obtain two sufficient conditions on n1, n2, . . . , nt, k, α and a prime p for the existence of a cyclic p α -partition of the complete t-partite k-uniform hypergraph K (k) n 1 ,n 2 ,...,n t .

Introduction

Definitions

For a finite set V and a positive integer k, let V k denote the set of all k-subsets of V . A hypergraph is a pair (V, E) in which V is a finite set of vertices and E is a collection of subsets of

V called edges. A hypergraph (V, E) is called k-uniform (or a k-hypergraph) if E ⊆ V k .
The order of a hypergraph is the cardinality of its vertex set, and the rank of a hypergraph is the maximum cardinality of an edge. Thus a k-uniform hypergraph has rank k. The vertex set and the edge set of a hypergraph X will often be denoted by V (X) and E(X), respectively.

Throughout the paper we let V n = {1, 2, . . . , n} and we always assume that the vertex set of a hypergraph of order n is equal to V n . The complete k-uniform hypergraph of order n is V n , Vn k and is de-

noted by K (k) n . For a nonempty subset K of V n-1 , the complete K-hypergraph is V n , k∈K V n k and denoted by K (K)
n . Let θ be a permutation of V n . If {E, E θ , E θ 2 , . . . , E θ q-1 } is a partition of

k∈K V n k , we call it a cyclic q-partition of K (K) n
and θ is called a (q, K)-complementing permutation, or a permutation of cyclic q-partition of

K (K) n . If K = {k} we abbreviate K ({k}) n to K (k)
n and we call θ a (q, k)complementing permutation. We denote the set

E θ i by E i . It is easy to see that E θ i = E i+1( mod q) for i = 0, 1, . . . , q -1. A cyclic q-partition of K (K) n corresponds to a family of q isomorphic hypergraphs {X i = (V n , E i ) : i = 0, 1, . . . , q -1} with edge ranks in K which decompose K (K)
n , and which are permuted cyclically under the action of θ. Each of the hypergraphs X i in this decomposition are sometimes called q-complementary, and θ is called a q-antimorphism of X i .

History and the statement of the main results

The 2-complementary 2-hypergraphs are the self-complementary graphs, which have been well studied due to their connection to the graph isomorphism problem and to large sets of combinatorial designs [START_REF] Colbourn | Graph isomorphism and self-complementary graphs[END_REF][START_REF] Knor | A note on 2-subset-regular self-complementary 3-uniform hypergraphs[END_REF][START_REF] Muzychuk | On Sylow subgraphs of vertex-transitive self-complementary graphs[END_REF][START_REF] Potočnik | The existence of regular self-complementary 3-uniform hypergraphs[END_REF][START_REF] Potočnik | Vertex-transitive self-complementary uniform hypergraphs[END_REF][START_REF] Rao | On regular and strongly-regular self-complementary graphs[END_REF][START_REF] Ringel | Selbstkomplementäre Graphen[END_REF][START_REF] Sachs | Über Selbstkomplementäre Graphen[END_REF]. A good reference on self-complementary graphs and their generalizations is found in [START_REF] Farrugia | Self-complementary graphs and generalizations: a comprehensive reference manual[END_REF].

For a prime power q = p α , the cycle types of the (q, k)-complementing permutations have been determined in [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF] and independently in [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF], while the case for k = 2 originally appeared in [START_REF] Adamus | A note on t-complementing permutations for graphs[END_REF]. We state this result in Theorem 1.1 using the notation of [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF], which we now introduce. A necessary and sufficient condition for a permutation to be (q, k)-complementing of K (k) n has been given in [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF] for arbitrary q and k (1 ≤ k ≤ n -1). For integers n and d, d > 0, the symbol r(n, d) denotes the remainder when n is divided by d. Thus n ≡ r(n, d) (mod d). For a positive integer k and a prime p, the symbol C p (k) denotes the largest nonnegative integer c such that p c divides k. Thus if k = i≥0 k i p i is the base-p representation of k, where 0 ≤ k i < p for all integers i ≤ 0, then C p (k) is the smallest integer i such that k i > 0. For a finite nonempty set A, we abbreviate C p (|A|) to C p (A). The symbol N denotes the set of nonnegative integers. Theorem 1.1 [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF][START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF] Let n, k, p and α be positive integers such that k < n and p is prime. Let θ be a permutation on

V n with orbits O 1 , O 2 , . . . , O m . Then θ is a (p α , k)-complementing permutation of K (k) n if and only if there is a nonnegative integer ℓ such that i:Cp(Oi)<ℓ+α |O i | < r(k, p ℓ+1 ).
The following corollary to Theorem 1.1 gives necessary and sufficient conditions on the order n of a cyclic p α -partition of

K (k)
n . The equivalence between statements (1) and ( 2) was noted in both [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF] and [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF], while the equivalence between ( 2) and (3) was established in [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF].

Corollary 1.2 [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF][START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF] Let n, k, p and α be positive integers such that k < n and p is prime. Suppose that k = i≥0 k i p i and n = i≥0 n i p i , where 0 ≤ k i < p and 0 ≤ n i < p for i ∈ N. Then the following three statements are equivalent.

1. There exists a cyclic p α -partition of

K (k) n .
2. There exists ℓ ∈ N such that r(n, p ℓ+α ) < r(k, p ℓ+1 ).

3. There exist r, ℓ ∈ N with r ≤ ℓ such that n r < k r , n i = k i for r < i ≤ ℓ whenever r < ℓ, and

n i = 0 for ℓ < i < ℓ + α.
The general complete hypergraph is K (Vn-1) n and denoted by K * n , for short. The integers p and n for which there exists a cyclic p-partition of K * n were determined in [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF], and the cycle types of their p-antimorphisms were characterized.

Theorem 1.3 [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF] Let n and p be positive integers with p < n. The general complete hypergraph K * n has a cyclic p-partition if and only if p is prime and n is a power of p. Moreover, every (p, V n-1 )complementing permutation is cyclic.

The goal of this paper is to establish the existence of cyclic q-partitions of K (K) n for various subsets K of V n-1 . Some existence results for cyclic 2-partitions of K (K) n were established in [START_REF] Gosselin | Self-complementary non-uniform hypergraphs[END_REF] for sets K consisting of integers of the form 2 ℓ or 2 ℓ + 1, and sets K consisting of integers which are sums of consecutive powers of 2. In this paper we are mainly interested in existence results for cyclic partitions of K (K) n for sets K of the form {1, 2, . . . , k}. Such results have applications to cyclic decompositions of complete multipartite k-uniform hypergraphs, which will be discussed in Section 3. The main results of this paper are stated in Theorems 1.4, 1.7 and 1.8, and Corollaries 1.5 and 1.6 below. The proofs of the theorems are given in Section 2.

Theorem 1.4 Let n, k, p and α be positive integers such that p is prime and k < n. A permutation σ of V n is (p α , V k )-complementing if and only if the cardinality of any orbit of σ is congruent to 0 (mod p α+β ), where β = ⌊log p k⌋. It is clear that if K ⊂ K ′ ⊂ V n and a permutation σ of V n is (q, K ′ )-complementing then σ is also (q, K)-complementing. Hence, and by Corollary 1.2(3), we have the following.

Corollary 1.6 Let p, n and α be positive integers where p is prime. If p α+β divides n, then there is a cyclic p α -partition of K (K) n for any nonempty subset K of {m : 1 ≤ m ≤ k or nk ≤ m ≤ n -1}, for any k such that p β ≤ k < p β+1 . In particular, there is a cyclic p α -partition of K (V k ) n for these k.

Theorem 1.7 Let n, k and q be positive integers such that q = p α1 1 • p α2 2 • ... • p αs s , where p 1 , p 2 , ..., p s are mutually distinct primes, k < n, and β j = ⌊log pj k⌋ for every j = 1, 2, .., s. A permutation σ of V n is (q, V k )-complementing if and only if the cardinality of any orbit of σ is congruent to 0 (mod

p α1+β1 1 • p α2+β2 2 • ... • p αs+βs s ).
Theorem 1.8 Let p, n and α be positive integers where p is prime, and let

K ⊆ V n-1 . Suppose that n = i≥0 n i p i and k = i≥0 k i p i for each k ∈ K, where 0 ≤ n i < p and 0 ≤ k i < p for all i ∈ N. Let L(n, α) = {ℓ ≥ 0 : n ℓ+1 = n ℓ+2 = • • • = n ℓ+α-1 = 0}.
If there is ℓ ∈ L(n, α) such that, for each k ∈ K, there is r ≤ ℓ for which n r < k r and n i = k i for r < i ≤ ℓ whenever r < ℓ, then there exists a cyclic p α -partition of

K (K) n .
r ≤ ℓ for which n r < k r , and n i = k i for r < i ≤ ℓ whenever r < ℓ. Let ℓ * be the largest integer in {r, r + 1, r + 2, . . . , ℓ} such that k ℓ * = 0. Then r(k, p ℓ+1 ) = r(k, p ℓ * +1 ). Also, we must have

n i = 0 for ℓ * < i < ℓ + α. Since ℓ * + α ≤ ℓ + α, it follows that i:Cp(Oi)<ℓ * +α |O i | = i:Cp(Oi)<ℓ+α |O i |. Thus k ℓ * = 0 and i:Cp(Oi)<ℓ * +α |O i | = i:Cp(Oi)<ℓ+α |O i | < r(k, p ℓ+1 ) = r(k, p ℓ * +1 ).
Now Theorem 1.1 guarantees that θ is a (p α , k)-complementing permutation. Since k was an arbitrary element of K, Lemma 2.4(1) implies that θ is a (p α , K)-complementing permutation. Hence Lemma 2.1 guarantees that there exists a cyclic p α -partition of K (K) n , as claimed.

✷ Proof of Corollary 1.6: If p α+β divides n, then using the notation of Theorem 1.8 we have β ∈ L(n, α). Let k be an integer such that p β ≤ k < p β+1 . For each m ∈ V k and each integer i ≥ 0, let m i denote the coefficient of p i in the base-p representation of m. Let r = r(m) = max{i : m i > 0}. Then m r(m) > n r(m) = 0 and m i = n i = 0 for i = r(m) + 1, r(m) + 2, . . . , β. Hence Theorem 1.8 guarantees the existence of a cyclic p α -partition of K

(V k ) n
. Now Lemma 2.4(3) implies that there exists a cyclic p α -partition of

K (M ) n for M = {m : 1 ≤ m ≤ k or n -k ≤ m ≤ n -1},
and Lemma 2.4(2) implies that there exists a cyclic p α -partition of K (K) n for every nonempty subset K of M , as claimed. ✷

3 Decomposing complete multipartite uniform hypergraphs

Let X = (V, E) be a hypergraph. A subset S ⊆ V is stable in X if S contains no edge of X.
The hypergraph X is called t-partite if V can be partitioned into t stable and mutually disjoint subsets

A 1 , A 2 , ..., A t . Hence V = A 1 ∪ A 2 ∪ ... ∪ A t , A i ∩ A j = ∅ for i = j, e ⊂ A i for i = 1, 2, ..., t
and any edge e ∈ E. The complete t-partite k-hypergraph with vertex set V = A 1 ∪ A 2 , ..., A t has edge set E k = {e : e ⊂ V, |e| = k, e ⊂ A i for i = 1, 2, ..., t}, and is denoted by

K (k) (A 1 , A 2 , ..., A t ) or K (k)
n1,n2,...,nt when |A i | = n i for i = 1, 2, ..., t. Let θ be a permutation of the set A 1 ∪A 2 ∪...∪A t such that A θ i = A i for i = 1, 2, ..., t. We say that θ is a (q, k)-complementing permutation of K (k) (A 1 , A 2 , ..., A t ) if there is a subset E of the set of edges of

K (k) (A 1 , A 2 , ..., A t ) such that E ∪ E θ ∪ E θ 2 ∪ ... ∪ E θ q-1 is a partition of E(K (k) (A 1 , A 2 , ..., A t )). Such a q-partition of E(K (k) (A 1 , A 2 , ..., A t ) is then called a cyclic q-partition of K (k) (A 1 , A 2 , ..., A t ).
For a nonempty set K of positive integers, let K (K) (A 1 , A 2 , ..., A t ) denote the hypergraph with the vertex set V = A 1 ∪ A 2 ∪ ... ∪ A t and the edge set k∈K E k . A permutation θ of A 1 ∪A 2 ∪...∪A t is said to be a (q, K)-complementing permutation of

K (K) (A 1 , A 2 , ..., A t ) if it is a (q, k)-complementing permutation of K (k) (A 1 , A 2 , ..., A t ) for every k ∈ K.
For a permutation θ of V and a subset A of V , let θ |A denote the restriction of the function θ to the set

A. That is θ |A (x) = θ(x), for all x ∈ A. If A is an invariant set of θ, then θ |A is a permutation of A.
Theorem 3.1 Let k, p, t and α be positive integers such that p is prime. Let V = A 1 ∪ A 2 ∪ ... ∪ A t where A i ∩ A j = ∅ for i = j and let θ be a permutation of the set V such that A i θ = A i for every i = 1, 2, ..., t. Each of the following two conditions is sufficient for θ to be a (p α , V k )-complementing permutation of

K (V k ) (A 1 , A 2 , ..., A t ).
1. For all but at most one i ∈ {1, 2, ..., t}, the cardinality of all the orbits of θ |Ai are divisible by p α+β , where β = ⌈log p k⌉ -1.

2. For every i ∈ {1, 2, ..., t}, the cardinalities of all orbits of θ |Ai are divisible by p α+γ , where γ = ⌊log p k/2⌋.

Proof: Let B be a subset of V such that |B| = k and there is no i such that B ⊂ A i . It suffices to show that if B θ s = B then s ≡ 0 (mod p α ).

(1) Since B has non empty intersection with at least two sets, there exists an index i 0 such that C = B ∩ A i0 = ∅ and the cardinality of any orbit of θ |Ai 0 is divisible by p α+β . Note that C θ s = C θ s

|A i 0 = C. Write k ′ = |C|. We have clearly 0 < k ′ < k, hence k ′ ∈ V k-1 . Since β = ⌈log p k⌉ -1, we have p β ≤ k -1 < p β+1 , and so Theorem 1.4 implies that θ A |i 0 is a (p α , V k-1 )-complementing permutation of K V k |Ai 0 | . Hence s ≡ 0 (mod p α ), and the sufficiency of condition (1) is proved.

(2) The proof of sufficiency of the condition ( 2) is similar to the proof given above. It suffices to observe that there is an index i 1 such that C ′ = B ∩ A i1 = ∅ and |C ′ | ≤ k/2. ✷ Corollary 3.2 Let n 1 , n 2 , . . . , n t , k, p and α be positive integers such that p is prime. If at least one of the following two conditions is verified then there is a (p α , k)-complementing permutation of K (k) n1,n2,...,nt .

1. For all but at most one i ∈ {1, 2, ..., t}, p α+β |n i where β = ⌈log p k⌉ -1.

2. For every i ∈ {1, 2, ..., t}, p α+γ |n i where γ = ⌊log p k/2⌋. ✷

Theorem 1 .

 1 4 implies the following. Corollary 1.5 Let n, k, p and α be positive integers such that p is prime and k < n. There is a cyclic p α -partition of K (V k ) n if and only if p α+β divides n, where β = ⌊log p k⌋.

Supported by the Polish Ministry of

In Section 3 we will look at an application of Corollary 1.6 to cyclic p α -partitions of complete t-partite k-uniform hypergraphs.

Proofs of the main results

Given a (q, k)-complementing permutation θ, we can use a simple algorithm described in [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF] and [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF] to generate all of the cyclic q-partitions of K (k) n with q-antimorphism θ. Hence given a (q, K)-complementing permutation θ, we can construct a cyclic q-partition of K (K) n with q-antimorphism θ by taking the union of |K| cyclic q-partitions of complete uniform hypergraphs, one of rank k for each k ∈ K, each of which is constructed using the algorithm in [START_REF] Gosselin | Cyclically t-complementary uniform hypergraphs[END_REF]. We obtain the following lemma.

Lemma 2.1 There exists a cyclic q-partition of K

and σ is (p α , k ′ )-complementing by Theorem 1.1, and hence (p α , V k )-complementing, by Lemma 2.1. Suppose now that the permutation σ of the set V n is (p α , V k )-complementing. We shall prove that for every j = 1, 2, ..., m the cardinality of O j is divisible by p α+β . By Theorem 1.1, for every k ′ ∈ V k there is a nonnegative integer ℓ such that i:Cp(Oi)<ℓ+α

Applying (1) for k ′ = 1, it is very easy to check that p α divides |O j |, for every j = 1, 2, ..., m. Suppose that for an integer γ, 1 ≤ γ ≤ β we have proved that p (γ-1)+α divides the cardinality of every orbit O 1 , O 2 , ..., O m . Since the permutation σ is (p α , p γ )-complementing, by Theorem 1.1 there is an integer ℓ such that i:Cp(Oi)<ℓ+α

(2)

By consequence i:Cp(Oi)<γ+α |O i | ∈ {0, 1, ..., p γ -1}. But since every orbit of the permutation σ has cardinality divisible by p (γ-1)+α , we have i:Cp(Oi)<γ+α |O i | = 0. This means that p α+γ divides |O j | for every j = 1, 2, ..., m. The theorem follows. ✷ Lemma 2.2 ( [START_REF] Szymański | Cyclic partitions of complete uniform hypergraphs[END_REF]) Let k, n and q be positive integers, k < n. A permutation σ of the set V n is (q, k)complementing if and only if σ s (e) = e for any subset e ⊂ V n of cardinality k and s ≡ 0 (mod q). Lemma 2.2 implies easily the following.

Lemma 2.3 Let n and q be positive integers and let K ⊂ V n-1 , K = ∅. A permutation σ of the set V n is (q, K)-complementing if and only if σ s (A) = A for any subset A ⊂ V n such that |A| ∈ K and s ≡ 0 (mod q).

Proof of Theorem 1.7. By Lemma 2.3, a permutation σ of the set V n is (q, V k )-complementing if and only if σ s (A) = A implies s ≡ 0 (mod q) for any subset A of V n such that |A| ∈ V k . But this implication holds if and only if σ s (A) = A implies s ≡ 0 (mod p αj j ) for all j = 1, 2, ..., s and all such sets A, which holds if and only if the permutation σ is (p αj j , V k )-complementing for every j = 1, 2, . . . , s, by Lemma 2.3. Now Theorem 1.4 guarantees that σ is (p αj j , V k )-complementing for every j if and only if the cardinality of every orbit of σ is divisible by p αj +βj j for every j, which holds if and only if every orbit of σ has cardinality divisible by p α1+β1

n for each k ∈ K. Hence we can view a cyclic q-partition of

as a union of |K| cyclic q-partitions of complete uniform hypergraphs, one of rank k for each k ∈ K, which all share a common q-antimorphism θ. Moreover, the complements of the edges in a cyclic q-partition of K (k) n with q-antimorphism θ form a cyclic q-partition of K (n-k) n with the same q-antimorphism θ. The following lemma follows easily from these observations. Lemma 2.4 Let n and q be positive integers and let K ⊆ V n-1 .

1. A permutation θ is (q, K)-complementing if and only if it is (q, k)-complementing for all k ∈ K.

2. There exists a cyclic q-partition of K (M ) n with q-antimorphism θ if and only if there exists a cyclic q-partition of K (K) n with q-antimorphism θ for all nonempty subsets K of M .

3. There exists a cyclic q-partition of K (K) n if and only if there exists a cyclic q-partition of K

Suppose that there is ℓ ∈ L(n, α) such that, for each k ∈ K, there is r ≤ ℓ for which n r < k r , and n i = k i for r < i ≤ ℓ whenever r < ℓ. Then Corollary 1.2 guarantees that r(n, p ℓ+α ) < r(k, p ℓ+1 ) and there exists a cyclic p α -partition of K

n for each k ∈ K. By Lemma 2.4(2), we must show that there exists such a set of |K| cyclic p α -partitions with a common p α -antimorphism θ. Now since r(n, p ℓ+α ) < r(k, p ℓ+1 ) for all k ∈ K, it follows that n = M p ℓ+α + j for some positive integer M and some j < min k∈K {r(k, p ℓ+1 )}. Let θ be a permutation on V n whose orbits O 1 , O 2 , . . . , O m consist of j orbits of length 1 and M orbits of length p ℓ+α . Fix k ∈ K. We will show that θ is a (p α , k)complementing permutation for this k. Now certainly i:Cp(Oi)<ℓ+α |O i | = j < r(k, p ℓ+1 ). To apply Theorem 1.1 to show that θ is (p α , k)complementing, we need to show that this holds for some ℓ * with k ℓ * = 0. By assumption, there is