Fundamenta Informaticae - Volume 97, issue 3

Article Type: Other

DOI: 10.3233/FI-2009-201

Citation: Fundamenta Informaticae, vol. 97, no. 3, pp. i-ii, 2009

Authors: Daykin, David E. | Daykin, Jacqueline W. | Smyth, W.F. (Bill)

Article Type: Research Article

Abstract: Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if and only if every word in Σ^+ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin, Iliopoulos and Smyth …(1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary. Show more

Keywords: alphabet, circ-UMFF, concatenate, dictionary, factor, lexicographic order, Lyndon, maximal, string, total order, UMFF, word

DOI: 10.3233/FI-2009-202

Citation: Fundamenta Informaticae, vol. 97, no. 3, pp. 295-309, 2009

Authors: Iliopoulos, Costas S. | Smyth, W. F. | Yusufu, Munina

Article Type: Research Article

Abstract: A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat is a repeat that occurs at least mmin times (m_{min} ⩾ 2) in each of at least q ⩾ 1 strings in a given set of strings. In this paper, we describe a family of efficient algorithms based …on suffix arrays to compute maximal multirepeats under various constraints. Our algorithms are faster, more flexible and much more space-efficient than algorithms recently proposed for this problem. The results extend recent work by two of the authors computing all maximal repeats in a single string. Show more

Keywords: maximal multirepeats, repeats, gaps, biological sequences, suffix arrays

DOI: 10.3233/FI-2009-203

Citation: Fundamenta Informaticae, vol. 97, no. 3, pp. 311-320, 2009

Authors: Gagie, Travis

Article Type: Research Article

Abstract: We show how to build an alphabetic minimax tree for a sequence W = w_1 , …, w_n of real weights in O(nd log log n) time, where d is the number of distinct integers ⌈wi⌉. We apply this algorithm to building an alphabetic prefix code given a sample.

Keywords: data structures, alphabetic minimax trees

DOI: 10.3233/FI-2009-204

Citation: Fundamenta Informaticae, vol. 97, no. 3, pp. 321-329, 2009

Authors: Allali, Julien | Ferraro, Pascal | Hanna, Pierre | Iliopoulos, Costas | Robine, Matthias

Article Type: Research Article

Abstract: Existing symbolic music comparison systems generally consider monophonic music or monophonic reduction of polyphonic music. Adaptation of alignment algorithms to music leads to accurate systems, but their extensions to polyphonic music raise new problems. Indeed, a chord may match several consecutive notes, or the difference between two similar motifs may be a few swapped notes. Moreover, the substitution scores between chords are difficult to set up. In this paper, we propose a general framework for …polyphonic music using the substitution score scheme set for monophonic music, which allows new operations by extending the operations proposed by Mongeau and Sankoff [15]. From a practical point of view, the limitation of chord sizes and the number of notes that can be merged consecutively lead to a complexity that remains quadratic. Show more

Keywords: music comparison, polyphony, alignment, edit operations, chord matching

DOI: 10.3233/FI-2009-205

Citation: Fundamenta Informaticae, vol. 97, no. 3, pp. 331-346, 2009