Publications

publications by our members in reversed chronological order.

2024

  1. Proceedings
    Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
    Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara
    In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, 2024
    DOI
  2. Proceedings
    Algorithms for Galois Words: Detection, Factorization, and Rotation
    Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara
    In 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, June 25-27, 2024, Fukuoka, Japan, 2024
    DOI
  3. Proceedings
    Maintaining the Size of LZ77 on Semi-Dynamic Strings
    Hideo Bannai, Panagiotis Charalampopoulos, and Jakub Radoszewski
    In 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, June 25-27, 2024, Fukuoka, Japan, 2024
    DOI
  4. Preprint
    NP-Completeness for the Space-Optimality of Double-Array Tries
    Hideo Bannai, Keisuke Goto, Shunsuke Kanda, and Dominik Köppl
    arXiv, 2024
    DOI
  5. Proceedings
    Height-Bounded Lempel-Ziv Encodings
    Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda, and Simon J. Puglisi
    In 32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, 2024
    Awarded DOI
  6. Journal
    Constructing and indexing the bijective and extended Burrows-Wheeler transform
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski
    Inf. Comput., 2024
    DOI
  7. Preprint
    Bijective BWT based compression schemes
    Golnaz Badkobeh, Hideo Bannai, and Dominik Köppl
    arXiv, 2024
    DOI
  8. Preprint
    Algorithms for Galois Words: Detection, Factorization, and Rotation
    Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara
    arXiv, 2024
    DOI
  9. Proceedings
    Bijective BWT Based Compression Schemes
    Golnaz Badkobeh, Hideo Bannai, and Dominik Köppl
    In String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, 2024
    DOI
  10. Proceedings
    On the Number of Non-equivalent Parameterized Squares in a String
    Rikuya Hamai, Kazushi Taketsugu, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    In String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, 2024
    DOI
  11. Journal
    Linear time online algorithms for constructing linear-size suffix trie
    Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga, Keisuke Goto, and Mitsuru Funakoshi
    Theor. Comput. Sci., 2024
    DOI
  12. Proceedings
    Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages
    Yoshito Kawasaki, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara
    In SOFSEM 2024: Theory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Cochem, Germany, February 19-23, 2024, Proceedings, 2024
    DOI
  13. Journal
    Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, and Simon J. Puglisi
    Algorithmica, 2024
    DOI
  14. Proceedings
    Edit and Alphabet-Ordering Sensitivity of Lex-Parse
    Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai
    In 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, 2024
    DOI
  15. Journal
    Faster space-efficient STR-IC-LCS computation
    Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    Theor. Comput. Sci., 2024
    DOI
  16. Preprint
    Edit and Alphabet-Ordering Sensitivity of Lex-parse
    Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai
    arXiv, 2024
    DOI
  17. Journal
    Pfp-fm: an accelerated FM-index
    Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, and Travis Gagie
    Algorithms Mol. Biol., 2024
    DOI
  18. Proceedings
    On the Hardness of Smallest RLSLPs and Collage Systems
    Akiyoshi Kawamoto, Tomohiro I, Dominik Köppl, and Hideo Bannai
    In Data Compression Conference, DCC 2024, Snowbird, UT, USA, March 19-22, 2024, 2024
    DOI
  19. Proceedings
    Computing Maximal Palindromes in Non-standard Matching Models
    Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings, 2024
    DOI
  20. Preprint
    Height-bounded Lempel-Ziv encodings
    Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda, and Simon J. Puglisi
    arXiv, 2024
    DOI

2023

  1. Proceedings
    Optimal LZ-End Parsing Is Hard
    Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno
    In 34th Annual Symposium on Combinatorial Pattern Matching, CPM 2023, June 26-28, 2023, Marne-la-Vallée, France, 2023
    DOI
  2. Proceedings
    Lyndon Arrays in Sublinear Time
    Hideo Bannai, and Jonas Ellert
    In 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, 2023
    DOI
  3. Proceedings
    Acceleration of FM-Index Queries Through Prefix-Free Parsing
    Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, and Travis Gagie
    In 23rd International Workshop on Algorithms in Bioinformatics, WABI 2023, September 4-6, 2023, Houston, TX, USA, 2023
    DOI
  4. Journal
    Longest bordered and periodic subsequences
    Hideo Bannai, Tomohiro I, and Dominik Köppl
    Inf. Process. Lett., 2023
    DOI
  5. Journal
    Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
    Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theor. Comput. Sci., 2023
    DOI
  6. Journal
    Space-efficient Huffman codes revisited
    Szymon Grabowski, and Dominik Köppl
    Inf. Process. Lett., 2023
    DOI
  7. Proceedings
    Space-Efficient STR-IC-LCS Computation
    Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    In SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, Proceedings, 2023
    DOI
  8. Proceedings
    Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings
    Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    In String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26-28, 2023, Proceedings, 2023
    DOI
  9. Preprint
    Optimal LZ-End Parsing is Hard
    Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, and Takeaki Uno
    arXiv, 2023
    DOI
  10. Preprint
    Linear-time computation of generalized minimal absent words for multiple strings
    Kouta Okabe, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    arXiv, 2023
    DOI
  11. Preprint
    Acceleration of FM-index Queries Through Prefix-free Parsing
    Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, and Travis Gagie
    arXiv, 2023
    DOI
  12. Preprint
    Sliding suffix trees simplified
    Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno
    arXiv, 2023
    DOI
  13. Preprint
    Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
    Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2023
    DOI

