The 14th Workshop on Compression, Text and Algorithms (WCTA 2019) will be held the day after SPIRE (October 10th), chaired by Susana Ladra and José R. Paramá. WCTA is a forum primarily for early-stage researchers to present their work; there are no published proceedings so the results presented can also be submitted to most other workshops and conferences. WCTA venue is the same as for SPIRE; i.e. Campus Maria Zambrano. All talks will be presented at room A-014.

Important Dates

Abstract deadline: September 2nd, 2019 (anywhere on Earth)
Notification: September 11th, 2019
Workshop: October 10th, 2019

Keynote talk

Nadia Pisanti
Prof. Nadia Pisanti from the Department of Computer Science, University of Pisa will present the Keynote Talk of WCTA

Title: «On-line (approximate) Pattern Matching on Degenerate Texts and Applications».

Abstract: A degenerate text (D-text or D-string) is a string that actually represents (a multiple alignment of) a set of similar strings by collapsing common fragments into a standard linear string, and representing variants with sets of alternative substrings. When such substrings are not bound to have the same size, then we talk about elastic D-strings (ED-strings). In CPM 2017 we defined the «Elastic Degenerate String Matching» (EDSM) problem as that of finding an occurrence in an ED-text T of a pattern P of length m, and gave an O(nm^2+N) time on-line algorithm, where n is the length of T and N is its size, defined as the total number of letters. A fundamental toolkit of our algorithm is the O(m^2+N) time solution of the (later called) «Active Prefixes» (AP) problem». In CPM 2018, Aoyama et al. gave a O(m^{1.5} \sqrt{log m}+N) solution for AP leading to a O(nm^{1.5} \sqrt{log m}+N) time solution for EDSM using our CPM 2017 algorithmic framework. The natural open problem thus because whether the 1.5 exponent could furtherly be decreased. In our ICALP 2019 paper, we prove several properties that answer this and other questions. First, we give a conditional O(nm^{1.5}+N) lower bound for EDSM, proving that a *combinatorial* algorithm solving EDSM in O(nm^{1.5-\epsilon}+N) time implies to break the Boolean Matrix Multiplication (BMM) conjecture, which states that there is no truly sub-cubic combinatorial algorithm solving BMM. Second, we use this result as a hint to devise a *non-combinatorial* algorithm that solves EDSM in O(nm^{1.381}+N) time. We do so by succesfully combining Fast Fourier Transform and properties of string periodicity.

Programme

08:45	Opening and welcome
09:00	Keynote talk On-line (approximate) Pattern Matching on Degenerate Texts and Applications	Nadia Pisanti
10:00	Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication	Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon Pissis and Giovanna Rosone
10:30	Compressed Direct-Address Table – practical index for genomic sequences	Katarzyna Jabłonowska, Norbert Dojer and Michał Sabaciński
11:00	Coffee
11:30	Efficient SPARQL Triple Pattern Queries in HDT++	Antonio Hernández-Illera, Miguel A. Martínez-Prieto, Javier D. Fernández and Antonio Fariña
12:00	Pattern Matching on Transformed Data Using the Dead-Zone Approach	Melanie Mauch, Loek Cleophas and Bruce Watson
12:30	Practical mergeable dictionaries	Simon J. Puglisi and Massimiliano Rossi
13:00 13:30	Lunch (@ Hotel San Antonio El Real.)
15:00	Tree-Shape Grammars for Random Access	Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Louisa Seelbach Benkner and Yoshimasa Takabatake
15:30	BWT-Runs Minimization	Daniel Gibney, Sharma V. Thankachan and Jason Bentley
16:00	Coffee
16:30	Improving the slowest operations in Repetition-Aware Compressed Suffix Trees	Manuel Cáceres and Gonzalo Navarro
17:00	An exploration of Levenshtein neighborhood densities	Yoann Dufresne
17:30	Closing

Programme Chairs

Susana Ladra, University of A Coruña
José R. Paramá, University of A Coruña

Travel Grants for Students

BIRDS project will provide travel grants to all students presenting their work at WCTA 2019. WCTA is free for all attendees. Thus, travel grants can be used to cover transportation, meals on route, hotel room in Segovia and meal at WCTA. BIRDS will provide grants for all students with an accepted abstract. If the demand exceeds the available budget, travel grants may only cover a portion of the travel expenses, but in any case, at least 500 eur.

In line with the European Charter and Code for Researchers, BIRDS gives special focus to gender balance, as the gender imbalance in our community, and in IT in general, is well-known. Thus, BIRDS guarantees a minimum of 1,000 eur grant for female students presenting at WCTA.

The grant will be paid by reimbursement of costs. To get reimbursed, students will need to send, after the conference, a brief summary of their expenses, with the original receipts attached to a postal address we will provide. The sum of money allocated is a limit, and expenditures past the limit will not be reimbursed.

Application deadline: September 5th, 2019 (anywhere on Earth)
Notification: September 11th, 2019

Application Form: here .

Submission

Please, submit the abstract in PDF format using the following link: https://easychair.org/conferences/?conf=wcta19