Author name cluster

W.F. Smyth

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

1 author row

TCS Journal 2021 Journal Article

A new approach to regular & indeterminate strings

Felipe A. Louza
Neerja Mhaskar
W.F. Smyth

In this paper we propose a new, more appropriate definition of regular and indeterminate strings. A regular string is one that is “isomorphic” to a string whose entries all consist of a single letter, but which nevertheless may itself include entries containing multiple letters. A string that is not regular is said to be indeterminate. We begin by proposing a new model for the representation of strings, regular or indeterminate, then go on to describe a linear time algorithm to determine whether or not a string x = x [ 1. . n ] is regular and, if so, to replace it by a lexicographically least (lex-least) string y whose entries are all single letters. Furthermore, we connect the regularity of a string to the transitive closure problem on a graph, which in our special case can be efficiently solved. We then introduce the idea of a feasible palindrome array MP of a string, and prove that every feasible MP corresponds to some (regular or indeterminate) string. We describe an algorithm that constructs a string x corresponding to given feasible MP, while ensuring that whenever possible x is regular and if so, then lex-least. A final section outlines new research directions suggested by this changed perspective on regular and indeterminate strings.

TCS Journal 2021 Journal Article

Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order

Jacqueline W. Daykin
Neerja Mhaskar
W.F. Smyth

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.

TCS Journal 2019 Journal Article

More properties of the Fibonacci word on an infinite alphabet

Amy Glen
Jamie Simpson
W.F. Smyth

Recently the Fibonacci word W on an infinite alphabet was introduced by Zhang et al. (2017) [13] as a fixed point of the morphism ϕ: ( 2 i ) ↦ ( 2 i ) ( 2 i + 1 ), ( 2 i + 1 ) ↦ ( 2 i + 2 ) over all i ∈ N. In this paper we investigate the occurrence of squares, palindromes, and Lyndon factors in this infinite word.

TCS Journal 2019 Journal Article

Off-line and on-line algorithms for closed string factorization

Mai Alzamel
Costas S. Iliopoulos
W.F. Smyth
Wing-Kin Sung

