Costas S Iliopoulos
email: [costas.iliopoulos@kcl.ac.uk

Steven Watts
email: steven.watts]@kcl.ac.uk

Efficient Recognition of Abelian Palindromic Factors and Associated Results

A string is called a palindrome if it reads the same from left to right. In this paper we define the new concept of an abelian palindrome which satisfies the property of being abelian equivalent to some palindrome of the same length. The identification of abelian palindromes presents a novel combinatorial problem, with potential applications in filtering strings for palindromic factors. We present an algorithm to efficiently identify abelian palindromes, and additionally generate an abelian palindromic array, indicating the longest abelian palindrome at each location. Specifically, for an alphabet of size |Σ| ≤ log 2 (n) and after O(n) time preprocessing using O(n + |Σ|) space, we may determine if any factor is abelian palindromic in O(1) time. Additionally, we may determine the abelian palindromic array in O(|Σ|n) time. We further specify the algorithmic complexity when this condition on alphabet size |Σ| is relaxed.

Introduction

The identification of palindromic factors in strings, has been a much studied area of stringology, due to the interesting combinatorial aspects and the strong ties with genetic analysis, where palindromes often correspond to significant structures in DNA [START_REF] Subramanian | A pilot study on the prevalence of dna palindromes in breast cancer genomes[END_REF].

Variations of the palindrome identification problem have been frequently introduced, for example Karhumäki et al. presented results on k-abelian palindromes on rich and poor words [START_REF] Karhumäki | On k-Abelian Palindromic Rich and Poor Words[END_REF]. Holub et al. considered the problem as applied to binary words, investigating the properties of palindromic factors of binary strings [START_REF] Holub | On highly palindromic words[END_REF].

We introduce our own simple modification to the problem, yet to be explored, namely abelian palindromes. Though an interesting combinatorial problem in it itself, an efficient method of detecting abelian palindromes can potentially provide a filter by which ordinary palindromic factors may be deduced. This follows from the fact that an ordinary palindrome must necessarily also be an abelian palindrome, and therefore the search space may be reduced if non abelian palindromes can be efficiently dismissed.

Likewise, the abelian palindromic array may potentially be used to assist in the calculation of the ordinary palindromic array, for the purpose of performing a greedy factorisation of a string into ordinary palindromes. This follows from the fact that the abelian palindromic array provides an upper bound for the equivalent value in the ordinary palindromic array.

The rest of this paper is organised as follows. In Section 2, we present basic definitions and notation on strings as well as definitions and results on abelian palindromes. Section 3 presents various data structures and algorithmic tools used in our final algorithms. In Section 4, a detailed implementation of our algorithms are presented, the first being identification of abelian palindromes, the second being the generation of the abelian palindromic array. Our concluding remarks are noted in Section 5. Additionally, the pseudocode of our implementation may be found in Section 6.

Preliminaries

Basic Terminology

We begin with basic definitions and notation from [START_REF] Crochemore | Algorithms on Strings[END_REF]. Let x = x[0]x [START_REF] Crochemore | Algorithms on Strings[END_REF] . . . x[n -1] be a string of length |x| = n over a finite ordered alphabet. We consider the case of strings over an integer alphabet Σ: each character may be replaced by its lexicographical rank in such a way that the resulting string consists of integers in the range {0, . . . , n -1}. We use ORD(x[i]) to refer to the lexicographical rank of the character x

[i]. We use Σ[i] to refer to the ith character of Σ, i.e. Σ[ORD(x[i])] = x[i].
For example, for the alphabet Σ = {a, c, g, t} we have ORD(g) = 2 and Σ[2] = g.

For two positions i and j on x, we denote by

x[i . . j] = x[i] . . . x[j]
the factor (sometimes called substring) of x that starts at position i and ends at position j (it is of length 0 if j < i), and by ε the empty string of length 0. We recall that a prefix of x is a factor that starts at position 0 (x[0 . . j]) and a suffix of x is a factor that ends at position

n -1 (x[i . . n -1]).
Let y be a string of length m with 0 < m ≤ n. We say that there exists an occurrence of y in x, or, more simply, that y occurs in x, when y is a factor of x. Every occurrence of y can be characterised by a starting position in x. Thus we say that y occurs at the starting position i in x when y = x[i . . i + m -1].

We denote the reverse string of x by x R as the string obtained when reading x from right to left, i.e.

x R = x[n -1]x[n -2] . . . x[1]x[0]. We say a string x is a palindrome when x = x R .
We make use of the bit-wise exclusive or (XOR) operation between two binary strings x and y of the same length |x| = |y|, denoted x ⊕ y. This adheres to the standard definition of XOR on two binary strings, i.e. z[i] = (x[i] + y[i]) (mod 2) where z = x ⊕ y. We may similarly apply the XOR operation to integers, x, y ∈ Z by converting x and y to their respective binary equivalents, performing the XOR operation, and converting the binary result into an integer. For example, given x = 5, y = 11 we have x ⊕ y = 5 ⊕ 11 = 0101 ⊕ 1011 = 1110 = 14.

Abelian Palindromes

The concept of abelian strings relates to the idea of disregarding the order of appearance of characters in a string, and concerning ourselves only with the number of occurrences of each character within the string. With this in mind, we wish to define the concept of an abelian palindrome. To facilitate this, we must first recall the definition of a Parikh Vector.

Definition 1. The Parikh vector P(T ) of a string T over the alphabet Σ, is a vector of size |Σ| which enumerates the number of occurrences of each character of the alphabet in T . If the character c ∈ Σ has ordinality i = ORD(c) in the lexicographical ordering of the alphabet Σ, then P(T )[i] stores the number of occurrences of c in T .

We say that two strings T 1 and T 2 are abelian equivalent denoted T 1 ≈ p T 2 if and only if they have the same Parikh vector, i.e. are permutations of each other.

For example, the string T 1 = accgta has the Parikh vector P(T 1 ) = (2, 2, 1, 1). The string T 2 = gactcac has the same Parikh vector and thus T 1 ≈ p T 2 . We may now define the concept of an abelian palindrome. Definition 2. A string T is an abelian palindrome if and only if there exists some palindrome P such that P ≈ p T .

