Publications

Volumes and Journal Special Issues

1 - R. Giancarlo and D. Sankoff Eds., Proc. of 11th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Springer-Verlag, Vol. 1848.

2 - R. Giancarlo and D. Sankoff Editors, Pattern Matching Algorithms, Special Issue of Journal of Descrete Algorithms, Vol. 2, 2004.

3 - A. Apostolico and R. Giancarlo, Pattern Discovery in the Post-Genome, Special Issue of Theoretical Computer Science, Vol. 335, 2005.

4 - A. Apostolico, R. Giancarlo, C. Guerra and G. Lancia, Articles selected from posters presented at the Tenth Annual International Conference on Research in Computational Biology - Preface and Special Issue. BMC Bioinformatics (on line) Vol. 8, pp. 1471-2105, 2007.

5 - R. Giancarlo, S. Hannenhalli, Algorithms in Bioinformatics, 7th International Workshop, WABI 2007, Philadelphia, PA, USA, September 8-9, 2007, Proceedings Springer 2007.

Invited Contributions

1 - Z. Galil and R. Giancarlo, Data Structures and Algorithms for Approximate String Matching, J. of Complexity, 4, (1988), pp. 33-72.

2 - D. Eppstein, Z. Galil and R. Giancarlo, Efficient Algorithms for Molecular Biology, Sequences: Combinatorics, Compression, Security, Transmission, R.M. Capocelli Ed., Springer-Verlag (1990), pp. 59-74.

3 - D. Eppstein, Z. Galil, R. Giancarlo and G. Italiano, Efficient Sequence Alignment Algorithms; Sequences II: Combinatorics, Compression, Security, Transmission, R.M. Capocelli Ed., Springer-Verlag, (1992), pp. 225-244.

4 - R. Giancarlo, Dynamic Programming-Special Cases, in Pattern Matching Algorithms, A. Apostolico and Z. Galil Eds., Oxford University Press, 1997, pp. 201-236.

5 - R. Giancarlo and R. Grossi, Suffix Tree Data Structures for Matrices, in Pattern Matching Algorithms, A. Apostolico e Z. Galil Eds., Oxford University Press, (1997), pp. 293-340.

6 - A. Apostolico and R. Giancarlo, Sequence Alignment in Molecular Biology, in DIMACS Special Year for Mathematical Support of Molecular Biology, M. Farach, F. Roberts M. Vingron and M.S. Waterman Eds., American Mathematical Society, DIMACS Series in Dicrete Mathematics, pp. 85-115 (1999).

7 - R. Giancarlo and R. Grossi, Parallel Construction and Query of Index Data Structures for Pattern Matching on Square Matrices, J. of Complexity, 15, (1999), pp. 30-71.

8 - R. Giancarlo and D. Guaiana, On-Line Construction of Two-Dimensional Suffix Trees, Journal of Complexity, 15, (1999), pp. 72-127.

9 - A.L. Buchsbaum and R. Giancarlo, Algorithmic Aspects of Speech Recognition: A Synopsis, Proc. 11th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1848, pp. 27-32.

10 - Raffaele Giancarlo, Sabrina Mantaci, I Contributi delle Scienze Matematiche ed Informatiche al Sequenziamento Genomico su Larga Scala, Contributo invitato in ``La Matematica nella Societ\'a e nella Cultura, Bollettino della Unione Matematica Italiana, Vol. 8, 4-A, (2001), pp. 33-62.

Proceedings of Refereed Conferences

1 - A. Apostolico and R. Giancarlo, Elaborating on the Boyer-Moore- Galil String Searching Strategies, Proc. 20th Allerton Conference on Communication, Control and Computing, Monticello, Ill., (1982), pp. 924-933.

2 - R. Giancarlo and W. Rytter, Optimal Parallel Parsing of Bracket Languages, Proc. Inter. Workshop on Parallel Algorithms and Architectures , A. Albrecht, H. Jung and K. Mehlhorn Eds., Lecture Notes in Computer Science, Vol. 269, Springer-Verlag, (1987), pp. 146-154.