2022

  1. Journal
    c-trie++: A dynamic trie tailored for fast prefix searches
    Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Inf. Comput., 2022
    DOI
  2. Preprint
    Augmented Thresholds for MONI
    César Martı́nez-Guardiola, Nathaniel K. Brown, Fernando Silva-Coira, Dominik Köppl, Travis Gagie, and Susana Ladra
    arXiv, 2022
    DOI
  3. 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic
    2022
  4. Journal
    Factorizing Strings into Repetitions
    Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theory Comput. Syst., 2022
    DOI
  5. Journal
    Graph Compression for Adjacency-Matrix Multiplication
    Alexandre P. Francisco, Travis Gagie, Dominik Köppl, Susana Ladra, and Gonzalo Navarro
    SN Comput. Sci., 2022
    DOI
  6. Journal
    Correction to: Graph Compression for Adjacency-Matrix Multiplication
    Alexandre P. Francisco, Travis Gagie, Dominik Köppl, Susana Ladra, and Gonzalo Navarro
    SN Comput. Sci., 2022
    DOI
  7. Preprint
    Computing NP-hard Repetitiveness Measures via MAX-SAT
    Hideo Bannai, Keisuke Goto, Masakazu Ishihata, Shunsuke Kanda, Dominik Köppl, and Takaaki Nishimoto
    arXiv, 2022
    DOI
  8. Preprint
    Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
    Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno
    arXiv, 2022
    DOI
  9. Journal
    Palindromic trees for a sliding window and its applications
    Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Inf. Process. Lett., 2022
    DOI
  10. Proceedings
    FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
    Jin Jie Deng, Wing-Kai Hon, Dominik Köppl, and Kunihiko Sadakane
    In Data Compression Conference, DCC 2022, Snowbird, UT, USA, March 22-25, 2022, 2022
    DOI
  11. Preprint
    Space-Efficient STR-IC-LCS Computation
    Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, and Hideo Bannai
    arXiv, 2022
    DOI
  12. Journal
    Parameterized DAWGs: Efficient constructions and bidirectional pattern searches
    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda
    Theor. Comput. Sci., 2022
    DOI
  13. Journal
    Combinatorics of minimal absent words for a sliding window
    Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theor. Comput. Sci., 2022
    DOI
  14. Proceedings
    HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
    Dominik Köppl, Gonzalo Navarro, and Nicola Prezza
    In Data Compression Conference, DCC 2022, Snowbird, UT, USA, March 22-25, 2022, 2022
    DOI
  15. Proceedings
    Computing Lexicographic Parsings
    Dominik Köppl
    In Data Compression Conference, DCC 2022, Snowbird, UT, USA, March 22-25, 2022, 2022
    DOI
  16. Proceedings
    Accessing the Suffix Array via \(\varphi\) \(^\mbox-1\)-Forest
    Christina Boucher, Dominik Köppl, Herman Perera, and Massimiliano Rossi
    In String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8-10, 2022, Proceedings, 2022
    DOI
  17. Journal
    Order-preserving pattern matching indeterminate strings
    Luı́s M. S. Russo, Diogo M. Costa, Rui Henriques, Hideo Bannai, and Alexandre P. Francisco
    Inf. Comput., 2022
    DOI
  18. Proceedings
    Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions
    Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, and Takuya Mieno
    In String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8-10, 2022, Proceedings, 2022
    DOI
  19. Proceedings
    Computing the Parameterized Burrows-Wheeler Transform Online
    Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara
    In String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8-10, 2022, Proceedings, 2022
    DOI
  20. Journal
    Fast and Simple Compact Hashing via Bucketing
    Dominik Köppl, Simon J. Puglisi, and Rajeev Raman
    Algorithmica, 2022
    DOI
  21. Proceedings
    Computing NP-Hard Repetitiveness Measures via MAX-SAT
    Hideo Bannai, Keisuke Goto, Masakazu Ishihata, Shunsuke Kanda, Dominik Köppl, and Takaaki Nishimoto
    In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, 2022
    DOI
  22. Journal
    Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
    Paolo Ferragina, Giovanni Manzini, Travis Gagie, Dominik Köppl, Gonzalo Navarro, Manuel Striani, and Francesco Tosoni
    Proc. VLDB Endow., 2022
  23. Journal
    Linking Off-Road Points to Routing Networks
    Dominik Köppl
    Algorithms, 2022
    DOI
  24. Proceedings
    Computing Longest (Common) Lyndon Subsequences
    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, and Simon J. Puglisi
    In Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, 2022
    Awarded DOI
  25. Proceedings
    Space-Efficient B Trees via Load-Balancing
    Tomohiro I, and Dominik Köppl
    In Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, 2022
    DOI
  26. Journal
    Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks
    Dominik Köppl
    Inf., 2022
    DOI
  27. Preprint
    Computing the Parameterized Burrows-Wheeler Transform Online
    Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, and Ayumi Shinohara
    arXiv, 2022
    DOI
  28. Preprint
    Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
    Paolo Ferragina, Travis Gagie, Dominik Köppl, Giovanni Manzini, Gonzalo Navarro, Manuel Striani, and Francesco Tosoni
    arXiv, 2022
    DOI
  29. Preprint
    Computing Longest (Common) Lyndon Subsequences
    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, and Simon J. Puglisi
    arXiv, 2022
  30. Preprint
    Longest (Sub-)Periodic Subsequence
    Hideo Bannai, Tomohiro I, and Dominik Köppl
    arXiv, 2022
  31. Journal
    Computing Minimal Unique Substrings for a Sliding Window
    Takuya Mieno, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Algorithmica, 2022
    DOI
  32. Preprint
    Computing maximal generalized palindromes
    Mitsuru Funakoshi, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2022
    DOI