Note that in general, a string T will more easily satisfy the abelian palindromic property over the palindromic property. This comes as a direct result of Lemma 1, which follows clearly from Definition 2.

Lemma 1.

T palindromic =⇒ T abelian palindromic

(1)

T not abelian palindromic =⇒ T not palindromic (2)
Proof. Assume T is palindromic, choose P = T . Therefore we have P = T ≈ p T . Thus T is abelian palindromic and Statement 1 is proven. Statement 2 follows as the contrapositive of Statement 1.

Tools

Initial Observations

We wish to efficiently identify abelian palindromic factors within a string. To enable this, we define some further concepts and auxiliary data structures.

From Definition 2, it is clear that whether a string T is an abelian palindrome is dependant on the values in its Parikh vector P(T ), specifically the number of values that are odd or even. We use |P(T )| to refer to the total number of values in P(T ), and further use |(P(T ))| odd and |(P(T ))| even to refer to the number of odd and even values in P(T ) respectively. This notation allows us to succinctly describe the defining quality of an abelian palindrome in Lemma 2.

Lemma 2. T abelian palindromic ⇐⇒ 0 ≤ |(P(T ))| odd ≤ 1.
Proof. We refer to the length of T as n. We call

T l = T [0 . . n-1 2 -1 ] the left half of T and T r = T [ n-1 2 + 1 . . n -1] the right half of T . Note that if n is even, T = T l T r . If n is odd, T = T l c T r where c = T [ n-1 2 ]
. For an ordinary palindrome P , it is clear that if a character s occurs m times in P l it must correspondingly occur m times in P r , to preserve the palindromic property of P .

We first show that if T is an abelian palindrome, the number of odd values in the Parikh vector |(P(T ))| odd can not exceed 1 by contradiction. Let us assume that |(P(T ))| odd > 1. In this case, we have at least 2 different characters s 1 , s 2 ∈ Σ with an odd number of occurrences in T . For any permutation of the characters in T , at least one of these two characters must have all its occurrences contained entirely within T l and T r , and we call this character s. The character s therefore occurs 2m times in T where m is the number of occurrences of s in T l . Therefore s has an even number of occurrences, which leads us to a contradiction. Therefore we conclude that 0 ≤ |(P(T ))| odd ≤ 1.

We now show that we can always form a palindrome from a permutation of T when 0 ≤ |(P(T ))| odd ≤ 1. In the notation below we use P R l to represent the reversal of P l . Let us assume |(P(T ))| odd = 0. In this case, P(T ) contains only even values. We distribute the characters evenly to form an even length palindrome P such that P ≈ p T as follows (with braces under characters indicating the number of repetitions of that character):

P l = Σ[0] 1 2 P(T )[0] Σ[1] 1 2 P(T )[1] . . . Σ[|Σ| -1] 1 2 P(T )[|Σ|-1] P = P l P R l Now let us assume |(P(T ))| odd = 1.
In this case, P(T ) contains a single odd entry corresponding to some character c = Σ[i]. We distribute the characters evenly, placing the character c at the centre, to form an odd length palindrome P such that P ≈ p T as follows:

P l = Σ[0] 1 2 P(T )[0] . . . Σ[i -1] 1 2 P(T )[i-1] Σ[i + 1] 1 2 P(T )[i+1] . . . Σ[|Σ| -1] 1 2 P(T )[|Σ|-1] Σ[i]
P = P l Σ[i] P R l
Thus we have shown that 0 ≤ |(P(T ))| odd ≤ 1 is both a necessary and sufficient condition for T to be an abelian palindrome. Therefore Lemma 2 follows.

Prefix Parity Integer Array

We aim to describe a new data structure that will prove useful in recognising palindromic factors, beginning with some new definitions.

Lemma 2 provides us with a useful criterion by which we can seek longest abelian palindromes. We first provide some additional definitions which will prove useful. Definition 3. A prefix Parikh vector P i (T ) of a string T is the Parikh vector of the ith prefix of T :

P i (T ) = P(T [0 . . i]) for 0 ≤ i ≤ n -1
Definition 4. A parity vector P(T ) of a string T over the alphabet Σ is a bit vector of length Σ which indicates the parity (even or odd) of the number of occurrences of each character of Σ in T (0 indicates even, 1 indicates odd):

P(T )[i] = P(T )[i] (mod 2)
Definition 5. A prefix parity vector P i (T ) of a string T is the parity vector of the ith prefix of T :

P i (T ) = P(T [0 . . i]) for 0 ≤ i ≤ n -1
Definition 6. A parity integer P(T ) of a string T over the alphabet Σ is a decimal integer representing the value of the parity vector P(T ) when interpreted as a binary number, with the order of magnitude of each bit determined by the lexicographical order of the alphabet Σ:

P(T ) = |Σ|-1 i=0 2 i × P(T )[i]
Definition 7. A prefix parity integer Pi (T ) of a string T is the parity integer of the ith prefix of T :

Pi (T ) = P(T [0 . . i]) for 0 ≤ i ≤ n -1
Definition 8. The prefix parity integer array PA (T ) of a string T of length n is an integer array of length n, which contains the value of Pi (T ) at each position i:

PA (T )[i] = Pi (T )

The prefix parity integer array PA (T ) (example: see bottom of Figure 1) is the key to identifying longest abelian palindromes in a string T . To observe this, we note that the Parikh vector of a factor of T can be determined by evaluating the difference between the two prefix Parikh vectors at the start and end indexes of the factor. The parity vector and parity integer of a factor can also be determined in a similar way, by employing the bit-wise exclusive or (XOR) operation. We summarise these observations in Lemma 3.

Lemma 3. Given a string T :

P(T [i . . j]) = P j (T ) -P i-1 (T ) (1)
P(T [i . . j]) = P j (T ) ⊕ P i-1 (T ) (2)
P(T [i . . j]) = Pj (T ) ⊕ Pi-1 (T ) (3)
Proof. Given a factor F = T [i . Statement 2 follows from Statement 1 by observing that the truth table for the XOR operator is analogous to the parity table for the subtraction operator (when we interpret 0 as even, 1 as odd):

even odd ⊕ 0 1 even even odd 0 0 1 odd odd even 1 1 0

Note that subtraction (mod 2) and XOR are both commutative operations, and therefore the order of operations is unimportant for both tables.

Statement 3 is simply an alternative formulation of Statement 2 in the form of parity integers instead of parity vectors.

Given PA (T ), it now becomes simple to verify whether a factor T [i . . j] is an abelian palindrome, i.e. 0 ≤ |P(T [i . . j])| odd ≤ 1.

Lemma 4.

Given a text T over the alphabet Σ, the following holds:

T [i . . j] abelian palindromic ⇐⇒ Pj (T ) ⊕ Pi-1 (T ) ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 }
Proof. The lemma follows from the application of previously defined lemmas. We use brackets under runs of characters to indicate the length of that run of characters:

