Updated on 2024/11/21

写真a

 
KOEPPL Dominik
 
Organization
Graduate Faculty of Interdisciplinary Research Faculty of Engineering Electrical and Electronic Information Engineering (Computer Science and Engineering) Associate Professor
Title
Associate Professor
Homepage
https://dkppl.de/cowasp/
External link

Research History

  • University of Yamanashi

    2023.9

    　 More details

    Job classification：Professor

    researchmap

  • Tokyo Medical and Dental University   M&D Data Center   part-time lecturer

    2023.4

    　 More details

    Country：Japan

    Job classification：Lecturer (part-time)

    researchmap

  • Tokyo Medical and Dental University   M&D Data Center   Assistant Professor

    2020.9 - 2023.3

    　 More details

    Country：Japan

    researchmap

Research Areas

  • Informatics / High performance computing

  • Informatics / Intelligent informatics

  • Informatics / Theory of informatics

Research Interests

  • Combinatorics on words

  • string processing

  • information retrieval

  • compressed data structures

  • data structure

  • data compression

  • Algorithms

Research Projects

Papers

  • 未決定文字列における欠如単語の検索の困難さ

    Dominik Köppl; Jannik Olbrich

    Local Proceedings of the 200th アルゴリズム研究会   200 ( 7 )   1 - 5   2024.11

    　More details

    Authorship：Corresponding author   Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • Bijective BWT based Compression Schemes Reviewed

    Golnaz Badkobeh; Hideo Bannai; Dominik Köppl

    Proc. SPIRE   14899   16 - 25   2024.9

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    We put the bijective Burrows-Wheeler transform into the landscape of compressivitiy measures by drawing connections to bidirectional macro schemes, study the number of runs with respect to the classic Burrows-Wheeler transform, give a linear-time algortihm for computing the Lyndon factorization of all cyclic rotations of a text, and conjecture that strings with the same Parikh-vector can be bijectively mapped by a sequence of cyclic rotatations and bijective Burrows-Wheeler transform applications.

    DOI： 10.1007/978-3-031-72200-4_2

    researchmap

  • LZ78 Substring Compression with CDAWGs Reviewed

    Hiroki Shibata; Dominik Köppl

    Proc. SPIRE   14899   289 - 305   2024.9

    　More details

    Authorship：Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)  

    We study the substring compression in the LZ78 scheme introduced in \cite{koppl21nonoverlapping} with a compressed text index. The presented solution has superlinear running time with respcet to the number of factors to compute, but can use space asymptotically smaller than the text size.

    DOI： 10.1007/978-3-031-72200-4_22

    researchmap

  • Edit and Alphabet-Ordering Sensitivity of Lex-Parse Reviewed

    Yuto Nakashima; Dominik Köppl; Mitsuru Funakoshi; Shunsuke Inenaga; Hideo Bannai

    Proc. MFCS   306   75:1 - 75:15   2024.8

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    We give tight logarithmic bounds on the change of the number of factors produced by the lex-parse compression scheme when we change a single character of the input or change the order of the alphabet.

    DOI： 10.4230/LIPIcs.MFCS.2024.75

    researchmap

  • 対数的な幅を持つ疎行列圧縮のNP完全性

    坂内 英夫; 後藤 啓介; 田 峻介; クップル ドミニク

    Local Proceedings of the LA Symposium Summer 2024   ( 15 )   2024.7

    　More details

    Authorship：Corresponding author   Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching Reviewed

    Kento Iseri; Tomohiro I; Diptarama Hendrian; Dominik Köppl; Ryo Yoshinaka; Ayumi Shinohara

    Proc. ICALP   297   89:1 - 89:19   2024.7

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    We adapt the online Burrows-Wheeler transform construction on the reversed text for constructing the parameterized Burrows-Wheeler transform like in \cite{hashimoto22computing}. By binary searching the interval for the insertion position, we obtain the first construction algorithm of pamaterized indexes whose time only logarithmically depend on the parameterized alphabet size. Up to that point, only linear-dependence has been known.

    DOI： 10.4230/LIPICS.ICALP.2024.89

    researchmap

  • CDAWG による LZ78 部分文字列圧縮

    柴田 紘希; クップル ドミニク

    Local Proceedings of the LA Symposium Summer 2024   ( 13 )   2024.7

    　More details

    Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • Algorithms for Galois Words: Detection, Factorization, and Rotation Reviewed

    Diptarama Hendrian; Dominik Köppl; Ryo Yoshinaka; Ayumi Shinohara

    Proc. CPM   296   18:1 - 18:16   2024.6

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    Galois words are conceptually Lyndon words based on the alternating order, for which we give algorithms to determine whether a word is Galois, to factorize a non-Galoid word into Galois words in a unique manner like the Lyndon factorization, and to find the rotation of a word that is Galois. All algorithms work in linear time.

    DOI： 10.4230/LIPICS.CPM.2024.18

    researchmap

  • On arithmetically progressed suffix arrays and related Burrows–Wheeler transforms Reviewed

    Jacqueline W. Daykin; Dominik Köppl; David Kübel; Florian Stober

    Discrete Applied Mathematics   355   2024.4( ISSN：0166-218X )

    　More details

    Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

    Compared to the conference version~\cite{daykin20arithmetically}, we here additionally analyze the shapes of Burrows-Wheeler transforms of strings whose suffix arrays are arithmetically progressed. Additionally, we give applications for Christoffel words, balanced words, and meta strings. Finally, we extend our study on binary and ternary alphabets to general alphabets.

    DOI： 10.1016/j.dam.2024.04.009

    researchmap

  • Pfp-fm: an accelerated FM-index Reviewed International coauthorship

    Aaron Hong; Marco Oliva; Dominik Köppl; Hideo Bannai; Christina Boucher; Travis Gagie

    Algorithms for Molecular Biology   19 ( 15 )   1 - 14   2024.4( ISSN：1748-7188 )

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    Journal version of \cite{hong23acceleration}. We improved the space bounds by run-length encoding both FM-indexes. We called this solution PFP-FM-CSA in the article. Compared to the conference version, this implementation has higher memory consumption during the construction, but significantly smaller index sizes.

    DOI： 10.1186/s13015-024-00260-8

    researchmap

  • Computing LZ78-Derivates with Suffix Trees Reviewed

    Dominik Köppl

    Proc. DCC   133 - 142   2024.3

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    We extend the LZ78 substring compression introduced in \cite{koppl21nonoverlapping} to the LZ78 derivates LZMW and LZ double. As a byproduct, we obtain the first linear-time algorithm for integer alphabets independent on the text compressibility.

    researchmap

  • Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences Reviewed

    Hideo Bannai, Tomohiro I., Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi

    Algorithmica   2024.3( ISSN：1432-0541 )

    　More details

    Authorship：Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

    We improve on \cite{bannai22computing}, we could improve the time and space complexity of our online algorithm, where we shaved off a factor linear in the alphabet size

    DOI： 10.1007/s00453-023-01125-z

    Scopus

    researchmap

  • On the Hardness of Smallest RLSLPs and Collage Systems Reviewed

    Akiyoshi Kawamoto, Tomohiro I, Dominik Köppl, Hideo Bannai

    Proc. DCC   243 - 252   2024.3

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    We show that finding a smallest run-length compressed straight line programs (RLSLPs) is NP-hard for unbounded alphabet size. The same proof can be adapted for finding a smallest collage system. Additionally, we give a MAX-SAT encoding for computing a smallest RLSLP.

    researchmap

  • Extending the Parameterized Burrows–Wheeler Transform Reviewed

    Eric M. Osterkamp, Dominik Köppl

    Proc. DCC   143 - 152   2024.3

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    We propose a generalized pattern matching combining parameterized with circular pattern matching. As an indexing data structure for such a matching, we enhance the parameterized Burrows--Wheeler transform (pBWT) of Kim and Cho with techniques derived from the extended Burrows--Wheeler transform of Mantaci et al., obtaining time and space complexities similar to the pBWT.

    researchmap

  • Answer Set Programming を用いた圧縮指標の計算

    クップル ドミニク, 番原 睦則

    2024.2

    　More details

    Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • Constructing and Indexing the Bijective and Extended Burrows–Wheeler Transform Reviewed

    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski

    Inf. Comput.   ( 105153 )   2024.1

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    Journal version of \cite{bannai19bbwt} and \cite{bannai21constructing} with more examples, higher detail in the explanations and an experimental evaluation of the presented construction algorithm with known algorithms constructing the BBWT.

    DOI： 10.1016/j.ic.2024.105153

    researchmap

  • パラメタ化 Burrows–Wheeler 変換の拡張

    Eric M. Osterkamp, Dominik Köppl

    Local Proceedings of コンピュテーション研究会   123 ( 325 )   20 - 20   2023.12

    　More details

    Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • LZD と LZMW 分解の部分文字列圧縮について

    クップル ドミニク

    Local Proceedings of the 195th アルゴリズム研究会   195 ( 1 )   1 - 3   2023.11

    　More details

    Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • lex-parse の圧縮感度

    中島 祐人, クップル ドミニク, 舩越 満, 稲永 俊介

    Local Proceedings of the 195th アルゴリズム研究会   195 ( 2 )   1 - 3   2023.11

    　More details

    Language：Japanese   Publishing type：(MISC) Institution technical report and pre-print, etc.  

    researchmap

  • Acceleration of FM-Index Queries Through Prefix-Free Parsing Reviewed International coauthorship

    Aaron Hong; Marco Oliva; Dominik Köppl; Hideo Bannai; Christina Boucher; Travis Gagie

    Proc. WABI   273   13:1 - 13:16   2023.9

    　More details

    Language：English   Publishing type：Research paper (international conference proceedings)  

    By storing additionally to the FM-index the index of \cite{deng22fm}, we can make use of both to accelerate counting queries for all pattern lengths and the expense of more space compared to the FM-index.

    DOI： 10.4230/LIPIcs.WABI.2023.13

    researchmap