3 - D. Eppstein, Z. Galil and R. Giancarlo, Speeding up Dynamic Programming, Proc. 29-th IEEE Conference on Foundations of Computer Science, (1988), pp. 488-495.

4 - D. Eppstein, Z. Galil, R. Giancarlo and G. Italiano, Sparse Dynamic Programming, Extended Abstract, Proc. first ACM-SIAM Symposium on Descrete Algorithms, (1990), pp. 513-522.

5 - L. Colussi, Z. Galil and R. Giancarlo, On the Exact Complexity of String Matching; Extended Abstract, Proc. 31-th IEEE Foundations of Computer Science, (1990), pp. 135-144.

6 - R. Giancarlo, The Suffix Tree of a Square Matrix, Extended Abstract, 4-th ACM SIAM Symposium on Descrete Algorithms, (1993), pp. 402-412.

7 - R. Giancarlo and R. Grossi, Parallel Construction and Query of Suffix Trees for Two-Dimensional Matrices, Extended Abstract, 5-th ACM Symposium on Parallel Algorithms and Architectures, (1993), pp. 86-97.

8 - R. Giancarlo, An index Data Structure for Matrices, with Applications to Fast Two-Dimensional Pattern Matching, Extended Abstract, Workshop on Algorithms and Data Structures, F. Dehne, J. Sack, N. Santoro and S. Whitesides Eds., Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, (1993), pp. 67-76.

9 - R. Giancarlo and F. Mignosi, A Generalization of the Theorem by Fine and Wilf, Colloquium on Algebra, Automata Programming, Lecture Notes in Computer Science, Vol. 787, Springer-Verlag, (1993), pp. 130-141.

10 - R. Giancarlo and R. Grossi, On The Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications, 22nd Int. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 944, Springer-Verlag, (1995), pp. 111-123.

11 - R. Giancarlo and R. Grossi, Multi-Dimensional Pattern Matching with Dimensional Wildcards, Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 937, (1995), pp. 90-101.

12 - R. Giancarlo and D. Guaiana, On-Line Construction of Two-Dimensional Suffix Trees, Extended Abstract, European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 1284, Springer-Verlag, (1997), pp. 217-231.

13 - A.L. Buchsbaum, R. Giancarlo and J. Westbrook, Shrinking Language Models by Robust Approximation, Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, (1998), pp. 1215-1219.

14 - A.L. Buchsbaum, R. Giancarlo and J. Westbrook, On the Derminization of Weighted Automata, Proc. of International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 1443, Springer-Verlag, (1998), pp.482-493.

15 - B.S. Baker and R. Giancarlo, Longest Common Subsequence from Fragments via Sparse Dynamic Programming, Proc. of European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 1461, Springer-Verlag, (1998), pp. 79-90.

16 - Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo, Improving Table Compression with Combinatorial Optimization, Proc. ACM-SIAM Symposium on Descrete Algorithms, (2002), pp. 213-222.

17 - R. Giancarlo and M. Sciortino, Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms, Proc. of Combinatorial Pattern Matching 2003, Lecture Notes in Computer Science, (2003), pp. 129-143.

18 - M. Crochemore, R. Giancarlo and M.F. Sagot, Longest Motifs with a Functionally Equivalent Central Block, Proc. of SPIRE 2004, Lecture Notes in Computer Science, Vol. 3246 (2004), pp. 298-310.

19 - Joong Chae Na, R. Giancarlo and K. Park, $O(n^2 \log n)$ Time On-line Construction of Two-Dimensional Suffix Trees, COCOON 05, Lecture Notes in Computer Science, Vol. 3595 (2005), pp. 273-282.

20 - A. Apostolico and R. Giancarlo, Periodicity and Repetitions in Parameterized Strings, Proc. of ZiF Special Year in Information Theory and Combinatorics, Electronic Notes in Discrete Mathematics, Vol. 21, pp. 227-230.

21 - J.C. Na, R. Giancarlo and K. Park, An O(n^2log n) Time on-line construction of two dimensional suffix trees, Lectures Notes in Computer Science, Vol.  3595, pp. 273-282, 2005.