T [i . . j] is abelian palindromic ⇐⇒ Lem. 2 0 ≤ |P(T [i . . j])| odd ≤ 1 ⇐⇒ |P(T [i . . j])| odd = 0 ∨ |P(T [i . . j])| odd = 1 ⇐⇒ Def. 4 P(T [i . . j]) = 0 . . . 0 |Σ| ∨ P(T ) ∈ {0 . . . 0 |Σ|-1 1 , 0 . . . 0 |Σ|-2 10 , . . . , 1 0 . . . 0 |Σ|-1 } ⇐⇒ Def. 6 P(T [i . . j]) = 0 ∨ P(T ) ∈ {2 0 , 2 1 , 2 2 , . . . , 2 |Σ|-1 } ⇐⇒ Lem. 3 Pj (T ) ⊕ Pi-1 (T ) ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 }
Lemma 4 immediately leads us to Lemma 5, which allows us to identify the longest factor of a string T starting at i which is abelian palindromic.

Lemma 5. Given a text T over the alphabet Σ, the longest abelian palindromic factor of T occurring at position i is T [i . . j] where j satisfies the following:

j = max{j : Pj (T ) ∈ M (T, i)} M (T, i) = { Pi-1 (T ) ⊕ k : k ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 }}
For a given string T and position i, we call M (T, i) the match set.

Proof. For a fixed i, the longest T [i . . j] which is abelian palindromic is found by determining the largest j, such that i and j satisfy the condition in Lemma 4. We may derive the match set M (T, i) from this condition by employing the fact that XOR is commutative:

Pj (T ) ⊕ Pi-1 (T ) ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 } ⇐⇒ ∃k ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 } such that Pj (T ) ⊕ Pi-1 (T ) = k ⇐⇒ ∃k ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 } such that Pj (T ) = Pi-1 (T ) ⊕ k ⇐⇒ P j (T ) ∈ { Pi-1 (T ) ⊕ k : k ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 }} = M (T, i)
Thus for a given i, the largest j satisfying the above condition gives us the j corresponding to the largest abelian palindromic factor T [i . . j].

Rightmost Array

We describe a simple data structure that will prove useful for identifying longest abelian palindromes.

Definition 9. The rightmost array R(A) of an integer array A of length n over the alphabet {0, . . . , n -1} stores at position i the index of the rightmost occurrence of the integer i in A. If there is no occurrence of i in A then A[i] = -1. Formally stated: Our algorithm to generate a function recognising abelian palindromic factors, relies on the construction of the prefix parity integer array PA (T ). As shown in Lemma 4, we are able to determine if T [i . . j] is abelian palindromic by evaluating the truthfulness of the expression Pj (T ) ⊕ Pi-1 (T ) ∈ {0} ∪ {2 0 , 2 1 , . . . , 2 |Σ|-1 }.

R(A)[i] = k ⇐⇒ A[k] = i ∧ A[k ] = i ∀ k > k R(A)[i] = -1 ⇐⇒ A[k] = i ∀k
Given PA (T ), this expression may be evaluated in O(1) time for a given i and j. This follows from the fact that XOR is a constant time operation. Additionally, we may check if an integer is a power of 2 in constant time by employing the (mod 2) operation.

It is important to note, that these operations are constant time under the assumption that their arguments do not exceed the maximum word size w of the computer implementation used. If we assume that the alphabet size is bounded by the logarithm of n, then this assumption holds, i.e. |Σ| ≤ log 2 (n). Alternatively, the limitation on |Σ| need not depend on n, and may instead be expressed in terms of the word size w of a machine. If the word size is w, we may assume these operations are constant for an alphabet size |Σ| ≤ w. For a larger |Σ|, the expression in Lemma 4 may be evaluated in O( |Σ| w ) time. We now consider the construction of PA (T ). It is possible to construct the array directly while maintaining a single instance of Pi (T ), by Lemma 6. Lemma 6.

PA (T )[0] = 2 ORD(T [0]) PA (T )[i] = PA (T )[i -1] + (2 P i (T )[ORD(T [i])] -1) × 2 ORD(T [i]) 0 < i ≤ n -1
Proof. The case for PA (T )[0] is trivially true. We note that PA (T )[i] = Pi (T ) is an integer representation of P i (T ) interpreted as a binary string. P i (T ) and P i-1 (T ) differ by a single bit flip, corresponding to the character encountered at T [i]. Therefore by Definition 6 and 7, Pi (T ) and Pi-1 (T ) will accordingly differ by a single power of 2, specifically 2 ORD(T [i]) .

Whether 2 ORD(T [i]) should be added or subtracted is dependant on the current parity of the character T [i]. This is determined by P i (T )[ORD(T [i])], with 1 corresponding to addition (+1) and 0 corresponding to subtraction (-1).

Thus the mapping 2b -1 where b ∈ {0, 1} is the most recently flipped bit b = P i (T )[ORD(T [i])], indicates the appropriate addition (+1) or subtraction (-1).

With this iterative equation for PA (T ), we now have all the tools necessary to efficiently determine abelian palindromic factors and solve the problem as stated. We formalise the result in Theorem 1.

Theorem 1. Given a string T of length n over the alphabet Σ, after O(n) time preprocessing and O(n + |Σ|) space, we may perform queries to determine if T [i . . j] is abelian palindromic in O(1) time when |Σ| ≤ log 2 (n).

Additionally with no constraint on the size of Σ, with O( |Σ| w n) time preprocessing we may perform such queries in O( |Σ| w ) time, where w is the computer word size. Proof. By using Lemma 6 we may iteratively construct PA (T )[i] from PA (T )[i -1] in O(1) time at each step, while maintaining the Σ-sized data structure P i (T ), resulting in a total time complexity O(n) and space complexity O(n + |Σ|) to construct PA (T ).