2021

  1. Preprint
    Space-Efficient Huffman Codes Revisited
    Szymon Grabowski, and Dominik Köppl
    arXiv, 2021
  2. Preprint
    On Arithmetically Progressed Suffix Arrays and related Burrows-Wheeler Transforms
    Jacqueline W. Daykin, Dominik Köppl, David Kübel, and Florian Stober
    arXiv, 2021
  3. Journal
    Re-Pair in Small Space
    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, and Keisuke Goto
    Algorithms, 2021
    DOI
  4. Proceedings
    Grammar Index by Induced Suffix Sorting
    Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, 2021
    DOI
  5. Journal
    Engineering Practical Lempel-Ziv Tries
    Diego Arroyuelo, Rodrigo Cánovas, Johannes Fischer, Dominik Köppl, Marvin Löbel, Gonzalo Navarro, and Rajeev Raman
    ACM J. Exp. Algorithmics, 2021
    DOI
  6. Journal
    The Smallest Grammar Problem Revisited
    Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jez, Markus Lohrey, and Carl Philipp Reh
    IEEE Trans. Inf. Theory, 2021
    DOI
  7. Journal
    Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees
    Dominik Köppl
    Algorithms, 2021
    DOI
  8. Proceedings
    Repetitions in Strings: A "Constant" Problem (Invited Talk)
    Hideo Bannai
    In 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland, 2021
    DOI
  9. Proceedings
    Longest Common Rollercoasters
    Kosuke Fujita, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, 2021
    DOI
  10. Proceedings
    A Separation of \(γ\) and b via Thue-Morse Words
    Hideo Bannai, Mitsuru Funakoshi, Tomohiro I, Dominik Köppl, Takuya Mieno, and Takaaki Nishimoto
    In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, 2021
    DOI
  11. Proceedings
    Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree
    Tomohiro I, Robert W. Irving, Dominik Köppl, and Lorna Love
    In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, 2021
    DOI
  12. Journal
    Efficiently computing runs on a trie
    Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theor. Comput. Sci., 2021
    DOI
  13. Journal
    Computing longest palindromic substring after single-character or block-wise edits
    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theor. Comput. Sci., 2021
    DOI
  14. Preprint
    Combinatorics of minimal absent words for a sliding window
    Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2021
  15. Preprint
    Grammar Index By Induced Suffix Sorting
    Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2021
  16. Journal
    Reversed Lempel-Ziv Factorization with Suffix Trees
    Dominik Köppl
    Algorithms, 2021
    DOI
  17. Journal
    Longest previous overlapping factor array
    Hideo Bannai, Shunsuke Inenaga, and Neerja Mhaskar
    Inf. Process. Lett., 2021
    DOI
  18. Proceedings
    Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski
    In 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland, 2021
    DOI
  19. Proceedings
    PHONI: Streamed Matching Statistics with Multi-Genome References
    Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, and Massimiliano Rossi
    In 31st Data Compression Conference, DCC 2021, Snowbird, UT, USA, March 23-26, 2021, 2021
    DOI
  20. Proceedings
    The Parameterized Suffix Tray
    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In Algorithms and Complexity - 12th International Conference, CIAC 2021, Virtual Event, May 10-12, 2021, Proceedings, 2021
    DOI
  21. Journal
    Compressed Communication Complexity of Hamming Distance
    Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Algorithms, 2021
    DOI
  22. Preprint
    A Separation of \(γ\) and b via Thue-Morse Words
    Hideo Bannai, Mitsuru Funakoshi, Tomohiro I, Dominik Köppl, Takuya Mieno, and Takaaki Nishimoto
    arXiv, 2021
  23. Preprint
    Load-Balancing Succinct B Trees
    Tomohiro I, and Dominik Köppl
    arXiv, 2021
  24. Preprint
    Compressed Communication Complexity of Hamming Distance
    Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2021
  25. Preprint
    FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns
    Jin Jie Deng, Wing-Kai Hon, Dominik Köppl, and Kunihiko Sadakane
    arXiv, 2021
  26. Preprint
    HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
    Dominik Köppl, Gonzalo Navarro, and Nicola Prezza
    arXiv, 2021