22 - P. Ferragina, R. Giancarlo and G. Manzini, The Myriad Virtues of Suffix Trees, Lectures Notes in Computer Science, Vol. 4051, pp. 560-571, 2006.

23 - P. Ferragina, R. Giancarlo and G. Manzini, The Engineering of a Compression Booster: Theroy Vs Practice in BWT Compression, Lectures Notes in Computer Science, Vol. 4168, pp. 756-767, 2006.

Refereed Journals

1 - A. Apostolico and R. Giancarlo, Pattern Matching Machine Implementation of a Fast Test for Unique Decipherability, Information Processing Letters, 18, (1984), pp. 155-158.

2 - A. Apostolico and R. Giancarlo, The Boyer-Moore-Galil String Searching Strategies Revisited, SIAM J. on Computing, 15, (1986), pp. 98-105.

3 - Z. Galil and R. Giancarlo, Improved String Matching with $k$ Mismatches, SIGACT NEWS, 62, (1986), pp. 52-54.

4 - R.M. Capocelli, R. Giancarlo and I.J. Taneja, Bounds on the Redundancy of Huffman Codes, IEEE Transaction on Information Theory, 32, (1986), pp. 854-857.

5 - R. Giancarlo and W. Rytter, Optimal Parallel Parsing of Bracket Languages, Theoretical Computer Science, 53, (1987), pp. 295-306.

6 - R. Giancarlo and W. Rytter, A Transformation of Nondeterministic Recursive Programs to Efficient Deterministic Ones, Fundamentae Informaticae, 10, (1987), pp. 149-160.

7 - Z. Galil and R. Giancarlo, Parallel String Matching with $k$ mismatches, Theoretical Computer Science, 51, (1987), pp. 341-384.

8 - R.M. Capocelli and R. Giancarlo, Efficient VLSI Networks for Converting an Integer from Binary System to Residue Number System and Viceversa, IEEE Transactions on Circuits and Systems, 35,(1988).

9 - Z. Galil and R. Giancarlo, Speeding up Dynamic Programming with Applications to Molecular Biology, Theoretical Computer Science, 64, (1989), pp 107-118.

10 - Z. Galil and R. Giancarlo, On the Exact Complexity of String Matching: Lower Bounds; SIAM J. on Computing, 20, (1991), pp. 1008-1020.

13 - D. Eppstein, Z. Galil, R. Giancarlo and G. Italiano, Sparse Dynamic Programming I: Linear Cost Functions, Journal of ACM, 39, (1992), pp. 519-545.

12 - D. Eppstein, Z. Galil, R. Giancarlo and G. Italiano, Sparse Dynamic Programming II: Convex and Concave Cost Functions, Journal of ACM, 39, (1992), pp. 546-567.

13 - Z. Galil and R. Giancarlo, On the Exact Complexity of String Matching: Upper Bounds; SIAM J. on Computing, 21, (1992), pp. 407-437.

14 - A. Amir, M. Farach, Z. Galil, R. Giancarlo and K. Park, Fully Dynamic Dictionary Matching, Journal of Computer and System Sciences, 49, (1994), pp.208-222.

15 - R. Giancarlo, A Generalization of the Suffix Tree to Matrices, with Applications, SIAM J. on Computing, 24, (1995), pp. 520-562.

16 - R. Giancarlo and R. Grossi, On The Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications, Information and Computation, 130, (1996), pp. 151-182.

17 - R. Giancarlo and R. Grossi, Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Algorithms, Journal of Algorithms, Vol. 24, (1997), 223-265.

18 - A. Buchsbaum and R. Giancarlo, Algorithmic Aspects of Speech Recognition: An Introduction, ACM Journal on Experimental Algorithmics, (1997).

19 - A. Apostolico and R. Giancarlo, Sequence Alignment in Molecular Biology, Journal of Computational Biology, Vol. 5, (1998), pp. 173-196.

20 - Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook, On the Determinization of Weighted Finite Automata. SIAM J. Comput., Vol. 30, (2000), pp. 1502-1531.