By evaluating the expression on PA (T ) in Lemma 4, we may then determine if T [i . . j] is abelian palindromic. Evaluating this expression may be performed in O(1) time when the number of bits required to store Pi (T ) is no larger than a single computer word w, i.e. when |Σ| ≤ log 2 (n) ≤ w. In general, Pi (T ) may be stored in |Σ| bits, requiring |Σ| w words to store, and thus a multiplying factor of O( |Σ| w ) time is required for all operations involving Pi (T ), both when constructing PA (T ) and when evaluating the expression in Lemma 4, corresponding to a single query.

Abelian Palindromic Array Algorithm

ABELIAN PALINDROMIC ARRAY

Input: A string T of length n. Output: An array P of size n such that A[i] stores the length of the longest abelian factor of T occurring at position i, i.e. as a prefix of T [i . . n -1].

Our algorithm to generate the abelian palindromic array makes use of Theorem 1 and the rightmost array described in Definition 9. We also make use of Lemma 7.

Lemma 7. The abelian palindromic array P of a string T satisfies:

P [i] = max{R(j) : j ∈ M (T, PA (T )[i])}
Where M is the match set as described in Lemma 5.

Proof. Lemma 5 indicates that the longest abelian palindromic factor occurring at i is T [i . . j] where j is the index of the rightmost prefix parity integer with a value contained in the match set M (T, i).

By Definition 9, this rightmost j can be found by taking the largest value obtained when querying the rightmost array with every member of the match set. We now apply Lemma 7, which enables us to determine the longest abelian palindromic factor occurring at i by performing |Σ| constant time queries. Thus a total of O(|Σ|n) constant time queries are required, and the total time complexity to generate the abelian palindromic array is O(|Σ|n).

Conclusion

We have presented two algorithms, the first for recognising whether or not a factor is abelian palindromic, and the second for generating an array which provides the length of the longest abelian palindromic factor at each position in a string.

The proposed algorithms are both dependant on a new data structure called the prefix parity integer array, requiring O(n) time to compute for a string with an alphabet size |Σ| ≤ log 2 (n). Additional complexity is required to determine the longest abelian palindromic factor for each position, namely O(|Σ|n) time.

The main improvement in this work, would be to remove the need for the current requirement that |Σ| ≤ log 2 (n), in order to obtain our current best complexity time. This appears to be a reasonable goal.

Pseudocode

Algorithm Abelian Palindromes

1 2

 1 (P(T )[i]-1)

Fig. 1 .

 1 Fig. 1. Example of prefix Parikh vectors, prefix parity vectors and prefix parity integers.

Fig. 2 . 4 Algorithms 4 . 1

 2441 Fig. 2. Example of rightmost array.

Theorem 2 .

 2 Given a string T of length n over the alphabet Σ, we may determine the abelian palindromic array of T in O(|Σ|n) time and O(n + |Σ|) space, when |Σ| ≤ log 2 (n). Proof. Via the proof in Theorem 1 we are able to calculate the prefix parity integer array PA (T ) in O(n) time and with O(n + |Σ|) space. Since |Σ| ≤ log 2 (n), we know all values of R(A)[i] ∈ {-1, 0, . . . , n -1}. Therefore the rightmost array R( PA (T )) may be calculated in O(n) time, by parsing PA (T ) from right to left and storing any new values encountered. Full details are available in the pseudocode in Section 6.

1 :PRP

 1 function GETPREFIXPARITYINTEGERARRAY(T , Σ) = boolean array of length σ filled with 0 13:for i = 0 to n -1 do 16: if P[ORD(T [i])] == 1 thenORD is the 0-indexed lexicographical order 17:A[i] = prev -B[ORD(T [i])]18: else 19:A[i] = prev + B[ORD(T [i])] (T [i])] = not P[ORD(T [i])] not 1 = 0, not 0 = integer array of length n filled with -1 stores final result 4: 5:for i = n -1 to 0 do parses A from right to left 6: if R[A[i]]== -1 then = integer array of length n filled with 0 stores final result 7: 8:for i = 0 to n -1 do 9:M = GETMATCHSET(A[i -1], σ) A[-1] defined as 0


Gerrit C Van Der Veer
email: gerrit@acm.org

WHERE -Physical Entries to the Internet

Keywords: Internet, Wearable Devices, QR code, Cloud, Information. 1

This contribution shows how the experienced location of data or information, and of computing, changed since the first general use of information and communication technology. We show how many current and future non-professional users will develop a view of locality for physical tagged entry points to resources that are in fact nodes in an, often global, network.

In summary: both for information and information processing devices there has been clear physical locations to keep them and to use them.

Computers Expanded our Possibilitiesan Example

When we started our research in cognitive psychology in the early 60's, one of our challenges was to develop models of individual differences in human information processing. The phenomena of individual difference in cognitive style was one of our key interests. Markov models seemed a promising way to characterize individual sequence preferences, so we choose a domain where sequences are an obvious relevant characteristic, melodies created by music composers. Based on a hand transcription of 46 melodies by Orlando di Lasso [START_REF]Orlando di Lasso: Bicinias[END_REF], we build Markov models to predict the most probable continuation(s) of melody fragments for this composer, intending to compare these to other volumes of this composer's work, or to collections from contemporary other composers. Keeping the information available was the first problem: working from the printed score was not (yet) feasible, working from a hand written or typewritten notation was rather clumsy. Luckily there were new tools available: machines like the Friden Flexowriter allowed us to input our data, to reproduce them, to correct errors, and to make multiple copies of the 7-hole paper tape that were the physical store of our data. A tape could always be read again and a human-readable document could be printed by this machine, see Figure 3. We could read the printed document, but we mostly considered the paper tape to be the actual information: We would store it safely at a location of our own choice, we could hand over a copy to a colleague when needed, and we could easily transport it. In this way, we had our information or data on a set of paper tapes, and we wrote a program in ALGOL-60 to build the Markov models, typed it in the Flexowriter, producing a readable print as well as another tape that we considered our program.