▼display all

Books and Other Publications

  • Acta Informatica - Topical Collection on Advances in String Processing Algorithms and String Data Structures Reviewed International journal

    Dominik Köppl, Golnaz Badkobeh（ Role： Joint EditorLeading Guest Editors）

    Springer  2024 

    　More details

    Language：English  

    researchmap

Presentations

  • Overcoming boundaries of AI: future prospects

    Dominik Köppl

    EU-Japan AI Bridge – Connecting International Researchers and the Japanese AI Start-up Scene  2024.10 

    　More details

    Language：English   Presentation type：Oral presentation(general)  

    researchmap

  • Enumerating full binary trees in polynomial delay International conference

    Yasuko Matsui; Hirotaka Ono; Dominik Koeppl

    25th International Symposium on Mathematical Programming (ISMP)  2024.7 

    　More details

    Language：English   Presentation type：Oral presentation(general)  

    researchmap

  • ZDDを用いた最小文字列アトラクタの列挙

    藤岡 祐太; 斎藤 寿樹; クップル ドミニク

    日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会  2023.10 

    　More details

    Language：Japanese   Presentation type：Oral presentation(general)  

    researchmap

Teaching Experience (On-campus)

▼display all

Teaching Experience

Professional Memberships

Committee Memberships

  • Symposium on Experimental Algorithms   program committee  

    2025   

    　 More details

    Committee type：Society

    SEA, link: https://regindex.github.io/sea2025.github.io/

    researchmap

  • 27th Prague Stringology Conference   co-chair of the program committee  

    2024   

    　 More details

    Committee type：Society

    PSC, link: http://www.stringology.org/event/2024/

    researchmap

  • 31st International Symposium on String Processing and Information Retrieval   program committee  

    2024   

    　 More details

    Committee type：Society

    SPIRE, link: http://computo.fismat.umich.mx/spire2024/committees.html

    researchmap

  • 35th Annual Symposium on Combinatorial Pattern Matching   program committee  

    2024   

    　 More details

    Committee type：Society

    CPM, link: https://cpm2024.github.io/

    researchmap

  • StringMasters   local organizing committee  

    2024   

    　 More details

    Committee type：Society

    StringMasters, link: https://cpm2024.github.io/stringmasters.html

    researchmap

  • 35th Annual Symposium on Combinatorial Pattern Matching   local organizing committee  

    2024   

    　 More details

    Committee type：Society

    CPM, link: https://cpm2024.github.io/

    researchmap

  • 24th International Workshop on Algorithms in Bioinformatics   program committee  

    2024   

    　 More details

    Committee type：Society

    WABI, link: https://algo-conference.org/2024/wabi/

    researchmap

  • 32nd European Symposium on Algorithms   program committee  

    2024   

    　 More details

    Committee type：Society

    ESA, link: https://algo-conference.org/2024/esa/

    researchmap

  • Workshop on Emerging Results in Data Science and Engineering   program committee  

    2024   

    　 More details

    Committee type：Society

    ERDSE, link: https://erdse2024.github.io/

    researchmap

  • 49th International Conference on Current Trends in Theory and Practice of Computer Science   program committee  

    2024   

    　 More details

    Committee type：Society

    SOFSEM, link: https://www.uni-trier.de/en/universitaet/fachbereiche-faecher/fachbereich-iv/faecher/informatikwissenschaften/professuren/theoretische-informatik/research/conferences-and-workshops/sofsem-2024

    researchmap

  • 30th International Computing and Combinatorics Conference   program committee  

    2024   

    　 More details

    Committee type：Society

    COCOON, link: https://anl.sjtu.edu.cn/cocoon2024/

    researchmap

▼display all

Academic Activities

▼display all