O'Donnell, F, Ramachandran, V N, Smyth, T J, Smyth, W F, Brooks, P R
The ethyl acetate extract of the leaves of Melicope vitiflora was separated by column chromatography and the resulting fractions tested for their bioactivity towards...
F. Franek, W. F. Smyth, X. Xiao
Abstract. The space requirement of Crochemore’s repetitions algorithm is generally estimated to be about 20mn bytes of memory, where n is the length of the input string and m the number of bytes...
Reconstructing a Suffix Array (2008)
Abstract. For certain problems (for example, computing repetitions and repeats, data compression applications) it is not necessary that the suffixes of a string represented in a suffix tree or suffix...
ABSTRACT A recent paper shows that it can be determined in O(n) time whether or not a given string x of length n is a substring of an infinite Sturmian string; further, if x is such a substring, the...
A simple algorithm for computing the Lempel–Ziv (2008)
Maxime Crochemore, Lucian Ilie, W. F. Smyth
factorization
Reconstructing a Suffix Array (2008)
Abstract. For certain problems (for example, computing repetitions and repeats, data compression applications) it is not necessary that the suffixes of a string represented in a suffix tree or suffix...
Heuristics for Image Retrieval Using Spatial Configurations ⋆ (2008)
W. F. Smyth, C. P. Lam, Xin Chen, Valerie Maxville
Abstract. This paper describes a strategy for content-based image retrieval via spatial configuration of objects within an image. The proposed strategy locates “pattern ” images within “text...
W.F.: New complexity results for the k-covers problem (2008)
Costas S. Iliopoulos, Manal Mohamed, W. F. Smyth
Abstract The k-covers problem (kCP) asks us to compute a minimum cardinality set of stringsof given length k> 1 that covers a given string. It was shown in a recent paper,by reduction to 3-SAT,...
F. Franek, W. F. Smyth, X. Xiao
Abstract. The space requirement of Crochemore’s repetitions algorithm is generally estimated to be about 20MN bytes of memory, where N is the length of the input string and M the number of bytes...
Costas S. Iliopoulos, W. F. Smyth
An O(n 2 (n\Gammak)) on-line algorithm for computing a minimum set of k-covers for a given string of length n is presented. A straightforward modification of the algorithms yields O(kn 2 (n \Gamma...
An Approach to Phrase Selection for Offline Data Compression (2008)
Recently several offline data compression schemes have been published that expend large amounts of computing resources when encoding a file, but decode the file quickly. These compressors work by...
REPETITIVE PERHAPS, BUT CERTAINLY NOT BORING (2007)
In this paper some of the work done on repetitions in strings is surveyed, especially that of an algorithmic nature. Several open problems are described and conjectures formulated about some of them.
REPETITIONS IN STURMIAN STRINGS Frantisek Franek (2007)
In this paper we apply a simple representation of Sturmian strings, which we call a \reduction sequence", to three algorithms. The rst algorithm accepts as input a given nite string x and...
Graphs With Small Generalized Chromatic Number (2007)
Let G = (V; E) denote a finite simple undirected connected graph of order n = jV j and diameter D. For any integer k 2 [1; D], a proper k-colouring of G is a labelling of the vertices V such that no...
A linear algorithm for computing all the squares of a Fibonacci string (2007)
Costas S. Iliopoulos, Dennis Moore, W. F. Smyth, Canada Ls K
A (finite) Fibonacci string Fn is defined as follows: F 0 = b, F 1 = a; for every integer n 2, Fn = Fn\Gamma1 Fn\Gamma2 . For n 1, the length of Fn is denoted by fn = jF n j, while it is convenient...
Approximate Periodicity In Strings (2007)
In many application areas (for instance, DNA sequence analysis), it becomes important to compute various kinds of "approximate period" of a given string y. Here we discuss three such...
Problems Conjectures On Sum Graphs (2007)
Given an integer r 0, let G r = (V r ; E) denote a graph consisting of a simple finite undirected graph G = (V; E) of order n and size m together with r isolated vertices K r . Then jV j = n, jV r j...
Computing Periodicities in Strings — A New Approach ⋆ (2007)
Abstract. The most efficient methods currently available for the computation of repetitions or repeats in a string x = x[1..n] all depend on the prior computation of a suffix tree/array STx/SAx....
Smyth, W F, McClean, S, Hack, C J, Ramachandran, V N, Doherty, B, Joyce, C, ...
This article considers the application of topical analytical techniques – electrospray ionisation-mass spectrometry (ESI-MS) and liquid chromatography (LC)-ESI-MS – to the characterisation of...
A simple fast hybrid pattern-matching algorithm (2005)
Frantisek Franek, Christopher G. Jennings, W. F. Smyth
Abstract. The Knuth-Morris-Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the...
Fast pattern-matching on indeterminate strings (2005)
Jan Holub, W. F. Smyth, Shu Wang
Abstract. In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ1, λ2,..., λj} of Σ, 2 ≤ j ≤ |Σ|. A string x containing...
A new periodicity lemma (2005)
Kangmin Fan, Simon J. Puglisi, W. F. Smyth, Andrew Turpin
Abstract. Given a string x = x[1..n], a repetition of period p in x is a substring u r = x[i..i+rp−1], p = |u|, r ≥ 2, where neither u = x[i..i+p−1] nor x[i..i+(r+1)p−1] is a repetition. The...
A simple fast hybrid pattern-matching algorithm (2005)
Frantisek Franek, Christopher G. Jennings, W. F. Smyth
Abstract. The Knuth-Morris-Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the...
Two-Pattern Strings — Computing Repetitions & Near-Repetitions (2005)
Frantisek Franek, Weilin Lu, W. F. Smyth
In a recent paper we introduced infinite two-pattern strings on the alphabet {a, b} as a generalization of Sturmian strings, and we posed three questions about them: • Given a finite string x, can...
Technical Report containing detail proofs for paper: Sorting suffixes of two-pattern strings (2004)
First, for completeness, we present the actual paper: Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar...
Verifying a border array in linear time (2002)
Weilin Lu, P. J. Ryan, W. F. Smyth, Yu Sun, Lu Yang
A border of a string x is a proper (but possibly empty) prefix of x that is also a suffix of x. The border array β = β[1..n] of a string x = x[1..n] is an array of nonnegative integers in which...
An approach to phrase selection for offline data compression (2002)
Emaih andrew, smyth)cs. curtin. edu. au Recently several offline data compression schemes have been published that expend large amounts of computing resources when encoding a file, but decode the...
Verifying a border array in linear time (2002)
Shudi Gao, Weilin Lu, P. J. Ryan, W. F. Smyth, Yu Sun, Lu Yang
A border of a string x is a proper (but possibly empty) prex of x that is also a sux of x. The border array = [1::n] of a string x = x[1::n] is an array of nonnegative integers in which each element...
An Approach to Phrase Selection for Offline Data Compression (2002)
Recently several offline data compression schemes have been published that expend large amounts of computing resources when encoding a file, but decode the file quickly. These compressors work by...
Frantisek Franek, Jiandong Jiang, Weilin Lu, W. F. Smyth
This paper introduces a new class of strings on {a, b}, called two-pattern strings, that constitute a substantial generalization of Sturmian strings while at the same time sharing many of their nice...
Counting Distinct Strings (1999)
Dennis Moore, W. F. Smyth, Dianne Miller
This paper discusses how to count and generate strings that are "distinct" in two senses: p-distinct and b-distinct. Two strings x on alphabet A and x 0 on alphabet A 0 are said to be...
The sum number of the cocktail party graph (1998)
Mirka Miller, Joseph F. Ryan, W. F. Smyth
A graph G is called a sum graph if there exists a labelling of the vertices of G by distinct positive integers such that the vertices labelled u and v are adjacent if and only if there exists a...
A Representation of Sturmian Strings (1998)
In this paper we introduce a class of morphisms that collectively can be used to represent all Sturmian strings. 1
A Representation Of Sturmian Strings (1998)
In this paper we introduce a class of morphisms that collectively can be used to represent all Sturmian strings. 1 INTRODUCTION A string x is a concatenation of elements, called letters, drawn from a...
An Optimal On-Line Algorithm To Compute All The Covers Of A String (1998)
Let x denote a given nonempty string of length n = jxj. A substring u of x is a cover of x if and only if every position of x lies within an occurrence of u within x. This paper extends the work of...
On-line Algorithms for k-Covering (1998)
Costas S. Iliopoulos, W.F. Smyth
. An O(n 2 (n \Gamma k)) on-line algorithm for computing a minimum set of k-covers for a given string of length n is presented. A straightforward modification of the algorithms yields O(kn 2 (n...
Counting Distinct Strings (1996)
Dennis Moore, W. F. Smyth, Dianne Miller, On Alphabet A
This paper discusses how to count and generate strings that are "distinct" in two senses: p-distinct and b-distinct. Two strings x on alphabet A and x 0 on alphabet A 0 are said to be...
Labelling Wheels for Minimum Sum Number (1996)
Mirka Miller, Joseph Ryan, W.F. Smyth
A simple undirected graph G is called a sum graph if there exists a labelling of the vertices of G into distinct positive integers such that any two distinct vertices u and v of G are adjacent if and...
Covering A Circular String With Substrings Of Fixed Length (1995)
A nonempty circular string C(x) of length n is said to be covered by a set U k of strings each of fixed length k n iff every position in C(x) lies within an occurrence of some string u 2 U k . In...
A Family Of Sparse Graphs Of Large Sum Number (1995)
Given an integer r 0, let G r = (V r ; E) denote a graph consisting of a simple finite undirected graph G = (V; E) of order n and size m together with r isolated vertices K r . Then jV j = n, jV r j...
Correction to An Optimal Algorithm To Compute All The Covers Of A String (1995)
This note corrects an error in a paper recently published in this journal (An optimal algorithm to compute all the covers of a string, IPL 50-5 (1994) 239-246). The correction consists primarily of a...
A Fast Average Case Algorithm For Lyndon Decomposition (1995)
Costas S. Iliopoulos, W. F. Smyth
A simple algorithm, called LD, is described for computing the Lyndon decomposition of a word of length n. Although LD requires time O(nlogn) in the worst case, it is shown to require only \Theta(n)...
Computing the Covers of a String in Linear Time (1994)
this paper we characterize all the covers of x in terms of an easily computed normal form for x. The characterization theorem then gives rise to a simple recursive algorithm which computes all the...
An Optimal Algorithm To Compute All The Covers Of A String (1994)
Let x denote a given nonempty string of length n = jxj 1. A string u is a cover of x if and only if every position of x lies within an occurrence of u within x. Thus x is always a cover of itself. In...
A Fast Effective Heuristic For The Feedback Arc Set Problem (1993)
Peter Eades, Xuemin Lin, W. F. Smyth
Let G = (V; A) denote a simple connected directed graph, and let n = jV j, m = jAj, where n \Gamma 1 m \Gamma n 2 \Delta . A feedback arc set (FAS) of G, denoted R(G), is a (possibly empty) set of...
Mu-balancing M-way Search Trees (1991)
A recent paper by Stout and Warren describes an asymptotically optimal algorithm (using &thetas;(N) time and constant space) for the balancing of binary search trees on N vertices. This paper shows...
Evaluating Measure of Program Quality (1987)
A number of approaches to the measurement of program quality or ‘style’ have recently been described in the computing literature. This article discusses criteria which may be considered for the...
A characterization of the Squares in a Fibonacci string
Costas S. Iliopoulos, Dennis Moore, W. F. Smyth, Canada Ls K
A (finite) Fibonacci string F n is defined as follows: F 0 = b, F 1 = a; for every integer n 2, F n = F n\Gamma1 F n\Gamma2 . For n 1, the length of F n is denoted by f n = jF n j. The infinite...
Approximate Periods of Strings
Jeong Seop Sim, Costas S. Iliopoulos, Kunsoo Park, W. F. Smyth
. The study of approximately periodic strings is relevant to diverse applications such as molecular biology, data compression, and computer-assisted music analysis. Here we study different forms of...
A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward \Theta(n 2 ) algorithm which computes all the weak...
The Sum Number of the Cocktail Party Graph
Mirka Miller, Joseph F. Ryan, W. F. Smyth
A graph G is called a sum graph if there exists a labelling of the vertices of G by distinct positive integers such that the vertices labelled u and v are adjacent if and only if there exists a...
The Covers Of A Circular Fibonacci String
Costas S. Iliopoulos, Dennis Moore, W. F. Smyth
Fibonacci strings turn out to constitute worst cases for a number of computer algorithms which find generic patterns in strings. Examples of such patterns are repetitions, Abelian squares, and...
Sum Graphs Of Small Sum Number
Given an integer r ? 0, let G r = (V; E) denote a graph consisting of a simple finite undirected connected nontrivial graph G together with r isolated vertices K r . Let L : V ! Z + denote a...