On June 27, 2024, at ACROS Fukuoka, Yasuo Tabei, leader of the Compressed Information Processing Team, delivered a special lecture at the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) during the highlight session.
Lecture Title: Optimal-Time Queries and Constructions of RLBWT in BWT-runs Bounded Space
The highlight session was designed to introduce the latest research outcomes in the field of Combinatorial Pattern Matching, focusing particularly on contributions that have the potential to advance the field.
This lecture was based on the following two papers presented at the major international conference on theoretical computer science, ICALP, in 2021 and 2022:
- Takaaki Nishimoto, Shunsuke Kanda, Yasuo Tabei: “Optimal-Time RLBWT Construction in BWT-runs Bounded Space”, 49th International Colloquium on Automata, Languages, and Programming (ICALP), 2022
- Takaaki Nishimoto and Yasuo Tabei: “Optimal-Time Queries on BWT-runs Compressed Indexes”, 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021
The lecture covered the topic of efficiently compressing and querying repetitive sequences, such as genomes, using the run-length encoded BWT (RLBWT) in an optimal computational time.
For more details, please visit the symposium’s website: CPM 2024 Official Website