2020

  1. Preprint
    In-Place Bijective Burrows-Wheeler Transforms
    Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian, and Ayumi Shinohara
    arXiv, 2020
  2. Preprint
    Lyndon Words, the Three Squares Lemma, and Primitive Squares
    Hideo Bannai, Takuya Mieno, and Yuto Nakashima
    arXiv, 2020
  3. Journal
    Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
    Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theory Comput. Syst., 2020
    DOI
  4. Proceedings
    Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Ayumi Shinohara
    In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, 2020
    DOI
  5. Preprint
    Grammar-compressed Self-index with Lyndon Words
    Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020
  6. Journal
    Practical Grammar Compression Based on Maximal Repeats
    Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Takuya Kida
    Algorithms, 2020
    DOI
  7. Proceedings
    DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures
    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda
    In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, 2020
    DOI
  8. Preprint
    PHONI: Streamed Matching Statistics with Multi-Genome References
    Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, and Massimiliano Rossi
    arXiv, 2020
  9. Journal
    More Time-Space Tradeoffs for Finding a Shortest Unique Substring
    Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, and Luı́s M. S. Russo
    Algorithms, 2020
    DOI
  10. Proceedings
    Towards Efficient Interactive Computation of Dynamic Time Warping Distance
    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, 2020
    DOI
  11. Proceedings
    Longest Square Subsequence Problem Revisited
    Takafumi Inoue, Shunsuke Inenaga, and Hideo Bannai
    In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, 2020
    DOI
  12. Proceedings
    On Repetitiveness Measures of Thue-Morse Words
    Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, 2020
    Awarded DOI
  13. Proceedings
    Lyndon Words, the Three Squares Lemma, and Primitive Squares
    Hideo Bannai, Takuya Mieno, and Yuto Nakashima
    In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, 2020
    DOI
  14. Journal
    Dynamic Path-decomposed Tries
    Shunsuke Kanda, Dominik Köppl, Yasuo Tabei, Kazuhiro Morita, and Masao Fuketa
    ACM J. Exp. Algorithmics, 2020
    DOI
  15. Preprint
    Longest Square Subsequence Problem Revisited
    Takafumi Inoue, Shunsuke Inenaga, and Hideo Bannai
    arXiv, 2020
  16. Preprint
    Computing Palindromic Trees for a Sliding Window and Its Applications
    Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020
  17. Preprint
    The Parameterized Suffix Tray
    Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020
  18. Journal
    Space-efficient algorithms for computing minimal/shortest unique substrings
    Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    Theor. Comput. Sci., 2020
    DOI
  19. Preprint
    DAWGs for parameterized matching: online construction and related indexing structures
    Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, and Masayuki Takeda
    arXiv, 2020
  20. Preprint
    Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Ayumi Shinohara
    arXiv, 2020
  21. Preprint
    Towards Efficient Interactive Computation of Dynamic Time Warping Distance
    Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020
  22. Preprint
    On repetitiveness measures of Thue-Morse words
    Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020
  23. Preprint
    Faster STR-EC-LCS Computation
    Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda
    arXiv, 2020