A string X = X [ 1. . n ], n > 1, is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X; for n = 1, every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al. [2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X = X 1 X 2 ⋯ X k, where X 1 is the longest closed prefix of X, X 2 the longest closed prefix of X with prefix X 1 removed, and so on. In this paper we present an O ( log ⁡ n ) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O ( n log 2 ⁡ n ) -time algorithm to compute M C F ( X ), then we present an on-line algorithm for the same problem. In fact, we show that M C F ( X ) can be computed in O ( L log ⁡ n ) time from M C F ( X ′ ), where X ′ = X [ 1. . n − 1 ], and L is the largest integer such that the suffix X [ n − L + 1. . n ] is a substring of X ′.

TCS Journal 2018 Journal Article

Constructing an indeterminate string from its associated graph

Joel Helling
P.J. Ryan
W.F. Smyth
Michael Soltys

As discussed at length in Christodoulakis et al. (2015) [3], there is a natural one-many correspondence between simple undirected graphs G with vertex set V = { 1, 2, …, n } and indeterminate strings x = x [ 1. . n ] — that is, sequences of subsets of some alphabet Σ. In this paper, given G, we consider the “reverse engineering” problem of computing a corresponding x on an alphabet Σ min of minimum cardinality. This turns out to be equivalent to the NP-hard problem of computing the intersection number of G, thus in turn equivalent to the clique cover problem. We describe a heuristic algorithm that computes an approximation to Σ min and a corresponding x. We give various properties of our algorithm, including some experimental evidence that on average it requires O ( n 2 log ⁡ n ) time. We compare it with other heuristics, and state some conjectures and open problems.

TCS Journal 2018 Journal Article

Reconstructing a string from its Lyndon arrays

Jacqueline W. Daykin
Frantisek Franek
Jan Holub
A.S.M. Sohidull Islam
W.F. Smyth

Given a string x = x [ 1. . n ] on an ordered alphabet Σ of size σ, the Lyndon array λ = λ x [ 1. . n ] of x is an array of positive integers such that λ [ i ], 1 ≤ i ≤ n, is the length of the maximal Lyndon word over the ordering of Σ that begins at position i in x. The Lyndon array has recently attracted considerable attention due to its pivotal role in establishing the long-standing conjecture that ρ ( n ) < n, where ρ ( n ) is the maximum number of maximal periodicities (runs) in any string of length n. Here we first describe two linear-time algorithms that, given a valid Lyndon array λ, compute a corresponding string — one for an alphabet of size n, the other for a smaller alphabet. We go on to describe another linear-time algorithm that determines whether or not a given integer array is a Lyndon array of some string. Finally we show how σ Lyndon arrays λ Σ = { λ 1 = λ, λ 2, …, λ σ } corresponding to σ “rotations” of the alphabet can be used to determine uniquely the string x on Σ such that λ x = λ.

TCS Journal 2015 Journal Article

Indeterminate strings, prefix arrays & undirected graphs

Manolis Christodoulakis
P.J. Ryan
W.F. Smyth
Shu Wang

An integer array y = y [ 1. . n ] is said to be feasible if and only if y [ 1 ] = n and, for every i ∈ 2. . n, i ≤ i + y [ i ] ≤ n + 1. A string is said to be indeterminate if and only if at least one of its elements is a subset of cardinality greater than one of a given alphabet Σ; otherwise it is said to be regular. A feasible array y is said to be regular if and only if it is the prefix array of some regular string. We show using a graph model that every feasible array of integers is a prefix array of some (indeterminate or regular) string, and for regular strings corresponding to y, we use the model to provide a lower bound on the alphabet size. We show further that there is a 1–1 correspondence between labelled simple graphs and indeterminate strings, and we show how to determine the minimum alphabet size σ of an indeterminate string x based on its associated graph G x. Thus, in this sense, indeterminate strings are a more natural object of combinatorial interest than the strings on elements of Σ that have traditionally been studied.

TCS Journal 2015 Journal Article

Three overlapping squares: The general case characterized & applications

Widmer Bland
W.F. Smyth

The “Three Squares Lemma” [9] famously explored the consequences of supposing that three squares occur at the same position in a string; essentially it showed that this phenomenon could not occur unless the longest of the three squares was at least the sum of the lengths of the other two. More recently, several papers [10, 30, 21, 13] have greatly extended this result to a “New Periodicity Lemma” (NPL) by supposing that only two of the squares occur at the same position, with a third occurring in a neighbourhood to the right — in these cases also, similar restrictions apply. In this paper an alternative strategy is proposed: the consequences of having only two squares at neighbouring positions are carefully analyzed, and then the observation is made that the analysis applies in a straightforward way (though perhaps with complicated details) to the three neighbouring squares problem in its full generality. We then apply these new insights, first to proofs of the final two remaining unproved subcases (out of a total of 14) of the NPL [10], then to an instance of the more general problem.

TCS Journal 2014 Journal Article

A bijective variant of the Burrows–Wheeler Transform using V -order

Jacqueline W. Daykin
W.F. Smyth

In this paper we introduce the V-transform (V-BWT), a variant of the classic Burrows–Wheeler Transform. The original BWT uses lexicographic order, whereas we apply a distinct total ordering of strings called V-order. V-order string comparison and Lyndon-like factorization of a string x = x [ 1. . n ] into V-words have recently been shown to be linear in their use of time and space (Daykin et al. , 2011) [18]. Here we apply these subcomputations, along with Θ ( n ) suffix-sorting (Ko and Aluru, 2003) [26], to implement linear V-sorting of all the rotations of a string. When it is known that the input string x is a V-word, we compute the V-transform in Θ ( n ) time and space, and also outline an efficient algorithm for inverting the V-transform and recovering x. We further outline a bijective algorithm in the case that x is arbitrary. We propose future research into other variants of transforms using lex-extension orderings (Daykin et al. , 2013) [19]. Motivation for this work arises in possible applications to data compression.

TCS Journal 2013 Journal Article

A linear partitioning algorithm for Hybrid Lyndons using V -order

David E. Daykin
Jacqueline W. Daykin
W.F. Smyth

In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called V -order. We present new combinatorial results for V -order, in particular concatenation under V -order. We propose linear-time RAM algorithms for string comparison in V -order and for Lyndon-like factorization of a string into V -words. This asymptotic efficiency thus matches that of the corresponding algorithms for lexicographical order. Finally, we introduce Hybrid Lyndon words as a generalization of standard Lyndon words, and hence propose extensions of factorization algorithms to other forms of order.

TCS Journal 2013 Journal Article

Enhanced string covering

Tomáš Flouri
Costas S. Iliopoulos
Tomasz Kociumaka
Solon P. Pissis
Simon J. Puglisi
W.F. Smyth
Wojciech Tyczyński

A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border—both prefix and suffix—of y. If u is a cover of a superstring of y then u is a seed of y. Covers and seeds are two formalisations of quasiperiodicity, and there exist linear-time algorithms for computing all the covers and seeds of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string: the enhanced cover; the enhanced left cover; and the enhanced left seed.

TCS Journal 2009 Journal Article

A new approach to the periodicity lemma on strings with holes

W.F. Smyth
Shu Wang

We first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a “wild card”, a “don’t-care” or an “indeterminate letter” in the literature). The proof is modelled on Euclid’s algorithm for the greatest common divisor and is simpler than the original proof given in [J. Berstel, L. Boasson, Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci. 218 (1999) 135–141]. We then study the two-hole case, where our result agrees with the one given in [F. Blanchet-Sadri, Robert A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited, Theoret. Comput. Sci. 270 (1-2) (2002) 401–419] but is more easily proved and enables us to identify a maximum-length prefix or suffix of the string to which the periodicity lemma does apply. Finally, we extend our result to three or more holes using elementary methods, and state a version of the periodicity lemma that applies to all strings with or without holes. We describe an algorithm that, given the locations of the holes in a string, computes maximum-length substrings to which the periodicity lemma applies, in time proportional to the number of holes. Our approach is quite different from that used by Blanchet-Sadri and Hegstrom, and also simpler.