In Amsterdam, a single computer was available for both universities and for the Mathematical Center (later renamed CWI), an Electrologica X-1with 8K of memory words and, next to the binary console, a paper tape station, seer Figure 4. To use it we had to go to the Mathematica Center, bringing our data and our programs on paper tape. We were allowed on night (9 hours) each week, to consider this computer ours, which was enough to work on one matrix multiplication as part of our project. Fig. 3. Friden Flexowriter [START_REF] Flexowriter | [END_REF], and Fig. 4. Electrologica X-1 [START_REF]Picture from Collection Jak Boumans[END_REF].

Around 1970 my department acquired its own "minicomputers", from DEC's PDP series, running UNIX. Now the location of the computer was next to the office and we just walked around with our programs and data tapes.

In the early 80s personal computers became available and we could buy on privately (see Figure 5), a Commodore DX with a detachable keyboard and two 5.25" floppy disk drives, running a disk operating system that was similar to UNIX, and, moreover, could be enlarged with UNIX-like editors etc. The machine could be carried and did fit in the overhead compartment of a plane so we were able to travel with our own machine, and with both our programs and data on disks. The computer, the programs, and the data or information resources were all in people's own hands and could all fit in the luggage of s single traveler.

Then mainframe computers got connected, and we could, both, send email to others, and to work on remote machines, where UNIX was the universal language as well as the hierarchical map structure of resources. Email addresses were in fact complete specifications of the chain of computers that our message should go to, e.g. "utzoo!utgpu!water!watmath!clyde!rutgers!seismo!mcvax!botter!gerrit" (1987), and the same network knowledge allowed us to go to remote machines and login. Figure 6 shows the network of European nodes. Because collaborated with colleagues in many European countries, we did set up an account at one of the available mainframes and we all used the same login name and password, so we could see who was working in our UNIX domain and we used one file to communicate. We knew the path and the location of the machine was, and we knew where the programs and the data were that we were collaborating on. Another possibility that existed for some time was (at least when using UNIX) to work between machines and connect the UNIX filesystems. When being employed by several universities this allowed us access to all programs and data stored at all sites, and even to operate peripherals to read or write at remote locations. This indeed provided strong opportunities, and required precise knowledge of the current state of the remote machines.

But the internet developed, paths were getting too complicated, and in fact multiple paths were used even in a single connection or transport.

Who Cares Where our Things are Anyhow

Email no longer requires the user to know the path or even the machine that hosts the mail server of the addressee. Addresses may refer to provider domains (Gmail), institutes (vu.nl), locations (.eu, .nl), type of business (.ed, .com, .org). Many of us will have multiple addresses, for which we may have to login to several systems. And some of our addresses are aliases (..@acm.org), that allow us to reroute the mail to whichever of our actual mail address). We find our tools increasingly at websites. And if we download the tools or apps, we are used to get updates for which we sometimes pay and sometimes we are not even aware.

Our programs and information can be stored at machines that we know and that we trust. We store our data partly in local memories or hard drives, partly in the cloud, and we sometimes share with specific colleagues or friends, and sometimes with the world, and we might well forget we stored, or shared, or where we left them. In the case of the programs and the interactive websites we create, we will mostly be more carefully about in what system, and with whom we share certain rights. But we need to keep track of locations, names, and passwords. And sometimes we want certain access information to be easily available for a certain community or at a certain location.

4

Here is What You Need at This Moment Sometimes, people feel enabled if they find information or interactivity at specific physical locations.

Industrial Design Teams Work in Physical Spaces

Vyas did a field study in a design school [START_REF] Vyas | Supporting cooperative design through "living" artefacts[END_REF] where he provided 2D color barcodes to the members of several design teams, showed them how they could stick these to any physical artifact like a sketch, a 3D mock-up etc., and how they could use their phone cameras to send tweets to the artifact and read the history of tweets to this artifact.

Figures 78910show some examples. We found that as soon as an artifact was tagged and tweeted to, there was no need to scribble on the sketch anymore: all discussion and comments were tweeted. Somewhat surprisingly, in several (unrelated) projects designers invented an unexpected type of physical artifacts to tweed to, for discussing about other business: They took a clean sheet of paper, tagged is and pus a single word on it like "vote" or "planning", see Figure 11.). Whether sketches, 3-d mock-ups, or simple calls for ideas, in all cases the tagged artifacts were positioned at a location where team members would go to read, comment, and discuss. The tweet flow was the ongoing conversation, located wherever the tag was.

4.2

Pointing is to a Location

We teach in multiple countries. In the case of China, we know that outside the Universities there is a language problem. Most people we need to talk to, like Cab drivers or waiters in restaurants, only communicate in Chinese and sometimes they cannot read complex phrases. We use our Lifescribe pen and notebook (Figure 12) and ask our students to translate our written notes to written Chinese, at the same time pronouncing this translation (Figure 13). Whenever we need to communicate we find the right page in our notebook, and point to the translationif that does not work we point with our pen and the system will pronounce the sentence. Interestingly, anybody who has never seen or used this before considers the pen to be the resource of the sound. For the regular user, the location on the right page in the notebook is the location where the pronunciation is, see Figure 14. And at the same time, the regular user will probably use the pen as input device for his regular computing devices like phone or laptop and network connections where the scribbles and the accompanying sound will be stored and often shared.

Smartphones Open Up the QR Code

QR codes are now arriving at many locations for very different purposes. Some public transport companies put them at stations to allow travelers access to actual traffic information. A QR code on a wine bottle provides information on production and content. Small businesses put them on their leaflets that people will find in their (physical) mailboxes, or pick up from the counter, see Figure 15. At the time of writing, the smartphone is the common device for people to capture the code and find out about its meaning.

Where the code is, there we will find the information. Our students are experimenting with "interactive posters" to enhance the possibilities to engage their peers at conferences, see Figure 16. In this case, the codes are intended to provide many types of experiences: interactive websites, videos of presentations, interactive PowerPoints, and strait forward text and pictures. The actual locations that the codes refer to are, consequently, websites, videos on YouTube or, in China, Youku. For the young researchers that crowed around the poster, phones in hand, the codes directly provide them the content of the discussion and the possibility to compare, e.g., the PowerPoint and the actual performance.

5

Future Meanings of "Here"

