CPM 2019

30th Annual Symposium on Combinatorial Pattern Matching

Pisa, Italy, June 18-20, 2019

Conference

Papers and Proceedings

Local information

Other

Programme

Welcome Cocktail on June 17 (Monday)
Aperitivo at Il Bistrot starting at 19:00.

Tuesday | Wednesday | Thursday

Tuesday, June 18, 2019

8:00 - 8:50
Registration
8:50 - 9:00
Opening Remarks
 
Invited Talk I
9:00 - 10:00
Paweł Gawrychowski
How to exploit periodicity
 
10:00 - 10:20
Coffee Break
 
Session I
10:20 - 10:45
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl and Marcin Piątkowski
Indexing the Bijective BWT
10:45 - 11:10
Raffaele Giancarlo, Giovanni Manzini, Giovanna Rosone and Marinella Sciortino
A New Class of Searchable and Provably Highly Compressible String Transformations
11:10 - 11:35
Nicola Prezza and Giovanna Rosone
Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
 
11:35 - 11:55
Break
 
Session II
11:55 - 12:20
Sung Gwan Park, Amihood Amir, Gad M. Landau and Kunsoo Park
Cartesian Tree Matching and Indexing
12:20 - 12:45
Djamal Belazzougui and Fabio Cunial
Fully-functional bidirectional Burrows-Wheeler indexes
12:45 - 13:10
Bastien Cazaux and Eric Rivals
Linking BWT and XBW via Aho-Corasick automaton: applications to Run-Length Encoding
 
13:10 - 14:30
Lunch
 
Highlight Talk I
14:30 - 15:00
Diptarka Chakraborty
Approximating edit distance within constant factor in truly sub-quadratic time
 
Session III
15:00 - 15:25
Diptarama Hendrian, Takuya Takagi and Shunsuke Inenaga
Online Algorithms for Constructing Linear-size Suffix Trie
15:25 - 15:50
Nicola Prezza
Optimal Rank and Select Queries on Dictionary-Compressed Text
 
15:50 - 16:10
Coffee Break
 
Session IV
16:10 - 16:35
Takaaki Nishimoto and Yasuo Tabei
Conversion from RLBWT to LZ77
16:35 - 17:00
Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations
 
17:00 - 17:30
Business Meeting

Wednesday, June 19, 2019

Invited Talk II
9:00 - 10:00
Michal Ziv-Ukelson
Stringology combats microbiological threats
 
10:00 - 10:20
Coffee Break
 
Session V
10:20 - 10:45
Diego Diaz-Dominguez, Travis Gagie and Gonzalo Navarro
Simulating the DNA string graph in succinct space
10:45 - 11:10
Niko Kiirala, Leena Salmela and Alexandru I. Tomescu
Safe and complete algorithms for dynamic programming problems, with an application to RNA folding
11:10 - 11:35
Haitao Jiang, Jiong Guo, Daming Zhu and Binhai Zhu
A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
 
11:35 - 11:55
Break
 
Session VI
11:55 - 12:20
Jan Studený and Przemysław Uznański
Approximating Approximate Pattern Matching
12:20 - 12:45
Mai Alzamel, Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
Quasi-Linear-Time Algorithm for Longest Common Circular Factor
12:45 - 13:10
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Faster queries for longest substring palindrome after block edit
 
13:10 - 14:30
Lunch
 
Highlight Talk II
14:30 - 15:00
Nicola Prezza
At the roots of dictionary compression: string attractors
 
Session VII
15:00 - 15:25
Pawel Gawrychowski, Jakub Radoszewski and Tatiana Starikovskaya
Quasi-periodicity in streams
15:25 - 15:50
Oleg Merkurev and Arseny Shur
Searching Long Repeats in Streams
 
15:50
Excursion and Conference Banquet

Excursion
Trip to Lucca from 16:00 to 20:00.

Conference Banquet
Dinner for all participants at La clessidra starting at 20:30.

Thursday, June 20, 2019

Invited Talk III
9:00 - 10:00
Antonio Restivo
Some variations on Lyndon words
 
10:00 - 10:20
Coffee Break
 
Session VIII
10:20 - 10:45
Hayam Alamro, Golnaz Badkobeh, Djamal Belazzougui, Costas S. Iliopoulos and Simon J. Puglisi
Computing the Antiperiod(s) of a String
10:45 - 11:10
Julian Pape-Lange
On Maximal Repeats in Compressed Strings
11:10 - 11:35
Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote and Brigitte Vallee
Dichotomic selection on words: a probabilistic analysis
 
11:35 - 11:55
Break
 
Session IX
11:55 - 12:20
Giulia Bernardini, Paola Bonizzoni, Gianluca Della Vedova and Murray Patterson
A rearrangement distance for fully-labelled trees
12:20 - 12:45
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniel Paulusma and Stephane Vialette
Finding a Small Number of Colourful Components
12:45 - 13:10
Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Computing runs on a trie
 
13:10 - 14:35
Lunch
 
Session X
14:35 - 15:00
Karim Labib, Przemysław Uznański and Daniel Wolleb-Graf
Hamming distance completeness
15:00 - 15:25
Pawel Gawrychowski and Tatiana Starikovskaya
Streaming dictionary matching with mismatches
15:25 - 15:50
Dmitry Kosolobov and Nikita Sivukhin
Compressed Multiple Pattern Matching
 
15:50 - 16:10
Coffee Break
 
Session XI
16:10 - 16:35
Eitan Kondratovsky and Amihood Amir
Sufficient Conditions for Efficient Indexing under Different Matchings
16:35 - 17:00
Michał Gańczorz
Entropy lower bounds for dictionary compression
 
17:00 - 17:05
Closing Remarks