TCS Journal 2008 Journal Article

How many runs can a string contain?

Simon J. Puglisi
Jamie Simpson
W.F. Smyth

Given a string x = x [ 1. . n ], a repetition of period p in x is a substring u r = x [ i + 1. . i + r p ], p = ∣ u ∣, r ≥ 2, where neither u = x [ i + 1. . i + p ] nor x [ i + 1. . i + ( r + 1 ) p + 1 ] is a repetition. The maximum number of repetitions in any string x is well known to be Θ ( n log n ). A run or maximal periodicity of period p in x is a substring u r t = x [ i + 1. . i + r p + ∣ t ∣ ] of x, where u r is a repetition, t a proper prefix of u, and no repetition of period p begins at position i of x or ends at position i + r p + ∣ t ∣ + 1. In 2000 Kolpakov and Kucherov showed that the maximum number ρ ( n ) of runs in any string x [ 1. . n ] is O ( n ), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ ( n ) < n. Recently, Rytter [Wojciech Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), STACS 2006, in: Lecture Notes in Computer Science, vol. 3884, Springer-Verlag, Berlin, 2006, pp. 184–195] made a significant step toward proving this conjecture by showing that ρ ( n ) < 5 n. In this paper we improve Rytter’s approach and press the bound on ρ ( n ) further, proving ρ ( n ) ≤ 3. 48 n.

TCS Journal 2001 Journal Article

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 approximate periodicity under a variety of distance functions. We consider three related problems, for two of which we derive polynomial-time algorithms; we then show that the third problem is NP-complete.

TCS Journal 2000 Journal Article

Repetitions in Sturmian strings

František Franěk
Ayşe Karaman
W.F. Smyth

In this paper we apply a simple representation of Sturmian strings, which we call a “reduction sequence”, to three algorithms. The first algorithm accepts as input a given finite string x and determines in time O(|x|) whether or not x is Sturmian. The second algorithm is a modification of the first that, in the case that x is Sturmian, outputs a reduction sequence for a superstring u of x that is a prefix of an infinite Sturmian string. The third algorithm uses the reduction sequence of u to compute all the repetitions in u in time Θ(|u|), thus extending a recent result for Fibonacci strings. The third algorithm is also based on a characterization of the repetitions in a Sturmian string that describes them compactly in terms of “runs”. Finally, for every integer r⩾4, we show how to construct an infinite Sturmian string that contains maximal repetitions of exponents 2, 3, …, r−1, but none of exponent r.

TCS Journal 2000 Journal Article

Repetitive perhaps, but certainly not boring

W.F. Smyth

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.

TCS Journal 1997 Journal Article

A characterization of the squares in a Fibonacci string

Costas S. Iliopoulos
Dennis Moore
W.F. Smyth

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 − 1 F n − 2. For n ⩾ 1, the length of F n is denoted by ƒn = ¦Fn¦. The infinite Fibonacci string F is the string which contains every F n, n ⩾ 1, as a prefix. Apart from their general theoretical importance, Fibonacci strings are often cited as worst-case examples for algorithms which compute all the repetitions or all the “Abelian squares” in a given string. In this paper we provide a characterization of all the squares in F, hence in every prefix F n; this characterization naturally gives rise to a Θ(ƒn) algorithm which specifies all the squares of F n in an appropriate encoding. This encoding is made possible by the fact that the squares of F n occur consecutively, in “runs”, the number of which is Θ(ƒn). By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require Θ(ƒn log ƒn) time (and produce Θ(ƒn log ƒn) outputs) when applied to a Fibonacci string F n.

TCS Journal 1994 Journal Article

Parallel RAM algorithms for factorizing words

J.W. Daykin
C.S. Iliopoulos
W.F. Smyth

An O(logn log log n) CRCW PRAM algorithm using O( n log n ) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.

TCS Journal 1992 Journal Article

Optimal algorithms for computing the canonical form of a circular string

Costas S. Iliopoulos
W.F. Smyth

An O(log n) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using O( n log n )processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(log n log log n) units of time, also using O( n log n ) processors.