21 - Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook: An Approximate Determinization Algorithm for Weighted Finite-State Automata, Algorithmica, Vol. 30, (2001), pp. 503-526.

22 - Brenda S. Baker, Raffaele Giancarlo, Sparse Dynamic Programming for Longest Common Subsequence from Fragments. J. Algorithms, Vol. 42, (2002), pp. 231-254.

23 - A.L. Buchsbaum, Raffaele Giancarlo, J.R. Westbrook, On Finding Common Neighborhoods in Massive Graphs, Theoretical Computer Science, Vol. 299, (2003), pp. 707-718.

24 - Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo, Improving Table Compression with Combinatorial Optimization, J. of ACM, Vol. 50, pp. 825-851, (2003)

25 - P. Ferragina, R. Giancarlo, G. Manzini and M. Sciortino, Boosting Textual Compression in Optimal Linear Time, J. of ACM, Vol. 52 (2005), pp. 688-713.

26 - V. Di Gesu, R. Giancarlo, G. Lo Bosco, A. Raimondi, D. Scaturro, GenClust: A Genetic Algorithm for Clustering of Gene Expression Data, BMC Bioinformatics, Vol. 6 (2005), pp. 289

27 - A. Apostolico and R. Giancarlo, Periodicity and Repetitions in Parameterized Strings, Extended Abstract, Electronic Notes in Discrete Mathematics, Vol. 21 (2005), pp. 227-230.

28 - V. Vesco, A. Siragusa, R. Giancarlo and G. Ghersi, Differential Expression of Proteolytic Enzymes during Epithelia - Mesenchyma Transaction of Endothelial cells, Cell Biology International, Vol.  21 (2005), pp. 227-230.

29 - J. C. Na, R. Giancarlo and K. Park, An O(n^2log n) Time on-line construction of two dimensional suffix trees, Algorithmica, Vol. 48 (2007), pp. 173-186.

30 -  R. Giancarlo, A. Siragusa, E. Siragusa and F. Utro, A Basic Analysis Toolkit for Biological Sequences, Algorithms for Molecular Biology, Vol. 2 (2007), pp. 10.

31 - R. Giancarlo, M. Sciortino and A. Restivo, From First Principals to the Burrows and Wheeler Transform, via Combinatorial Optimization, Theoretical Computer Science, Vol. 387 (2007), pp. 236-248.

32 - P. Ferragina, R. Giancarlo, V. Greco, G. Manzini and G. Valiente, Compression-Based Classification of Biological Sequences and Structures via the Universal Similarity Metric: Experimental Assessment,  BMC Bioinformatics, Vol. 8 (2007), pp. 252.

33 - A. Apostolico and R. Giancarlo, Periodicity and Repetitions in Parameterized Strings, Discrete Applied Mathematics, Vol. 156 (2008), pp. 1389-1398.

Technical Reports

1 - D. Eppstein, Z. Galil and R. Giancarlo, Speeding up Dynamic Programming with Applications to the Computation of RNA Secondary Structure, Tech. Rep., Dept. of Computer Science, Columbia University, New York, U.S.A..

2 - R. Giancarlo, Efficient Algorithms on Strings, Ph.D. Thesis, Tech. Rep., Dept. of Computer Science, Columbia University, New York, U.S.A..

3 - R. Giancarlo, On the Construction of Index Data Structures for Matrices: A Lower Bound, Tech Report 11272-930614-21, AT&T Bell Laboratories, Murray Hill, N.J., USA.

4 - R. Giancarlo and R. Grossi, Parallel Construction and Query of Suffix Trees for Square Matrices, Tech Report 11272-931015-26, AT&T Bell Laboratories, Murray Hill, N.J., USA.

5 - A.L. Buchsbaum, R. Giancarlo and J. Westbrook, On Reduction via Determinization of Speech-Recognition Lattices, AT&T Labs Research Report 97.21.1, 1997.

6 - A.L. Buchsbaum, R. Giancarlo and J. Westbrook, Experimental Design of an Algorithm for Compressing Speech Recognition Models, AT&T Labs Research Report 97.21.1, 1997.