Computing artifacts, increasingly, are connected, may be traced, and can be hacked. Professionals in computing should know, and should want to know, where things are: in their smart wearable device (for now their phone or their pen), in their laptop, in their pen drive, their company network, or in the cloud, and they should be concerned about ownership, changeability, safety and privacy. The nonprofessional users of computing and of networked computing (at this moment these are already the majority) would need protection, by law and provided by ethical design and implementation. But at the same time, they cannot be bothered personally. RFD tags and GPS trackers seem to relate to things, not to the humans using them.

A special issue, and in fact the core concept of this paper, is the meaning of location for users of tagged entries to information. Currently the tags seem obvious (for devices like the Livescribe pen, however, they are invisible for the user, even if these needs to know and understand).

For most users of the tags that are increasingly being used to draw attention to information that may be relevant for the observer, for the agent that puts the tag, or for both, a tag is just location to point a wearable device on to find out if there is something relevant at the current moment in the current context. And even if the current common wearable is a smartphone, still growing, and decreasing in social acceptability of use in many contexts, new and more usable wearables will soon be available: think of camera-enhanced pointing device like pen, cameras in (simple or smart) glasses, in smart watches and in other types of smart jewelry.

The use, in all these cases, suggests that relevant information, fun, or interaction is "there"something non-professionals seem to understand quickly and easily. They will relate to non-local information and interactivity, without telling too much about that and about the related aspects of safety and privacy. There certainly is a task for designers, for the law, and for providers here.

Fig. 1 .

 1 Fig. 1. Slide rule, hand-made made by Robert Munafo at the age of 14.

Fig. 2 .

 2 Fig. 2. Abacus from 1340 Upper Italy, German Historical Museum, Berlin.

Fig. 5 .

 5 Fig. 5. Commodore SX 64-1, and Fig. 6. European network in 1986.

Fig. 7 .

 7 Fig. 7. Tagged sketch; Fig. 8. Tagged 3D mock-up; Fig. 9. Tweets; Fig 10. Reading tweets and commenting; Fig. 11. Call for planning suggestions.

Fig. 12

 12 Fig. 12 and 13. Lifescribe Notebook and pen; Fig. 13. English phrase and written and spoken translation; Fig. 14. Pointing to the scribbles triggers the sound track.

Fig. 15 .

 15 Fig. 15. Advertisement with QR code; Fig. 16. Interactive conference poster.

Acknowledgement

We thank our former and current PhD students Dhaval Vyas, Teresa Consiglio, and Danzhu Li for their creative ideas that inspired this analysis, and Elly Lammers for supporting us and enabling the international cooperation that made us think and understand.


Teresa Consiglio
email: teresaconsiglio@gmail.com

Gerrit C Van Der Veer
email: gerrit@acm.org

Design for Cultural Heritage -Developing Understanding in Teaching and Practice

Keywords: Internet of Things, Wearable Devices, Cultural heritage

This contribution shows how we discovered, by teaching and design, the need for ICT support in the domain of cultural heritage collections. We show examples of current situations with, both, workable solutions and logistic problems regarding the maintenance, documentation, and availability of precious artifacts to keep cultures alive. We point to currently available techniques to incorporate cultural heritage artifacts in a cloud based structure for knowledge and communication that might enable the continuation of cultures in an easy and safe way.

1

Culture is Living is Learning

How we Discovered the Opportunity for ICT support for Cultural Things

We have been developing and teaching university level courses on Design for Cultural Heritage in different countries and in different academic cultures [START_REF] Consiglio | Teaching Design for Living Memory[END_REF]: In Alghero (Italy) in a faculty or Architecture and Design; In Amsterdam (the Netherlands) in a consulting company to experts in designing for cultural institutes; In Dalian and in Liaoning (China) to students of Usability Engineering and students of Multimedia and Animation; in San Sebastian (Spain) to students in Human-Computer Interaction and to curators of museum collections in various domains of Cultural Heritage.

We have been designing ICT support for collections of cultural heritage and developed an ontology for systematic support of scholars in domains of living cultures [START_REF] Uras | Keeping Cultural Heritage Alive -Opportunities with ICT[END_REF].

We collaborated with curators of a variety of cultural heritage domains: Folk costumes and the history of local dress habits [START_REF] Uras | Keeping Cultural Heritage Alive -Opportunities with ICT[END_REF]; Folk music, including a collection of instruments, the history, maintenance, documentation, historic recordings, and teaching [3]; A museum institute on the conservation and history of 35 mm celluloid movies [START_REF] Donaldson | [END_REF][START_REF] Van Den Tempel | Een tweede leven voor celluloid[END_REF]; A collection of 17 th -19 th century European Art Music Instruments [START_REF]gerritvanderveer[END_REF].

We visited some large cultural heritage collections where we analyzed documentation and retrieval problems: e.g., a Dutch museum of Natural History that keeps 17 th -19 th century specimen of plants collected mainly in (former) Dutch territory and colonies [7]; a Spanish museum of Folk Musical Instruments around the world [START_REF] Música | [END_REF].

Based on these experiences we developed an understanding of the opportunities that state of the art ICT can contribute to the preservation of cultures and the maintenance, documentation, and accessibility of cultural heritage.

1.2

Examples from Teaching

When we teach design for cultural heritage, our introduction always includes examples from our own house where we show artifacts we inherited from our grandparents. These examples represent local or family culture and traditions that support the memories and knowledge as transferred between generations of a community. Figure 1a is an example that represents, for a single family: coat of arms of family members and of cities where family members have been living, the religious environment of this family, a family tradition of celebrating anniversaries of weddings, and the date of the celebration event. After our introduction, the first exercise for our students always is to bring from their own (or their parents') home a comparable artifact that represented the family or community cultural heritage. In a course we taught in a University at Sardinia, department of Architecture and Design, one of our students, member of an international community on the history of folk dresses, brought pictures of a 19 th century dress owned by her family, see figure 1b. During the course a team of students designed a tablet application to document the costume and to support the growing knowledge about its history and continuing use in a developing culture of celebrating heritage folk costumes, depicted in figure 2.

Fig. 2 Interactive tablet application that shows the viewpoints (2a) and their detail navigation on history (2b -2c); diary )2d -2f); and description (g -2h).

