CPM 2017

28th Annual Symposium on Combinatorial Pattern Matching

Warsaw, Poland, July 4-6, 2017

Conference

Papers and Proceedings

Local information

Other

Programme

Tuesday | Wednesday | Thursday

Tuesday, July 4, 2017

8:00 - 8:55
Registration
8:55 - 9:00
Welcome
 
Invited Talk I
9:00 - 10:00
Giovanni Manzini
Wheeler Graphs: Variations on a Theme by Burrows and Wheeler
 
10:00 - 10:20
Coffee Break
 
Session I
10:20 - 10:45
Gonzalo Navarro
Document Listing on Repetitive Collections with Guaranteed Performance
10:45 - 11:10
Travis Gagie, Meng He and Gonzalo Navarro
Path Queries on Functions
11:10 - 11:35
Philip Bille, Inge Li Gørtz and Frederik Rye Skjoldjensen
Deterministic Indexing for Packed Strings
 
11:35 - 11:45
Mini Break
 
Session II
11:45 - 12:10
Djamal Belazzougui and Fabio Cunial
Representing the suffix tree with the CDAWG
12:10 - 12:35
Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa and Ayumi Shinohara
Position Heaps for Parameterized Strings
12:35 - 13:00
Roberto Grossi, Costas Iliopoulos, Chang Liu, Nadia Pisanti, Solon Pissis, Ahmad Retha, Giovanna Rosone, Fatima Vayani and Luca Versari
On-line pattern matching on similar texts
 
13:00 - 14:30
Lunch
14:00 - 14:30
Tour of University Library gardens
 
Session III
14:30 - 14:55
Bartlomiej Dudek, Pawel Gawrychowski and Piotr Ostropolski-Nalewaja
A family of approximation algorithms for the maximum duo-preservation string mapping problem
14:55 - 15:20
Christian Komusiewicz, Mateus de Oliveira Oliveira and Meirav Zehavi
Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping
15:20 - 15:45
Karl Bringmann and Philip Wellnitz
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
 
15:45 - 16:10
Coffee Break
 
Session IV
16:10 - 16:35
Tatiana Starikovskaya
Communication and streaming complexity of approximate pattern matching
16:35 - 17:00
Mauro Castelli, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis
The Longest Filled Common Subsequence Problem
 
17:00 - 18:00
Apostolico Award and Business Meeting
18:00 -
Cocktail

Wednesday, July 5, 2017

Session V
9:00 - 9:25
Philip Bille, Patrick Hagge Cording, Johannes Fischer and Inge Li Gørtz
Lempel-Ziv Compression in a Sliding Window
9:25 - 9:50
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz and Hjalte Wedel Vildhøj
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
9:50 - 10:15
Alberto Policriti and Nicola Prezza
From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back
10:15 - 10:40
Tomohiro I
Longest Common Extensions with Recompression
 
10:40 - 11:00
Coffee Break
 
Invited Talk II
11:00 - 12:00
Artur Jeż
Recompression of SLPs
 
12:00 - 12:10
Mini Break
 
Session VI
12:10 - 12:35
Luis Cunha, Simone Dantas, Travis Gagie, Roland Wittler, Luis Kowada and Jens Stoye
Faster Jumbled Indexing for Binary RLE Strings
12:35 - 13:00
Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Faster STR-IC-LCS computation via RLE
 
13:00 - 14:30
Lunch
14:30 -
Excursion and Dinner*

Thursday, July 6, 2017

Session VII
9:00 - 9:25
Philippe Duchon, Cyril Nicaud and Carine Pivoteau
Gapped Pattern Statistics
9:25 - 9:50
Hideo Bannai, Shunsuke Inenaga and Dominik Köppl
Computing All Distinct Squares in Linear Time for Integer Alphabets
9:50 - 10:15
Dmitry Kosolobov, Mikhail Rubinchik, Kirill Borozdin and Arseny Shur
Palindromic Length in Linear Time
10:15 - 10:40
Takuya Mieno, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Tight bounds on the maximum number of shortest unique substrings
 
10:40 - 11:00
Coffee Break
 
Invited Talk III
11:00 - 12:00
Marcin Mucha
Shortest Superstring
 
12:00 - 12:10
Mini Break
 
Session VIII
12:10 - 12:35
Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin and Benny Porat
Can We Recover the Cover?
12:35 - 13:00
Amihood Amir, Avivit Levy, Ronit Lubin and Ely Porat
Approximate Cover of Strings
 
13:00 - 14:30
Lunch
 
Session IX
14:30 - 14:55
Laurent Bulteau, Guillaume Fertin and Christian Komusiewicz
Beyond Adjacency Maximization: Scaffold Filling for New String Distances
14:55 - 15:20
Manuel Lafond and Celine Scornavacca
On the Weighted Quartet Consensus problem
15:20 - 15:45
Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi and Alexandru I. Tomescu
Optimal Omnitig Listing for Safe and Complete Contig Assembly
 
15:45 - 16:10
Coffee Break
 
Session X
16:10 - 16:35
Giulio Ermanno Pibiri and Rossano Venturini
Dynamic Elias-Fano Representation
16:35 - 17:00
Carlos Ochoa, Jérémy Barbay and Srinivasa Rao Satti
Synergistic Solutions on MultiSets

*WARSAW PANORAMIC TOUR
Warsaw sightseeing bus tour with a guide (without entrances). Start: 2:30 p.m. from the entrance to the University of Warsaw Library. Traveling over the course of approximately five hours. Places to see:

After the bus tour there will be a gala dinner for all participants in Villa Foksal Restaurant from 7:30 to 10:00 p.m.