Author name cluster

C.S. Iliopoulos

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.

4 papers

1 author row

TCS Journal 2014 Journal Article

Extracting powers and periods in a word from its runs structure

M. Crochemore
C.S. Iliopoulos
M. Kubica
J. Radoszewski
W. Rytter
T. Waleń

A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O ( n ) and that they can all be computed in O ( n ) time. We study some applications of this result. New simpler O ( n ) time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for k = 2, and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25, 26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem.

Details DOI

TCS Journal 2013 Journal Article

Efficient seed computation revisited

M. Christou
M. Crochemore
C.S. Iliopoulos
M. Kubica
S.P. Pissis
J. Radoszewski
W. Rytter
B. Szreder

The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions—computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i. e. , the shortest seeds for all the prefixes of the string) in O ( n 2 ) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O ( n log ( n / m ) ) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm Iliopoulos et al. (1996) [14].

Details DOI

I&C Journal 1995 Journal Article

The Subtree Max Gap Problem with Application to Parallel String Covering

O. Berkman
C.S. Iliopoulos
K. Park

We introduce the subtree max gap problem. Consider a rooted tree T with n leaves whose internal nodes have at least two children. Each leaf is associated with a real number. For each internal node v, let A v be the set of numbers associated with the leaves in the subtree rooted at v which are regarded as points on the x-axis. The subtree max gap problem is to compute the maximum distance (gap) between any two consecutive points of Av for every internal node v of T. Our algorithm for the subtree max gap problem follows a series of reductions to other combinatorial problems which are interesting on their own merit. The algorithm runs in O(log n) time using n processors on the concurrent-read exclusive-write parallel random access machine. The subtree max gap problem plays a central role in the parallel solution of the string covering problem. Recently, lliopoulos, et al. (1993, in "Proc. 26th Symposium in Theory of Computing, " pp. 290-299) gave an O(n log n) time sequential algorithm for the string covering problem. Neither parallelizing the above sequential algorithm nor using known techniques from algorithms on strings seems to yield an efficient parallel algorithm for string covering. Our parallel algorithm thus follows a new approach, suing suffix trees and reducing the string covering problem to the subtree max gap problem. The algorithm runs in O(log n) time using n processors on the concurrent-read concurrent-write parallel random access machine, thereby matching the number of operations in lliopoulos, et al.

Details DOI

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.

Details DOI