Figure 2a illustrates the main structure of the knowledge as used in this community: artifacts are described in 3 different points of view. The history is (for this type of cultural heritage) described along the history of owners / users (Figure 2b At a course we taught in Spain for group of computer students mixed with museum curators, one of the students contributed the case of a picture developing collection related to the town of Bilbao during the 60's, see Figure 3. The student group designed a website for a community of citizens of Bilbao to integrate their collection of historic artifacts (mainly old photographs and documents) and related knowledge. In this case some of the artifacts are in fact old paper documents, original photographs, or original photo negatives. However, sometimes the only artefacts left are electronic documents like PDFs.

Another student group in the same group focused on a collection of historic dances (where the primary artifacts are choreographies, songs, and melodies, with additional artifacts like video and audio recordings, sketches of steps and movements, transcribed scores, and other descriptions). This group (and other design teams that focused their design attempts on historic musical instruments or the performance of local traditional plays and games) elaborated the issue of differences between stakeholders regarding their contributions and their needs of access to the artifacts and to the growing knowledge of their culture. Figure 4 shows an example that they intend to put on

1.3

Culture is Learning is Teaching

We adopt the definition of culture from [9], section 5a: "the integrated pattern of human knowledge, belief, and behavior that depends upon the capacity for learning and transmitting knowledge to succeeding generations". This definition from Merriam-Webster indicates that cultures are patterns of knowledge and behavior shared by a community that transfers the knowledge and behavior to new generations. People involved in such a culture we label in relation their role:

• Scholars: members of the community who are accepted to "know", and who may, consequently, act as teacher, researcher, restorer, copyist, historian, documenter. Examples in the domain of music: composer, performer, maker or maintainer of instruments, recorder of performances; • Amateur: member of the community who participates in a meaning full way based on enough knowledge to experience the activities and to share the beliefs, and who aims at continuing to participate. Examples from the domain of music: people who choose the type of performance, the type of music played, the performers, they want to go to, who may keep souvenirs of events in the culture they want to remember. In many cases these roles may be exchanged: a flute maker, may be happy to travel as an amateur to a performance where the artifact will be used by a performer.

• General pubic: In any type of culture as we define it, there may be people who do not (want to be) qualified as scholar or amateur. They may be labeled the "general public" or "tourists" -people who perceive a cultural event, performance, or an object of cultural heritage that they do not understand in relation to the knowledge, beliefs, or behavior of the culture. For this type of audience, the perceived culture as strange, incomprehensible, or surprising.

If the encounter triggers enough curiosity, however, they might be challenged to become an amateur. They might want to learn, and if they find teaching available, they may end up joining the culture and supporting its continuation and its staying alive.

Consequently, a culture that aims at staying alive will have to develop, keep, and provide, documentation and illustration in various levels of detail and depth, various types of representation and modalities, to accommodate both the scholars, the amateurs, and the general public.

And if the culture is alive, the knowledge and beliefs will continue to develop, and the tools of the culture will be used, adjusted, repaired or adapted to new situations and new members of the culture. In fact, the things, whether tangible or intangible, are the anchors for people to maintain participation in the culture, and, consequently, these things are essential to keep a culture alive. But the things alone cannot do this. The knowledge of their meaning related to the culture, and the skills needed to use them, are another part that should continually be kept, taught, and learned.

Things, in any culture, are from different types: tangible objects need to be maintained (and during the life of the culture often copied) by using (tangible) tools and (often intangible) prescriptions and standards. The actual use of the tangible objects will follow rules and customs (choreographies, scores, scripts, storylines) that are often itself intangible but may be recorded for memory, for teaching and learning in tangible ways (drawings, sketches, literature).

Collections of Things need Structure

In the different types of cultural heritage collections that we analyzed during our teaching, we mostly found some type of ontology being used to be able to retrieve the objects and refer to them in documentation, in reaching, and in learning. Sometimes, a single cultural collection needs in fact several ontologies, depending on the viewpoint needed for retrieval. In the website of [3] we find what seem to be separate collections for:

• Music instruments (over 1400 artifacts, of which 400 are on display and visible at the virtual museum in the website), where the collection is structured along the standard description ontologies by Hornbostel and Sachs, as published in [START_REF] Hornbostel | Systematik der Musikinstrumente: Ein Versuch. Translated as "Classification of Musical Instruments[END_REF] and along categories of Basque traditional ensembles; • Library (over 5800 documents); • Sound library (over 4800 recordings) structures along locations (countries and regions in the Spanish and France bask area) and period of recording; • Photographs, video, and films (hundreds); where all these objects are described in documents in a single content management system, where single or multiple elements can be searched through the search page illustrated in Figure 5. The result of a single search may be a single or a series of records, where each record is a description that may well refer to various objects, like a video recording, a sound recording, the instrument being played, a restoration report for the instrument, and a picture of the artist; all to be found in the museum premises, though stored on servers (for the digital recordings) or in different rooms and on different shelves related to the physical type of the artifact.

In [7] the ontology is still a challenge, since the 1000s of collected specimen have originally (often several centuries ago) been categorized according to different ontologies and taxonomies that have been overthrown, developed, or the category or species names translated. In addition, apart from the biological identification the location of origin (related to the Dutch Colonial history) is sometimes a main entry for search. The current labels often are being discussed, and the physical storage shows the characteristics of a collection that is in structural re-arrangement. The collection in [START_REF] Donaldson | [END_REF] is structured along several dimensions: type of movie, location and studio, actors, authors, and date of creation. And the storage of the physical artifacts is related to the flammability of the material (the movies) and the size (of the projectors, which are both historic home projectors, and huge cinema machines).

Fig. 5. Example search page, taken from [3]

, where for several types of cultural heritage a record may be found from the single content management system.

In [START_REF]gerritvanderveer[END_REF] -a collection of musical instruments, the curators made the decision to label the physical instruments "primary objects" (to be searched according to [START_REF] Hornbostel | Systematik der Musikinstrumente: Ein Versuch. Translated as "Classification of Musical Instruments[END_REF], and to refer in their description to different types of "secondary objects":

• Sound and video recordings;

• Restoration reports;

• Other documents like validation reports, proof of purchase or donation;

• Publications referring to the individual primary object;

• Physical objects that were removed during maintenance and restoration;

• Physical objects that were related to playing the individual instrument (original bows or mouth pieces, original spare parts like strings, original cases, etc.) Some of these secondary objects will not be stored with the primary object, but scholars, when allowed to study or manipulate the primary object, should be able to locate and inspect some of the secondary artifacts.

3

Where are our Things Electronic records of elements in a collection may be nicely stored in a content management system and can be approached through a search facility that is based on a feasible ontology. The physical cultural heritage objects, however, each need their own space in the "real" world. In case of large, or complex, collections like [3, 4, 7, 8] locating the individual objects, and relating them to documentation or entries in the content management system is often a challenge. The case of [START_REF] Música | [END_REF] shows how the structure and business model of the collection brings a challenge to the storage and handling of the artifacts. The collection is not available in a physical museum, the intention of the curators is to provide selections to specialized exhibitions in museums that are available and interested to do so [12 -14], where the actual number of instruments displayed, related to the theme of the exhibition, is between 50 and 200. The total physical collection, comprising close to 5000 instruments, is kept in a large store room with cupboards, boxes, and shelves, see Figure 6. Each individual instrument is labeled by paper sticker of 1 square centimeter containing a 5-digit number that refers to a paper card in a card box. The case referred to in [7] shows the same type of problem. The University website only provides an overview the collection and a few examples, the actual depot con-tains 1000s of artifacts, partly with descriptions in paper documents that are stored in other rooms. In all cases of [3,[START_REF] Donaldson | [END_REF]7,[START_REF] Música | [END_REF] retrieving a single artifact requires considerable time and the availability of a curator or an expert employee of the collection.

Moving our Things into the Cloud

To keep a culture alive, the cultural heritage objects need to be available and need to be related to the knowledge as described in section 2. Current developments in tagging, mobile connectivity, and the internet of things allow us to find solutions for the question from section 3. The cloud and the internet of things may be conceived to provide locations for a knowledge resource as well as a knowledge storage location (a source and sink) for information related to individual physical cultural heritage artifacts, whether these artifacts are movable or immovable [10].

Landmarks may have a Virtual Location to Communicate with

Wearable devices like smart phones or their future successors, if they are enabled to identify precise location of the wearer as well as viewing direction (towards an immovable cultural heritage object like a building or a sculpture), can easily relate the artifact to information at the dedicated location for this artifact in the cloud, as well as allow the viewer to comment or upload multimedia recordings to the location (see [15] for an early prototype developed by one of our students).

Movable Cultural Heritage can be Monitored and Approached from the Cloud

If the number of physical artifacts in a collection gets large, housekeeping is a problem.

Objects may be moved around, be displayed temporarily at a foreign location, made available for research or inspection elsewhere. However, once we connect them to the internet of things, solutions seem available:

RFID based Identification and Authentication. RFID tags are available for this in a contactless and passive mode within a short range (current systems allow distances from 10 cm to 100 meter). And they may be attached to the object in a way that is not immediately visible (even worked into textile fabrics etc. This allows to:

• identify an artifact when encountered;

• authenticate the artifact or establish the status of copy or fake; though forgeries might include cloning the RFID tag.

GPS Tracking. This will enable to locate an artifact within a 1 -2-meter range almost everywhere on the globe, by retrieving them on any web-connected device. It will work if the batteries are working, so some logistics need to be taken care of. This allows monitoring artifacts that are on the move, and retrieving lost or stolen artifacts. The latter functionality, obviously, will only work if the thief is not aware of the GOS tracker, or fails in removing it.

QR code referencing to URL. QR codes can now be captured by wearable devices, and allow direct connection to web locations that provide access to multimedia information that is relevant and related to the artifact. In the same way, the code can provide access to comment on the artifact and to upload multimedia data that could be used to involve the audience in cultural events or allow them to enrich the connotations of the object.

Conclusion: How Safe is Cultural Heritage in the Cloud

The techniques discussed in section 4 each provide part of the functionality, and currently the size of the tags and tracker is shrinking to a level where unobtrusive application seems feasible. Still, in case of criminal intend locating a missing artifact, and in case of potential forgery fake authentication is still a problem. There are current attempts to, in some cases, overcome these dangers [START_REF] Yu | Pervasive, Dynamic Authentication of Physical Items[END_REF]. However, in case of the current large collections of tangible artifacts that are only loosely connected to the intangible knowledge and the relation structure of a living culture, current technical facilities promise a considerable improvement in supporting a living culture. On the other hand, it requires a change in the logistics of many current collections that seem based on traditional paper index cards and backroom storage. We will need to educate the scholars in our cultures as well as to provide IT solutions that are understandable and usable for them.

Fig. 1a

 1a Fig. 1a Picture of a memory document designed and painted by 3 teen brothers to celebrate the wedding of their father and their stepmother, 1915. Fig 1b Picture of a student and her sister wearing a historic dress that has been used in the family for 4 generations.

  Figure 2a illustrates the main structure of the knowledge as used in this community: artifacts are described in 3 different points of view. The history is (for this type of cultural heritage) described along the history of owners / users (Figure 2b and 2c. The diary is a detailed account of what happened to the artifact during its use by the current owner (Figure 2d -2f), the interactive description part is shown in 2g and 2h.At a course we taught in Spain for group of computer students mixed with museum curators, one of the students contributed the case of a picture developing collection related to the town of Bilbao during the 60's, see Figure3. The student group designed a website for a community of citizens of Bilbao to integrate their collection of historic artifacts (mainly old photographs and documents) and related knowledge.

Fig. 3

 3 Fig.3Sketch for a website on a picture collection, intended to grow a community that builds the combined historic knowledge that is currently still available, though mainly spread among individual older citizens of Bilbao.

Fig. 4

 4 Fig. 4 Students' sketch for a structure of stakeholders of a local traditional dance collection, their needs, and their possibilities to contribute.

Fig. 6 .

 6 Fig.6. Some pictures of the storage of the physical cultural heritage artifacts from[START_REF] Música | [END_REF]

Fig. 7 .

 7 Fig. 7. Website related to collection [7]. And a view into one od=f the storages rooms.

Acknowledgement

We thank our students and the scholars and amateurs in the cultural domains who allowed us access to their precious cultural heritage and to their intentions and their struggles to keep their cultures alive.