Dany Breslauer, Dany Breslauer, Ramesh Hariharan, Ramesh Hariharan
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
the Parallel-Random-Access-Machine (2007)
Dany Breslauer, Dany Breslauer, Devdatt P. Dubhashi, Devdatt P. Dubhashi
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Detecting all Squares in a String (2007)
Alberto Apostolico, Alberto Apostolico, Dany Breslauer, Dany Breslauer
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Dany Breslauer, Artur Czumaj, Devdatt P. Dubhashi
zx--This note provides general transformations of lower bounds in Valiant's parallel comparison decision tree model to lower bounds in the priority concurrent-read concurrent-write...
Rotations of Periodic Strings and Short (2007)
Dany Breslauer, Dany Breslauer, Tao Jiang, Tao Jiang, Zhigen Jiang, Zhigen Jiang
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
[summary by Mireille R'egnier] (2007)
Let S = fs 1; : : : ; s m g be a set of strings over some alphabet \Sigma. A common superstring, or simply superstring, of S is a string s such that each s i in S is a substring (i.e., a consecutive...
Highly Parallelizable Problems (Extended Abstract) (2007)
Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin
) Omer Berkman 1,4 Dany Breslauer 1,2 Zvi Galil 1,2 Baruch Schieber 3 Uzi Vishkin 1,4,5 Summary of Results. We establish that several problems are highly parallelizable. For each of these problems,...
ftp ftp.brics.aau.dk (cd pub/BRICS) The Suffix Tree of a Tree and Minimizing (2007)
Dany Breslauer, Dany Breslauer
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Sequential Transducers, Dany Breslauer, Dany Breslauer
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Fast Parallel String Prefix-Matching. (1998)
An 0(loglogm) time nlogm/loglogm-processor CRCW-PRAM algorithm for the string prefix-matching problem over a general alphabet is presented. The algorithm can also be used to compute the KMP failure...
Testing String Superprimitivity in Parallel, (1998)
A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by...
Parallel String Matching Algorithms, (1998)
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
On the comparison complexity of the string prefix-matching problem (1998)
Dany Breslauer, Dany Breslauer, Livio Colussi, Livio Colussi, Laura Toniolo, Laura Toniolo
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
On the comparison complexity of the string prefix-matching problem (1998)
Dany Breslauer, Dany Breslauer, Livio Colussi, Livio Colussi, Laura Toniolo, Laura Toniolo
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
On Competitive On-Line Paging with Lookahead (1996)
Dany Breslauer, Dany Breslauer
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Rotations of Periodic Strings and Short Superstrings (1996)
Dany Breslauer, Tao Jiang, Zhigen Jiang
This paper presents two simple approximation algorithms for the shortest superstring problem, with approximation ratios 2 2 3 ( 2:67) and 2 25 42 ( 2:596), improving the best previously published 2 3...
Rotations of Periodic Strings and Short (1996)
Dany Breslauer, Tao Jiang, Zhigen Jiang, Dany Breslauer, Tao Jiang, Zhigen Jiang
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
On Competitive On-Line Paging with Lookahead (1996)
Dany Breslauer, Dany Breslauer
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Fast Parallel String Prefix-Matching (1995)
An O(log log m) time n log m log log m -processor CRCW-PRAM algorithm for the string prefix-matching problem over general alphabets is presented. The algorithm can also be used to compute the KMP...
Saving Comparisons in the Crochemore-Perrin String Matching Algorithm (1995)
Crochemore and Perrin discovered an elegant linear-time constant-space string matching algorithm that makes at most 2n \Gamma m symbol comparison. This paper shows how to modify their algorithm to...
Efficient Comparison Based String Matching (1995)
Dany Breslauer, Zvi Galil, Dedicated Joseph, F. Traub
We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the...
Dictionary-Matching on Unbounded Alphabets: Uniform Length Dictionaries (1995)
In the string-matching problem one is interested in all occurrences of a short pattern string in a longer text string. Dictionary-matching is a generalization of this problem where one is looking...
Finding All Periods and Initial Palindromes of a String in Parallel (1995)
An optimal O(log log n) time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the...
An On-Line String Superprimitivity Test (1995)
A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by...
Efficient String Matching on Coded Texts (1995)
Dany Breslauer, Dany Breslauer
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Efficient String Matching on Coded Texts (1994)
Dany Breslauer, Dany Breslauer, Leszek Gasieniec, Leszek Gasieniec
The so called "four Russians technique" is often used to speed up algorithms by encoding several data items in a single memory cell. Given a sequence of n symbols over a constant size...
Parallel Detection of all Palindromes in a String (1994)
Alberto Apostolico, Dany Breslauer, Zvi Galil
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An O(log n) time, n-processor algorithm over general alphabets....
Parallel detection of all palindromes in a string (1993)
Apopstolico, A., Breslauer, Dany, Galil, Z.
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string : - an 0/log n) time, n-processor algorithm over general alphabets....
Saving comparisons in the Crochemore-Perrin string matching algorithm (1993)
Crochemore and Perrin discovered an elegant linear-time constant-space string matching algorithm that makes at most 2n - m symbol comparison. This paper shows how to modify their algorithm to use...
Dictionary-matching on unbounded alphabets : uniform length dictionaries (1993)
Résumé disponible dans les fichiers attachés
Testing string superprimitivity in parallel (1993)
A string w convers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself and quasiperiodic if it is covered by...
Parallel detection of all palindromes in a string (1993)
Apopstolico, A., Breslauer, Dany, Galil, Z.
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string : - an 0/log n) time, n-processor algorithm over general alphabets....
Saving comparisons in the Crochemore-Perrin string matching algorithm (1993)
Crochemore and Perrin discovered an elegant linear-time constant-space string matching algorithm that makes at most 2n - m symbol comparison. This paper shows how to modify their algorithm to use...
Dictionary-matching on unbounded alphabets : uniform length dictionaries (1993)
Résumé disponible dans les fichiers attachés
Testing string superprimitivity in parallel (1993)
A string w convers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself and quasiperiodic if it is covered by...
Tight Comparison Bounds for the String Prefix-Matching Problem (1993)
Dany Breslauer, Livio Colussi, Laura Toniolo
In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting at each position of a text string of length n. This is a...
Efficient Comparison Based String Matching (1993)
Dany Breslauer Cwi, Dany Breslauer, Zvi Galil
We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the...
Tight Comparison Bounds for the String Prefix-Matching Problem (1993)
Dany Breslauer, Livio Colussi, Laura Toniolo
In the string prefix-matching problem one is interested in finding the longest prefix of a pattern string of length m that occurs starting at each position of a text string of length n. This is a...
Efficient string algorithmics /--Dany Breslauer. (1992)
Thesis (Ph. D.)--Columbia University, 1992.
A lower bound for parallel string matching (1992)
[summary by Mireille Regnier] This talk presents the derivation of an\Omega\Gamma/28 log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P [1::m] in a...
Fast Parallel String Prefix-Matching (1992)
An O(log log m) time n log m log log m -processor CRCW-PRAM algorithm for the string prefix-matching problem over a general alphabet is presented. The algorithm can also be used to compute the KMP...
Testing String Superprimitivity in Parallel (1992)
A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by...
Saving Comparisons in the Crochemore-Perrin String Matching Algorithm (1992)
Preliminary Version, Dany Breslauer
Crochemore and Perrin discovered an elegant linear-time constant-space string matching algorithm that makes at most 2n \Gamma m symbol comparison. This paper shows how to modify their algorithm to...
Efficient String Algorithmics (1992)
Ph Thesis Dany, Dany Breslauer, Dany Breslauer, Dany Breslauer
Problems involving strings arise in many areas of computer science and have numerous practical applications. We consider several problems from a theoretical perspective and provide efficient...
Efficient String Algorithmics (1992)
Dany Breslauer, Dany Breslauer, Dany Breslauer
Problems involving strings arise in many areas of computer science and have numerous practical applications. We consider several problems from a theoretical perspective and provide efficient...
An On-Line String Superprimitivity Test (1992)
A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by...
A Lower Bound for Parallel String Matching (1992)
We present an\Omega\Gamma/22 log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P [1::m] in a text string T [1::2m] in parallel using m comparisons in...
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract) (1992)
Alberto Apostolico, Dany Breslauer, Zvi Galil
) Alberto Apostolico Purdue University and Universit`a di Padova Dany Breslauer yyz Columbia University Zvi Galil z Columbia University and Tel-Aviv University Summary of results Optimal...
Finding All Periods and Initial Palindromes of a String in Parallel (1991)
Dany Breslauer Columbia, Dany Breslauer, Zvi Galil
An optimal O(log log n) time CRCW-PRAM algorithm for computing all periods of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of...
Parallel String Matching Algorithms (1990)
Dany Breslauer Columbia, Dany Breslauer, Zvi Galil
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
Parallel String Matching Algorithms (1990)
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
Work supported by NSF Grants CCR-86-05353 and CCR-88-14977 (1990)
Nd Ccr-, Dany Breslauer, Zvi Galil
An optimal O(log log n) time parallel algorithm for string matching on CRCWPRAM is presented. It improves previous results of [G] and [V]. 1 Introduction On a CRCW-PRAM we can solve some problems in...
Dany Breslauer, Devdatt P. Dubhashi, Dany Breslauer, Devdatt P. Dubhashi
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Dany Breslauer, Ramesh Hariharan, Dany Breslauer, Ramesh Hariharan
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...