Selected Publications

• Rotation of Periodic Strings and Short Superstrings. [Journal of Algorithms 24:2, 1997, pages 340-353. Preliminary report of this research was published in the Proceedings of the 3rd South American Workshop on String Processing, 1996, pages 115-125.] Available as BRICS Report RS-96-21.
• On Competitive On-Line Paging with Lookahead. [Theoretical Computer Science 209:2, 1998, pages 365-375. Preliminary report of this research was published in the Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science, 1996, pages 593-603.] Available as BRICS Report RS-95-50.
• The Suffix Tree of a Tree and Minimizing Sequential Transducers. [Theoretical Computer Science 191, 1998, pages 131-144. Preliminary report of this research was published in the Proceedings of the 7th Symposium on Combinatorial Pattern Matching, 1996, pages 116-129.] Available as BRICS Report RS-95-47.
• On the Comparison Complexity of the String Prefix-Matching Problem. [Journal of Algorithns 29:1, 1998, pages 18-67. Preliminary report of this research was published in the Proceedings of the 2nd European Symposium on Algorithms, 1994, pages 483-494.] Available as BRICS Report RS-95-46.
• Optimal Parallel Construction of Minimal Suffix and Factor Automata. [Parallel Processing Letters 6:1, 1996, pages 35-44.] Available as BRICS Report RS-95-16.
• An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String. [SIAM Journal on Computing 25:6, 1996, pages 1318-1331. Preliminary report of this research was published in the Proceedings of the 19th EATCS International Colloquium on Automata, Languages and Programming, 1992, pages 296-307 under the title "Optimal Parallel Algorithms for Periods, Palindromes and Squares".] Available as BRICS Report RS-95-11.
• Transforming Comparison Model Lower Bounds to the PRAM. [Information Processing Letters 62:2, 1997, pages 103-110. Preliminary report of this research was published in the Proceedings of the 5th Italian Conference on Theoretical Computer Science, 1995, pages 482-491.] Available as BRICS Report RS-95-10.
• Efficient String Matching on Packed Texts. [Informatique Theorique et Applications/Theoretical Informatics and Applications 30:6, 1996, pages 521-544. Preliminary report of this research was published in the Proceedings of the 6th Symposium on Combinatorial Pattern Matching, 1995, pages 27-40.] Available as BRICS Report RS-94-42.
• Saving Comparisons in the Chrochemore-Perrin String Matching Algorithm. [Theoretical Computer Science 158:1, 1996, pages 177-192. Preliminary report of this research was published in the Proceedings of the 1st European Symposium on Algorithms, 1993, pages 61-72.] Available as postscript file.
• Finding All Periods and Initial Palindromes of a String in Parallel. [Algorithmica 14:4, 1995, pages 355-366. Preliminary report of this research was published in the Proceedings of the 19th EATCS International Colloquium on Automata, Languages and Programming, 1992, pages 296-307 under the title "Optimal Parallel Algorithms for Periods, Palindromes and Squares".] Available as postscript file.
• Parallel Detection of all Palindromes in a String. [Theoretical Computer Science 141:1, 1995, pages 163-173. Preliminary report of this research was published in the Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, 1994, pages 497-506.] Available as postscript file.
• Dictionary Matching on Unbounded Alphabets: Uniform Length Dictionaries. [Journal of Algorithms 18:2, 1995, pages 278-295. Preliminary report of this research was published in the Proceedings of the 5th Symposium on Combinatorial Pattern Matching, 1994, pages 184-197.] Available as postscript file.
• Fast Parallel String Prefix-Matching. [Theoretical Computer Science 137:2, 1995, pages 269-278.] Available as postscript file.
• Tight Comparison Bounds for the String Prefix-Matching Problem. [Information Processing Letters 47:1, 1993, pages 51-57. Preliminary report of this research was published in the Proceedings of the 4th Symposium on Combinatorial Pattern Matching, 1993, pages 11-19.] Available as postscript file.
• Efficient Comparison Based String Matching. [Journal of Complexity 9:3, 1993, pages 339-365.] Available as postscript file.
• An On-Line String Superprimitivity test. [Information Processing Letters 44:6, 1992, pages 345-347.] Available as postscript file.
• Optimal Parallel Algorithms for Periods, Palindromes and Squares. [In the Proceedings of the 19th EATCS International Colloquium on Automata, Languages and Programming, 1992, pages 296-307.] Available as postscript file.
• Parallel String Matching Algorithms. [In the Proceedings of the Sequences '91 Workshop: "Sequences II: Methods in Communication, Security and Computer Science", 1991, pages 121-142.] Available as postscript file.
• A Lower Bound for Parallel String Matching. [SIAM Journal on Computing 21:5, 1992, pages 856-862. Preliminary report of this research was published in the Proceedings of the 23rd ACM Symposium on Theory of Computing, 1991, pages 439-443.] Available as postscript file.
• An Optimal O(log log n) Time Parallel String Matching Algorithm. [SIAM Journal on Computing 19:6, 1990, pages 1051-1058. Preliminary report of this research was published in the Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pages 309-319 under the title "Highly Parallelizable Problems".] Available as postscript file.
• Highly Parallelizable Problems. [In the Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pages 309-319.] Available as postscript file.
• Efficient String Algorithmics. [Ph.D. Thesis, Columbia University, 1992.] Available as postscript file.
• Combinatorics for Computer Scientists. [Lecture notes from a course taught in 1995 at the university of Aarhus, Denmark.] Available as BRICS Lecture Series LS-95-4.