Dominik Köppl

  • 研究
    理論情報学
  • 興味
    • データ構造
    • 文字列算法
    • 組み合わせ理論
  • アドレス
    ed.x@x ただし x = dkppl または koeppl @ 九大.jp
  • 言語
    この言語でメールが書けられる
    • バイエルン語 (bar)
    • 英語 (eng)
    • フランス語 (fra)
    • ドイツ語 (ger)
    • 日本語 (jpn)
  • 役
    令和５年９月〜令和１０年９月
    特任准教授
  • 研究室
    B-2号館327室
  • 住所
    〒400-0016 山梨県甲府市 武田４−３
    山梨大学 大学院　総合研究部　 工学域電気電子情報工学系 コンピュータ理工学コース（電気電子情報工学系）
  • 係属
    コンピュータ理工学
  • グループ
    文字列の組み合わせ論とその処理
  • 職場
    山梨大学
  • 名前
    クップル　ドミニク
photo

Recent Travels

Lesson Plan

timetuethufri
9
オフィスアワー@B2-327
900-1030
10
11
12
13
ucs207
1310-1440
14
stradsゼミ
1450-1620
cowasp ゼミ@A3-221A
1450-1620
stradsゼミ
1450-1620
15
timemontuethufri
9
オフィスアワー@B2-327
900-1030
10
ucs352@B2-21
1040-1210
11
12
13
ucs354@A3-K342
1310-1620
14
cki009+a@Ｙ－３２
1450-1620
gtk613@Ａ２－１１
1450-1620
15
16
ptw713@A3-221A
1630-1800
cowasp ゼミ@A3-221A
1630-1800
17
time

Former Positions

  1. 2026
  2.  [j37] 
    Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    Grammar index by induced suffix sorting.  Theoretical Computer Science 1082 (116080), pages 1–17. (2026)
    Journal version of [c26] with full proofs and extended examples.  doi  code  manuscript 
  3.  [i40] 
    パウリ ロマン, クップル ドミニク:
    円形デカルト木照合のためのコンパクト複数テキスト索引.  Local Proceedings of コンピュテーション研究会, 信学技報 126 (168), pages 1–3. (2026)
      Implementation of [j34].  link  manuscript  slide 
  4.  [i39] 
    Dominik Köppl, Gregory Kucherov:
    Near-real-time Solutions for Online String Problems.  Local Proceedings of WAAC. (2026)
      Workshop presentation of [c59].  mirror  slide  video  youtube 
  5.  [c64] 
    Dominik Köppl, Gregory Kucherov:
    Smallest Suffixient Set Maintenance in Near-Real-Time.  Proc. MFCS (Rank A), LIPIcs 386, pages 86:1–86:18. (2026)
    We maintain the smallest suffixient set based on the ending positions of the rightmost occurrences of the super-rightmaximal extensions of an text online. We give online algorithms in both streaming directions with time bounds based on the near-real-time bounds for suffix tree updates in Weiner's suffix tree construction manner.   doi  arxiv  mirror  slide  video  youtube 
  6.  [c63] 
    Hiroki Shibata, Takuya Mieno, Dominik Köppl, Shunsuke Inenaga:
    Relaxation of Square-Freeness.  Proc. PSC (Rank national), pages . (2026)
      We extend the analysis of nonrepetitive sequences to relaxations of equality testing under nonstandard equivalence relations, in particular parameterized equivalence and order-preserving equivalence. For this setting, we focus on squares whose total length is above a certain threshold. We obtain an infinite ternary or binary word that is free of such squares in the parameterized or order-preserving setting, respectively, with threshold 3.   link  arxiv 
  7.  [c62] 
    Mutsunori Banbara, Hideo Bannai, Takashi Horiyama, Dominik Köppl, Takuya Mieno, Hidetomo Nabeshima:
    Optimal Dictionary-Based Compression with Answer Set Programming: Encodings and Empirical Analysis.  Proc. KR, pages 700–710. (2026)
    We port the MAX-SAT encodings for the smallest bidirectional macro scheme and the smallest SLP from [j30] to the answer set program language, leveraging acyclicity checks to make the generation of the encoding more lightweight.   doi  manuscript  mirror 
  8.  [j36] 
    Golnaz Badkobeh, Hideo Bannai, Tomohiro I, Dominik Köppl:
    Bijective BWT Based Compression Schemes.  Theory of Computing Systems 70 (42), pages 1–16. (2026)
    Journal version of [c48], where we additionally give an algorithm determining the optimal rotation with a time complexity that depends on the input string length and the height of the left and right Lyndon trees of its rotations.   doi  manuscript  mirror 
  9.  [i38] 
    Dominik Köppl, Gregory Kucherov:
    最小 suffixient 集合の準実時間構築.  Local Proceedings of the LA Symposium Summer 2026. (2026)
      Workshop presentation of [c64]  mirror  slide 
  10.  [c61] 
    Seungbum Jo, Dominik Köppl:
    Indexing Range Maximum-Sum Segment Queries with Offsets.  Proc. SWAT, LIPIcs 370, pages 23:1–23:16. (2026)
    We combine the maximal segment sum problem extensions with a query and with a query offset to a query that supports both parameters.   Proof of Lemma 13 has a flaw: Using the OMSS data structure on X' may give wrong results. The correct way is to modify the OMSS setting to allow a weight per run. This is a straight-forward change but the logic in the OMSS algorithm has to be rewritten from scratch. Doing so correctly does not change the claimed time/space complexities.  doi  arxiv  mirror 
  11.  [c60] 
    Dominik Köppl, Jannik Olbrich:
    Hardness Results on Characteristics for Elastic-Degenerated Strings.  Proc. CPM (Rank B), LIPIcs 369, pages 14:1–14:25. (2026)
    We give NP-hardness results for the following problems extended to elastic-degenerate strings: finding a unique substring or an absent word of a certain length, finding a k-anti-power computing the longest previous factor length, and covering the string with Lempel-Ziv factors.  arxiv  code  mirror 
  12.  [c59] 
    Dominik Köppl, Gregory Kucherov:
    Near-real-time Solutions for Online String Problems.  Proc. CPM (Rank B), LIPIcs 369, pages 2:1–2:17. (2026)
    Based on near-real-time suffix tree updates in the line of research of Weiner's suffix tree construction algorithm, we show how to compute the longest repeating suffix array, the (reversed) Lempel–Ziv 77 factorization, and how to maintain minimal unique substrings, all in an online manner with a time bound matching based on the near-real-time suffix tree update.   doi  arxiv  mirror 
  13.  [c58] 
    Mutsunori Banbara, Hideo Bannai, Peaker Guo, Dominik Köppl, Takuya Mieno, Yoshio Okamoto:
    The Smallest String Attractors of Fibonacci and Period-Doubling Words.  Proc. CPM (Rank B), LIPIcs 369, pages 33:1–33:21. (2026)
    We characterize all smallest string attractors of the Fibonacci and period-doubling words, complementing already-known machine-proven characterizations with a human-verifiable proof framework.   doi  arxiv  mirror 
  14.  [c57] 
    Simone Faro, Dominik Köppl, Thierry Lecroq, Francesco Pio Marino:
    A Bitwise Approach to SCER Matching in Indeterminate Strings.  Proc. CPM (Rank B), LIPIcs 369, pages 21:1–21:17. (2026)
    We study the problem of matching a determinate pattern against an indeterminate text of the same length under the order-preserving and parameterized matching setting supporting mismatches. We use bit-parallel matching and bipartite graph matching as tools.   doi  code  mirror 
  15.  [c56] 
    Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon, Dominik Köppl:
    Efficient Index for Square Pattern Matching.  Proc. CPM (Rank B), LIPIcs 369, pages 35:1–35:12. (2026)
    We present a new extended matching substring equivalence relation (SCER) matching that matches two strings if the set of their squares coincides with respect to starting positions and lengths. We give an algorithm for square pattern matching using quadratic space and time.   doi  mirror 
  16.  [j35] 
    Hideo Bannai, Keisuke Goto, Shunsuke Kanda, Dominik Köppl:
    NP-Completeness on the Length of Double-Arrays and the Sparse Matrix Problem with at Least Logarithmic Alphabets/Widths.  Theory of Computing Systems 70 (23), pages 1–35. (2026)
    We show that the computation of the optimal layout of the double array is NP-hard even if the input alphabet size is at least logarithmic. For that, we follow a reduction from Hamiltonian path to shortest super string, and add some changes to obtain a string that is output-equivalent to the matrix compression problem, for which we show equivalence with the optimal layout of the double array.  doi  arxiv  code 
  17.  [j34] 
    Eric M. Osterkamp, Dominik Köppl:
    The ceBWT Index: An Index for Circular Cartesian Tree Matching on Multiple Texts.  Theory of Computing Systems 70 (27), pages 1–27. (2026)
    Journal version of [c50], where we additionally devise a static index with compact space bounds, and an algorithm for computing matching statistics in the circular Cartesian tree matching setting.  doi  link  manuscript 
  18.  [c55] 
    Che-Wei Tsao, Yi-Hua Lin, Wing-Kai Hon, Dominik Köppl:
    Enumeration of Unbordered Words in Compressed Representation.  Proc. DCC (Rank B), pages 103–112. (2026)
    We devise an enumeration algorithm of unbordered words. By storing the shift of an unbordered conjugates of an enumerated Lyndon word, we obtain amortized constant delay time. The basic idea is to apply Duval's algorithm to enumerate Lyndon words, and compute the border table of all cyclic shifts of each Lyndon word in linear time to the length of this Lyndon word.   doi  code  manuscript 
  19.  [c54] 
    Simone Faro, Dominik Köppl, Francesco Pio Marino:
    Attractor Matching: A New Paradigm for Structural String Comparison.  Proc. DCC (Rank B), pages 391–400. (2026)
    We introduce a new type of structural pattern matching based on string attractors. Given a set of positions, a length, and a text, our task is to compute all substrings of the text with the specified length that have the given set of positions as a string attractor. Our algorithm uses a sliding-window approach for indexing the specific substring in question to quickly check whether the given set of positions is a string attractor of the substring in the sliding window.  doi  manuscript 
  20.  [c53] 
    Simone Faro, Dominik Köppl, Francesco Pio Marino:
    Enabling FM-Index for Elastic-Degenerate Strings via a new Min/Max Wavelet Tree (Poster).  Proc. DCC (Rank B), pages 435. (2026)
    We propose a generalization of wavelet trees to index elastic-degenerate strings. This enables us to devise an FM-index based on elastic-degenerate strings that supports backward search for counting and locating patterns.  doi  manuscript 
  21.  [j33] 
    Eric M. Osterkamp, Dominik Köppl:
    Extended parameterized Burrows–Wheeler transform.  Information Systems 136 (102611), pages 1–19. (2026)
    Journal version of [i22]. We added more details on the construction and give matching statistics as an application. We simplified the encoding of the BWT by introducing a new encoding for cyclic matching.  doi  manuscript 
  22.  [c52] 
    Souta Kobayashi, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara:
    Efficient Solutions to Variants of Inversion Problems of Range Minimum Queries.  Proc. SOFSEM (Rank B), LNCS 16448, pages 16–30. (2026)
    We study the reverse problem of range minimum query computation. Given a set of answer-question pairs to range minimum queries, where the answer are either indices or values, we construct an integer array consistent with the results of the queries, or report inconsistency. While the value-based version has been studied in terms of competitive programming, we here give a computation linear in the length of the returned integer array.   doi  manuscript 
  23.  [t26] 
    Dominik Köppl:
    On Solving the Sparse Matrix Compression Problem.  Shonan Meeting No.240, New Era of Data Structures: From Strings to Graphs, and more. (2026)
    Presentation of ideas and open problems published in [i36], [t22], and [i26].  slide 
  24.  [j32] 
    Che-Wei Tsao, Jin-Jie Deng, Long-Qi Chen, Wing-Kai Hon, Dominik Köppl, Kunihiko Sadakane:
    τλ-Index: A framework for locating rare patterns in repetitive corpora.  Information Systems 139 (102702), pages 1–17. (2026)
    Given a substring P in a text T is called rare if it occurs at most τ times, we present a near-linear time method to identify the parts in T necessary for rare pattern search. This helps us to kernelize the problem for locate queries with an arbitrary index built on the remaining parts of the text.  doi  link  code  manuscript 
  25.  [i37] 
    Dominik Köppl, Gregory Kucherov:
    準リアルタイム接尾辞木構築に関する応用について.  Local Proceedings of the 206th アルゴリズム研究会, 研究報告アルゴリズム 206, pages 1–4. (2026)
      We apply Breslauer-Italiano's near-real-time suffix tree construction to solve various string problems such as the LZ77 factorization and the computation of all minimal unique substrings in near real-time.  manuscript  slide 
  26.  [i36] 
    Dominik Köppl, Vincent Limouzy, Andrea Marino, Jannik Olbrich, Giulia Punzi, Takeaki Uno:
    疎行列圧縮による二重対数行列幅の実現.  Local Proceedings of the LA Symposium Winter 2025. (2026)
      We devise a dynamic programming approach that solves the matrix compression problem. Given the rows of the matrix is our input size parameter, it works in polynomial time for logarithmic matrix widths if there are at most logarithmically many different rows, or otherwise for double-logarithmic matrix widths.  code  mirror  slide 
  27.  [i35] 
    三神 摩周, クップル ドミニク:
    LZW の圧縮感度.  Local Proceedings of the LA Symposium Winter 2025. (2026)
      We translate the proofs of Akagi et al. of the compression sensitivity for LZ78 to LZW, obtaining the same stated complexities for the additive and multiplicative sensitivity by slightly changing the used lower bound string families.   mirror  slide 
  28. 2025
  29.  [j31] 
    Hiroki Shibata, Dominik Köppl:
    LZ78 Substring Compression in Compressed Space.  Theory of Computing Systems 70 (1), pages 1–22. (2025)
    Journal version of [c49]. We abstracted the presented algorithm to work with any compressed self-index that implements access to the text, the inverted suffix array, and the suffix range for computed factors.  doi  arxiv  code  Nature SharedIt  manuscript 
  30.  [t25] 
    Dominik Köppl:
    一次元データの効率的な処理手法の開発.  山梨県大村智人材育成基金 若手研究者奨励事業 第７回研究成果報告会. (2025)
      Presentation of the result of [i28].  link  mirror  slide 
  31.  [j30] 
    Hideo Bannai, Keisuke Goto, Masakazu Ishihata, Shunsuke Kanda, Dominik Köppl, Takaaki Nishimoto, Bernardo Subercaseaux:
    Computing NP-hard Repetitiveness Measures via MAX-SAT.  ACM Trans. Algorithms 22 (2), pages 15:1–15:25. (2025)
    Journal version of [c33]. We could improve the CNF sizes for the smallest bidirectional macro scheme in two steps. The first step removes the necessity to encode the reference depth, which was used as one of the three dimensions in the reference variable. The second step is to apply leaf-elimination encoding. For the smallest straight-line program, we could improve the CNF size by partitioning the containment constraint.   doi  link   7 citations
  32.  [j29] 
    Tomohiro I, Dominik Köppl, Hiroshi Sakamoto, Sohei Yamaguchi:
    Space-Efficient B Trees via Load-Balancing.  Theory of Computing Systems 69 (32), pages 1–26. (2025)
    Journal version of [c31]. We here included an experimental analysis, and variants using word packing and external memory.  doi  code  Nature SharedIt  manuscript  mirror 
  33.  [c51] 
    Haruki Umezaki, Hiroki Shibata, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai:
    Counting Distinct (Non-)crossing Substrings.  Proc. SPIRE (Rank C), LNCS 16073, pages 281–290. (2025)
    We extend Problem 64 from the textbook 125 Problems in Text Algorithms counting all substrings crossing or not crossing a position. The extension asks for counting these substrings for all positions. While a naive extension just runs the textbook algorithm for each position individually taking quadratic time, we can get the answers in linear time in the text length. We can count these crossing factors in this time complexity for general alphabets, but need integer alphabets for non-crossing alphabets due to the use of data structures such as the LPF array.  doi  arxiv  manuscript 
  34.  [t24] 
    Dominik Köppl:
    Substring Compression Variants.  Invited talk at University of Ulm and the Bézout Labex colloquium. (2025)
    The talk combines the results of the journal papers [j9], [j27], and [i25] for the substring compression problem of LZ78 and some of its derivates.  slide 
  35.  [i34] 
    Eric Osterkamp, Dominik Köppl:
    複数文学列に対するデカルト木円形パターン照合の索引.  Local Proceedings of the LA Symposium Summer 2025. (2025)
      Presentation of the paper [c50] in Japanese.  mirror  slide 
  36.  [c50] 
    Eric M. Osterkamp, Dominik Köppl:
    Extending the Burrows–Wheeler Transform for Cartesian Tree Matching and Constructing It.  Proc. CPM (Rank B), LIPIcs 331, pages 26:1–26:17. (2025)
    We extend the BWT variant for Cartesian tree matching to index multiple strings for circular pattern matching in the spirit of the extended BWT. We analyze pattern matching with this BWT variant and the construction of it.  doi  arxiv  mirror  slide 
  37.  [i33] 
    Hideo Bannai, Dominik Köppl, Zsuzsanna Lipták:
    A Survey of the Bijective Burrows-Wheeler Transform.  , OASIcs 131, pages 2:1–2:26. (2025)
    We try to give a comprehensive survey from the starting point of the BBWT up to the current state of the art. We cover the construction, indexing, and relation to other compression schemes.  doi  mirror 
  38.  [i32] 
    Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono, Toshiki Saitoh, Yushi Uno:
    Enumeration of Ordered Trees with Leaf Restrictions.  , OASIcs 132, pages 8:1–8:19. (2025)
    Given the number of leaves on each level, we enumerate all trees with a fixed specified arity having such a leaf distribution. While finding the first such tree takes linear time in the input, we can report a subsequent tree as a difference to the former one in constant time.  doi  link  mirror 
  39.  [t23] 
    Hyodam Jeon, Dominik Köppl:
    Compression Sensitivity of the Bijective Burrows–Wheeler transform.  International Workshop on Discrete Mathematics and Algorithms. (2025)
    Presentation of [j28].  slide 
  40.  [i31] 
    Hyodam Jeon, Dominik Köppl:
    全単射 Burrows–Wheeler 変換の圧縮感度について.  Local Proceedings of the 202th アルゴリズム研究会, 研究報告アルゴリズム 202 (5), pages 1–3. (2025)
      Presentation of [j28] in Japanese.  link  manuscript  slide 
  41.  [j28] 
    Hyodam Jeon, Dominik Köppl:
    Compression Sensitivity of the Burrows–Wheeler transform and its Bijective Variant.  Mathematics 13(7) (1070), pages 1–46. (2025)
    We study the compression sensitivity of the bijective BWT (BBWT) when editing a single character of the input. Like previous work based on the BWT, we obtain a logarithmic multiplicative or a square-root additive change for specific cases.  doi  mirror 
  42.  [j27] 
    Dominik Köppl:
    Substring Compression Variations and LZ78-Derivates.  Information Systems 133 (102553), pages 1–16. (2025)
    Journal version of [c43]. We additionally devise an algorithm computing the standard flexible parsing with an AC automaton. We also analyze the longest and shortest closed factorization under the substring compression setting.  doi  manuscript 
  43.  [t22] 
    Dominik Köppl, Vincent Limouzy, Andrea Marino, Giulia Punzi, Takeaki Uno:
    On Solving the Sparse Matrix Compression Problem Greedily.  The 29th London Stringology Days and London Algorithmic Workshop. (2025)
    Workshop-Presentation of [i29].  slide 
  44.  [i30] 
    Dominik Köppl, Jannik Olbrich:
    未決定文字列における一意単語の検索の困難さ.  Local Proceedings of the 201th アルゴリズム研究会, 研究報告アルゴリズム 201 (4), pages 1–5. (2025)
      We prove that computing a minimal unique substring in indeterminate strings is NP-complete.  link  manuscript  slide 
  45.  [i29] 
    Dominik Köppl, Vincent Limouzy, Andrea Marino, Giulia Punzi, Takeaki Uno:
    On Solving the Sparse Matrix Compression Problem Greedily.  Local Proceedings of the LA Symposium Winter 2024. (2025)
      We show that the computed solution of Ziegler's method for computing a sparse matirx compression can be longer than the optimal solution by a square-root factor.  mirror  slide 
  46. 2024
  47.  [i28] 
    Dominik Köppl, Jannik Olbrich:
    未決定文字列における欠如単語の検索の困難さ.  Local Proceedings of the 200th アルゴリズム研究会, 研究報告アルゴリズム 200 (15), pages 1–5. (2024)
      We prove that computing absent words in indeterminate strings is NP-complete.  link  manuscript  slide 
  48.  [t21] 
    Dominik Köppl:
    Overcoming boundaries of AI: future prospects.  EU-Japan AI Bridge – Connecting International Researchers and the Japanese AI Start-up Scene. (2024)
      A talk about the limitations of machine learning with future prospects in combining techniques of different subjects to improve accuracy. 
  49.  [c49] 
    Hiroki Shibata, Dominik Köppl:
    LZ78 Substring Compression with CDAWGs.  Proc. SPIRE (Rank C), LNCS 14899, pages 289–305. (2024)
      We study the substring compression in the LZ78 scheme introduced in [j9] 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  dblp  code  manuscript   2 citations
  50.  [c48] 
    Golnaz Badkobeh, Hideo Bannai, Dominik Köppl:
    Bijective BWT based Compression Schemes.  Proc. SPIRE (Rank C), LNCS 14899, pages 16–25. (2024)
    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  dblp  arxiv  code  manuscript 
  51.  [i27] 
    Hiroki Shibata, Dominik Köppl:
    LZ78 Substring Compression in CDAWG-compressed Space.  Local Proceedings of WAAC. (2024)
      Presentation of [c49].  mirror   1 citation
  52.  [c47] 
    Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, Hideo Bannai:
    Edit and Alphabet-Ordering Sensitivity of Lex-Parse.  Proc. MFCS (Rank A), LIPIcs 306, pages 75:1–75:15. (2024)
    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  dblp  arxiv  manuscript  mirror  slide   1 citation
  53.  [c46] 
    Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara:
    Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching.  Proc. ICALP (Rank A), LIPIcs 297, pages 89:1–89:19. (2024)
    We adapt the online Burrows-Wheeler transform construction on the reversed text for constructing the parameterized Burrows-Wheeler transform like in [c35]. By binary searching the interval for the insertion position, we obtain the first construction algorithm of parameterized indexes whose time only logarithmically depend on the parameterized alphabet size. Up to that point, only linear-dependence has been known.  doi  dblp  arxiv  mirror   3 citations
  54.  [i26] 
    坂内 英夫, 後藤 啓介, 田 峻介, クップル ドミニク:
    対数的な幅を持つ疎行列圧縮のNP完全性.  Local Proceedings of the LA Symposium Summer 2024. (2024)
      We show that the sparse matrix compression problem is NP-hard even if the matrix rows have logarithmic width in relation to the number of rows. Presentation of [j35].  mirror  slide 
  55.  [i25] 
    柴田 紘希, クップル ドミニク:
    CDAWG による LZ78 部分文字列圧縮.  Local Proceedings of the LA Symposium Summer 2024. (2024)
      Presentation of [c49] in Japanese.  mirror  slide 
  56.  [t20] 
    Yasuko Matsui, Hirotaka Ono, Dominik Koeppl:
    Enumerating full binary trees in polynomial delay.  25th International Symposium on Mathematical Programming (ISMP). (2024)
    Given the number of leaves on each depth as a query, we enumerate all full binary trees that meet this query. We can output the first tree in time linear in its size, and subsequent trees in constant time by a differential representation. 
  57.  [c45] 
    Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara:
    Algorithms for Galois Words: Detection, Factorization, and Rotation.  Proc. CPM (Rank B), LIPIcs 296, pages 18:1–18:16. (2024)
    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-Galois 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  dblp  arxiv  code  mirror  slide   1 citation
  58.  [i24] 
    クップル ドミニク:
    山梨での研究活動.  LAシンポジウム会誌83号. (2024)
      We survey approaches for computing or enumerating the smallest string attractor based on MAX-SAT, ASP, and ZDD.  mirror 
  59.  [j26] 
    Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, Travis Gagie:
    Pfp-fm: an accelerated FM-index.  Algorithms for Molecular Biology 19 (15), pages 1–14. (2024)
      Journal version of [c41]. 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  dblp  code  mirror   6 citations
  60.  [j25] 
    Jacqueline W. Daykin, Dominik Köppl, David Kübel, Florian Stober:
    On arithmetically progressed suffix arrays and related Burrows–Wheeler transforms.  Discrete Applied Mathematics Volume 355, pages 180-199. (2024)
    Compared to the conference version [c21], 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  dblp  mirror   1 citation
  61.  [j24] 
    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi:
    Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences.  Algorithmica 86 (3), pages 735–756. (2024)
    We improve on [c32], we could improve the time and space complexity of our online algorithm, where we shaved off a factor linear in the alphabet size  doi  code  mirror   2 citations
  62.  [c44] 
    Eric M. Osterkamp, Dominik Köppl:
    Extending the Parameterized Burrows–Wheeler Transform.  Proc. DCC (Rank B), pages 143–152. (2024)
    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.  doi  dblp  manuscript  photo  slide  video  youtube   4 citations
  63.  [c43] 
    Dominik Köppl:
    Computing LZ78-Derivates with Suffix Trees.  Proc. DCC (Rank B), pages 133–142. (2024)
    We extend the LZ78 substring compression introduced in [j9] 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. We also introduce flexible parsing to LZ78 and give linear-time algorithms for computing these parsings.  doi  dblp  arxiv  manuscript  slide  video  youtube 
  64.  [c42] 
    Akiyoshi Kawamoto, Tomohiro I, Dominik Köppl, Hideo Bannai:
    On the Hardness of Smallest RLSLPs and Collage Systems.  Proc. DCC (Rank B), pages 243–252. (2024)
    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.  doi  dblp  code  manuscript   2 citations
  65.  [t19] 
    Dominik Köppl:
    Computing LZ78-Derivates with Suffix Trees.  International Workshop on Discrete Mathematics and Algorithms. (2024)
    Workshop-Presentation of [c43].   7 citations
  66.  [i23] 
    クップル ドミニク, 番原 睦則:
    Answer Set Programming を用いた圧縮指標の計算.  Local Proceedings of the LA Symposium Winter 2023. (2024)
      A translation of the MAX-SAT encodings presented in [c33] to the ASP language, in Japanese.  code  mirror  photo  slide 
  67.  [j23] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Constructing and Indexing the Bijective and Extended Burrows–Wheeler Transform.  Inf. Comput. 297 (105153), pages 1–30. (2024)
    Journal version of [c14] and [c24] with more examples, higher detail in the explanations and an experimental evaluation of the presented construction algorithm with known algorithms constructing the BBWT.  The Lyndon factorization (omitting duplicate Lyndon factors) in Algorithm 2 is described as a lexicographically ascending sequence, but is actually descending (as usual).  doi  dblp  code  manuscript   5 citations
  68. 2023
  69.  [i22] 
    Eric M. Osterkamp, Dominik Köppl:
    パラメタ化 Burrows–Wheeler 変換の拡張.  Local Proceedings of コンピュテーション研究会, 信学技報 123 (325), pages 53–55. (2023)
      Presentation of the results of the Bachelor thesis of Eric M. Osterkamp  link  manuscript  photo  slide 
  70.  [i21] 
    中島 祐人, クップル ドミニク, 舩越 満, 稲永 俊介:
    lex-parse の圧縮感度.  Local Proceedings of the 195th アルゴリズム研究会, 研究報告アルゴリズム 195 (2), pages 1–3. (2023)
      We study the chance of the number of factors of lex-parse when changing a character in the input.  link  manuscript 
  71.  [i20] 
    クップル ドミニク:
    LZD と LZMW 分解の部分文字列圧縮について.  Local Proceedings of the 195th アルゴリズム研究会, 研究報告アルゴリズム 195 (1), pages 1–3. (2023)
      We present a deterministic linear-time algorithm for computing LZD and LZMW, where linear either means linear in the input size, or in the model of substring compression linear in the number of factors of the output if we allow linear-time precomputation on the input text.  link  manuscript  photo  slide 
  72.  [t18] 
    藤岡 祐太, 斎藤 寿樹, クップル ドミニク:
    ZDD を用いた最小文字列アトラクタの列挙.  日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会. (2023)
      Enumeration of string attractors with ZDD.  link 
  73.  [c41] 
    Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, Travis Gagie:
    Acceleration of FM-Index Queries Through Prefix-Free Parsing.  Proc. WABI (Rank C), LIPIcs 273, pages 13:1–13:16. (2023)
      By storing additionally to the FM-index the index of [c30], 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  link  dblp  arxiv  code  mirror   2 citations
  74.  [c40] 
    Nicola Cotumaccio, Travis Gagie, Dominik Köppl, Nicola Prezza:
    Space-time Trade-offs for the LCP Array of Wheeler DFAs.  Proc. SPIRE (Rank C), LNCS 14240, pages 143–156. (2023)
      We sample the longest-common prefix array generalized from strings to Wheeler DFAs, which takes space of words linear to the number of states, for a representation that requires linear number in bits with a logarithmic access time. Like our precursor, we give matching statistics computation as an application, which we now can do with a time-space trade-off.  doi  dblp  arxiv  manuscript   7 citations
  75.  [c39] 
    Paola Bonizzoni, Christina Boucher, Davide Cozzi, Travis Gagie, Dominik Köppl, Massimiliano Rossi:
    Data Structures for SMEM-Finding in the PBWT.  Proc. SPIRE (Rank C), LNCS 14240, pages 89–101. (2023)
      We propose space-efficient data structures that augment the positional Burrows–Wheeler Transform for efficiently finding set-maximal exact matches, and compare these with the baseline approach, which uses the plain divergence array.  doi  dblp  arxiv  code  manuscript   3 citations
  76.  [c38] 
    Dominik Köppl, Florian Kurpicz, Daniel Meyer:
    Faster Block Tree Construction.  Proc. ESA (Rank A), LIPIcs 274, pages 74:1–74:20. (2023)
      We leverage the LPF array to judge whether a block in the block tree has already a previous occurrence. By building the block tree levelwise and using information about the previous level, we can obtain the same time complexity as previous approaches while gaining practical performance, primarily because more sophisticated techniques are no longer needed.  doi  link  dblp  code  mirror   2 citations
  77.  [j22] 
    Davide Cozzi, Massimiliano Rossi, Simone Rubinacci, Travis Gagie, Dominik Köppl, Christina Boucher, Paola Bonizzoni:
    μ-PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data.  Bioinformatics 39 (9). (2023)
      We augment the positional Burrows–Wheeler Transform (PBWT) with indexing data structures akin to the r-index to devise an indexing data structure for matching stastistics while keeping the working space bounded in the number of runs in the PBWT when read column-wise.  doi  dblp  code  mirror 
  78.  [j21] 
    Hideo Bannai, Tomohiro I, Dominik Köppl:
    Longest bordered and periodic subsequences.  Inf. Process. Lett. 182 (106398), pages 1–6. (2023)
    We use state-of-the-art tools for computing the longest common subsequences between all prefixes and all suffixes of a text to compute longest bordered subsequences or longest periodic subsequences. For the longest bordered subsequences, we give a conditional lower bound that matches our quadratic running time.  doi  dblp  arxiv  mirror   1 citation
  79.  [t17] 
    Davide Cozzi, Massimiliano Rossi, Simone Rubinacci, Travis Gagie, Dominik Köppl, Christina Boucher, Paola Bonizzoni:
    μ-PBWT: a lightweight r-indexing of the PBWT for storing and querying UK Biobank data.  Poster at ISMB/ECCB. (2023)
      poster   5 citations
  80.  [c37] 
    Dominik Köppl:
    Encoding Hard String Problems with Answer Set Programming.  Proc. CPM (Rank B), LIPIcs 259, pages 17:1–17:21. (2023)
    We study common NP-hard problems that have strings as inputs under the light of solvers that work with problem encodings written in answer set programming (ASP). Our evaluation reveals that naive implementations are usually outpaced by ASP encodings if the solver manages to considerably reduce the number of choices to take. While we empirically experienced this situation for most of the presented problems, solving the traveling salesman problem was more challenging with ASP than with a solution working with dynamic programming.  doi  link  dblp  code  mirror  photo  slide  video  youtube 
  81.  [t16] 
    Dominik Köppl:
    Encoding Hard String Problems with Answer Set Programming.  Sequences in London. (2023)
    Presentation of the result of [c37].  photo  slide 
  82.  [c36] 
    César Martínez-Guardiola, Nathaniel K. Brown, Fernando Silva-Coira, Dominik Köppl, Travis Gagie, Susana Ladra:
    Augmented Thresholds for MONI.  Proc. DCC (Rank B), pages 268–277. (2023)
      We practically accelerate matching statistics computation of PHONI (the r-index with a grammar supporting LCE queries) by augmenting thresholds introduced in MONI with LCE information between the thresholds and the neighboring run endings. This allows us to skip some LCE queries for the grammar, which was the computational bottleneck of PHONI.   doi  dblp  arxiv  code  manuscript   6 citations
  83.  [j20] 
    Dominik Köppl:
    Dynamic Skyline Computation with LSD Trees.  Analytics 2 (1), pages 146–162. (2023)
    We enhance the algorithm of [c3] for dynamic skyline computation that exhibits practically good performance for small dimensions. The dynamic skyline problem is to support successive queries, where the query parameters can slightly be changed. Our idea is to cache the query results and quickly decide on a new query which cached results can be reused. For this task, a geometric data structure like the LSD tree used in the original paper is useful.   doi  link  code  mirror   1 citation
  84.  [i19] 
    Christina Boucher, Dominik Köppl, Herman Perera, Massimiliano Rossi:
    r インデックスにおける接尾辞配列を模倣するデータ構造.  Local Proceedings of the LA Symposium Winter 2022. (2023)
      Presentation of [c34] in Japanese.  manuscript  slide 
  85.  [j19] 
    Szymon Grabowski, Dominik Köppl:
    Space-efficient Huffman codes revisited.  Information Processing Letters 179 (106274), pages 1–8. (2023)
    We lower the space requirements of a Huffman tree representation with constant time for a single encoding and decoding operation by a partitioning of the codewords and indexing each part by a dedicated fusion tree to improve the space bounds.   doi  link  dblp  arxiv  mirror   3 citations
  86.  [i18] 
    中島 祐人, クップル ドミニク, 舩越 満, 稲永 俊介:
    アルファベット順による lex-parse サイズ比.  Local Proceedings of the 191th アルゴリズム研究会, 研究報告アルゴリズム 191 (4), pages 1–4. (2023)
      We show that changing the alphabet order can lead to an logarithmic-multiplicative increase of the number of factors of lexicographic parsings.  link  manuscript 
  87. 2022
  88.  [i17] 
    クップル ドミニク:
    接尾辞木に基づくLZ77とLPF配列の変種の計算.  Local Proceedings of コンピュテーション研究会, 信学技報 122 (294), pages 29–30. (2022)
      Presentation of [j11] and [j9] in Japanese.  link  manuscript  slide 
  89.  [i16] 
    Dominik Köppl, Gonzalo Navarro, Nicola Prezza:
    Lempel–Ziv 項の距離を高次情報量で表現する符号.  Local Proceedings of the 190th アルゴリズム研究会, 研究報告アルゴリズム 190 (1), pages 1–3. (2022)
      Presentation of [c29] in Japanese.  link  manuscript  slide 
  90.  [c35] 
    Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara:
    Computing the Parameterized Burrows–Wheeler Transform Online.  Proc. SPIRE (Rank B), LNCS 13617, pages 70–85. (2022)
    We propose an algorithm for the construction of the parameterized Burrows-Wheeler transform whose time complexity linearly depends on the number of parameterized characters and logarithmically on the text length. The latter is due to dynamic wavelet trees necessary for building the Burrows-Wheeler transform from right to left.  doi  dblp  arxiv  manuscript   3 citations
  91.  [c34] 
    Christina Boucher, Dominik Köppl, Herman Perera, Massimiliano Rossi:
    Accessing the Suffix Array via ϕ^-1-Forest.  Proc. SPIRE (Rank B), LNCS 13617, pages 86–98. (2022)
    We augment the r-index with a graph of sparse ϕ-array values for improving random access to the suffix array. The r-index uses a predecessor data structure on these sparse ϕ-array values, and computes suffix array values sequentially starting from a run boundary by issuing a predecessor query per entry. We here propose a graph whose traversal simulates such a sequential computation of suffix array entries by avoiding predecessor queries if possible. This graph can speed up random access to the suffix array when long traversals on it are possible.   doi  dblp  code  manuscript  slide  video  youtube 
  92.  [c33] 
    Hideo Bannai, Keisuke Goto, Masakazu Ishihata, Shunsuke Kanda, Dominik Köppl, Takaaki Nishimoto:
    Computing NP-hard Repetitiveness Measures via MAX-SAT.  Proc. ESA (Rank A), LIPIcs 244, pages 12:1–12:16. (2022)
      We provide MAX-SAT formulations for the smallest string attractor, the smallest straight-line program, and the smallest bidirectional scheme, and give implementations in pysat. This is the first study that tackles these NP-hard problems practically and on real data.  doi  dblp  arxiv  code  mirror 
  93.  [j18] 
    Paolo Ferragina, Giovanni Manzini, Travis Gagie, Dominik Köppl, Gonzalo Navarro, Manuel Striani, Francesco Tosoni:
    Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices.  Proc. VLDB 15 (10), pages 2175–2187. (2022)
      We apply the grammar compressor Re-Pair on matrices by linearizing a matrix row-wise and joining the rows by special delimiters. The resulting grammar is used to build an arithmetic circuit for performing matrix-vector multiplications in compressed space related to the number of rules produced by the grammar. The reordering of the columns improves the compression performance by bringing columns with related content together.   doi  link  dblp  arxiv  code  mirror   15 citations
  94.  [c32] 
    Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi:
    Computing Longest (Common) Lyndon Subsequences.  Proc. IWOCA, LNCS 13270, pages 128–142. (2022)
    We give algorithms computing the smallest lexicographic sequence for each possible length, the longest Lyndon subsequence, and the longest common Lyndon subsequence. For the longest Lyndon subsequence, we additionally present an online algorithm.  doi  dblp  arxiv  manuscript  photo  slide  video  youtube   4 citations
  95.  [c31] 
    Tomohiro I, Dominik Köppl:
    Space-Efficient B Trees via Load-Balancing.  Proc. IWOCA, LNCS 13270, pages 327–340. (2022)
    We could improve the space bounds for B trees by a combination of two B tree variants, the B+ tree and B* tree. We extend the B* tree technique to share keys among a non-constant number of sibling nodes. Like the B+ tree, we store the actual data in the leaves, whose capacity we enlarging to reduce the number of internal nodes. We further augment our B tree with aggregate values such as storing the minimum in stored in the descendant leaves of a node, and show that our complexity bounds also hold for certain types of aggregate functions.   doi  dblp  arxiv  manuscript  slide  video  youtube 
  96.  [j17] 
    Dominik Köppl, Simon J. Puglisi, Rajeev Raman:
    Fast and Simple Compact Hashing via Bucketing.  Algorithmica 84 (9), pages 2735–2766. (2022)
    We extend [c20] with SIMD instruction support for accelerating the sequential scan in the buckets. We theoretically support our devised data structure with probabilistic time complexities and a lower bound on the time after which a rehashing must occur. We further showed that overflow tables can improve the distribution of elements among the buckets when the maximum bucket size is too small with respect to the number of elements to hash.  The measured memory must be treated with some reservation since the actual operating system memory allocator is not measured in the experiments. By allocating many tiny fragments of space, the non-measured space might not be non-negligible.  doi  link  dblp  code  mirror   9 citations
  97.  [j16] 
    Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    c-trie++: A dynamic trie tailored for fast prefix searches.  Inf. Comput. 285 Part B (104794), pages 1–22. (2022)
    We extended our introduction of a novel trie in [c17] by a more detailed evaluation. Here, we tested random and sorted insertion of keywords, and the effect of querying the generated data structure with the same distribution, a different random distribution or in sorted order. Despite the fact that the performance of our presented trie shows a strong dependency on that order with the sorted setting being the best case, it still outperforms other compact tries on less favorable distributions.  doi  link  dblp  code  mirror   18 citations
  98.  [j15] 
    Dominik Köppl:
    Linking Off-Road Points to Routing Networks.  Algorithms 15(5) (163), pages 1–15. (2022)
    We analyze ways in how to add two-dimensional points to routing networks that can be represented locally on a two-dimensional plane with the Euclidean metric. We give a practical use case for the spatial extension pgrouting of the Postgres database in how this linkage can practically be achieved.  doi  link  dblp  mirror 
  99.  [t15] 
    クップル ドミニク:
    圧縮指標 : 計算と特定.  AFSA B01 Group Meeting SSSS 2022.05. (2022)
      slide 
  100.  [j14] 
    Alexandre P. Francisco, Travis Gagie, Dominik Köppl, Susana Ladra, Gonzalo Navarro:
    Graph Compression for Adjacency-Matrix Multiplication.  SN Computer Science 3 (193), pages 1–8. (2022)
    We study two compression schemes for binary matrices in the light of an index for matrix-vector multiplications, namely (1) the WebGraph format, which encodes a row by a reference to a former row plus difference information, and (2) an extraction of bicliques, i.e., two sets of vertices where each node of the first set has arcs to all nodes of the second set. We perform such a compression and use the compressed matrix for PageRank computation, where we directly compute multiplications on the compressed representation without decompression, leveraging the fact that the compression removed redundancies.   doi  dblp  code  manuscript  mirror   6 citations
  101.  [c30] 
    Jin Jie Deng, Wing-Kai Hon, Dominik Köppl, Kunihiko Sadakane:
    FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns.  Proc. DCC (Rank B), pages 63–72. (2022)
      We build the Burrows-Wheeler transform on a text that has been grammar-compressed with the grammar deduced by induced suffix sorting, and show that this grammar exhibits properties to accelerate the backward search of the FM-index, which we now perform not only single characters but on the non-terminals produced by the grammar that serve as meta-characters. This speed-up can compensate the additional time for the grammar parse of the pattern if the pattern is long enough.  doi  link  dblp  arxiv  code  manuscript 
  102.  [c29] 
    Dominik Köppl, Gonzalo Navarro, Nicola Prezza:
    HOLZ: High-Order Entropy Encoding of Lempel–Ziv Factor Distances.  Proc. DCC (Rank B), pages 83–92. (2022)
      We propose an alternative encoding of the offset values of the LZ77 parsing by using the distances of the already parsed prefixes of the text sorted in colexicographic order, and achieve better compression ratios than the rightmost parsing or the bit-optimal parsing when the text has low k-th order empirical entropy.  This work is strongly related to old compression methods like the ACB and HYZ compression with the difference that these methods use only contexts of bounded length when sorting the prefixes of the processed text in co-lexicographic order.  doi  link  dblp  arxiv  code  manuscript  slide  video  youtube 
  103.  [c28] 
    Dominik Köppl:
    Computing Lexicographic Parsings.  Proc. DCC (Rank B), pages 232–241. (2022)
    We present a linear-time algorithm for computing the lex-parse via the ϕ-Array, for which we devise a sparse representation. Compared to previous implementations, we could significantly reduce the working space required for computing lex-parse. We obtain similar results for plcpcomp introduced in [c15].  doi  link  dblp  manuscript  slide  video  youtube   3 citations
  104.  [i15] 
    坂内 英夫, 後藤 啓介, 石畠 正和, 神田 峻介, クップル ドミニク, 西本 崇晃:
    SATソルバを用いたNP困難な圧縮指標の高速計算.  人工知能学会研究会資料 人工知能基本問題研究会 120 (11), pages 61–66. (2022)
      Presentation of [c33] in Japanese  doi  manuscript 
  105.  [j13] 
    Dominik Köppl:
    Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks.  Information 13(4) (168), pages 1–28. (2022)
    We study a weaker problem of the shortest path problem in that we just want a ranking of vertices with respect to the distance to a query vertex, which can be helpful in recommender systems. There, we provide a cache that can speed up such queries when they are issued subsequently and in a sufficient vicinity. This cache is an orthogonal enhancement to graph indices like contraction hierarchies.  doi  link  dblp  code  mirror   5 citations
  106.  [i14] 
    赤木 亨, ドミニク クップル, 中島 祐人and 稲永 俊介, 坂内 英夫, 竹田 正幸:
    文法圧縮索引構造 GCIS-index.  Local Proceedings of the LA Symposium Summer 2021. (2022)
      Presentation of [c26] in Japanese. 
  107.  [i13] 
    クップル ドミニク:
    圧縮表現に基づいた大規模データ処理.  LAシンポジウム会誌77号. (2022)
      mirror 
  108. 2021
  109.  [i12] 
    クップル ドミニク:
    省領域な lexicographic parse 構築アルゴリズム.  Local Proceedings of コンピュテーション研究会, 信学技報 121 (285), pages 38–39. (2021)
      Presentation of [c28] in Japanese.  link  mirror  photo  slide 
  110.  [t14] 
    Dominik Köppl:
    Managing Text Data.  "European Researchers in Japan: Achievements and Opportunities": European Research Days 2021. (2021)
     slide 
  111.  [c27] 
    Tomohiro I, Dominik Köppl, Robert Irving, Lorna Love:
    Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree.  Proc. SPIRE (Rank B), LNCS 12944, pages 143–150. (2021)
    We review the suffix binary search tree for sparse suffix sorting. The suffix binary search tree is a binary search tree for storing dynamically suffixes, and can be made balanced by using AVL tree techniques. While it is easy to extract the sparse suffix array with an in-order tree traversal, we can do so also for the sparse longest common prefix table if we keep track of the longest common prefix of the lowest left and the lowest right ancestor node.  doi  dblp  manuscript  slide  video  youtube 
  112.  [c26] 
    Tooru Akagi, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    Grammar Index by Induced Suffix Sorting.  Proc. SPIRE (Rank B), LNCS 12944, pages 85–99. (2021)
    We index the rules of the grammar deduced by induced suffix sorting with a suffix tree and use it for pattern matching on the pattern compressed with the same grammar. For that, we make the observation that the grammar rules produced for the pattern equal the rules for the text, except at the borders of the pattern. After finding these equal grammar rules in the grammar tree of the text, we need to do some extra work to extend these to cover the whole pattern. For that, we build the generalized suffix tree on the right hand sides of all rules of the text grammar to support longest common extension queries that speed up the comparison. Our index performs practically well on highly-repetitive texts.   doi  dblp  arxiv  code  manuscript   8 citations
  113.  [c25] 
    Hideo Bannai, Mitsuru Funakoshi, Tomohiro I, Dominik Köppl, Takuya Mieno, Takaaki Nishimoto:
    A Separation of γ and b via Thue–Morse Words.  Proc. SPIRE (Rank B), LNCS 12944, pages 167–178. (2021)
      While it is know that Thue-Morse words have string attractors of size 4 (for large enough such words), we here proof that the size of the smallest bidirectional macro scheme of such a word scales logarithmic with their lengths. Up so far, this is the first observation that the size of the smallest string attractors is asymptotically smaller than the size of the smallest bidirectional macro scheme of more than a constant factor.   doi  dblp  arxiv  manuscript 
  114.  [j12] 
    Diego Arroyuelo, Rodrigo Cánovas, Johannes Fischer, Dominik Köppl, Marvin Löbel, Gonzalo Navarro, Rajeev Raman:
    Engineering Practical Lempel–Ziv Tries.  ACM JEA 26 (14), pages 1.14:1–1.14:47. (2021)
      We improve on the LZ trie implementations studied in [c13] together with an LZ78 variant that encodes the output in a compact hash table to keep the working space small. We engineer a new trie representation with the hash table proposed in [c20]. This trie keeps multiple of these hash tables, each for different bit ranges for the values, and optionally also for the keys to store. We also use the latter hash table in the LZ78 variant, where we use a Bonsai trie representing the LZ78 trie as well as part of the parsing, since we here only emit the positions of the stored nodes in the hash table instead of the standard LZ78 coding. This can save space if the hash table has a high load factor.  doi  dblp  mirror 
  115.  [t13] 
    Dominik Köppl:
    Computation of Variations of the LZ77 factorization and the LPF Array with Suffix Trees.  WCTA. (2021)
    Presentation of [j11] and [j9].  slide  video 
  116.  [c24] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Constructing the Bijective and the Extended Burrows–Wheeler Transform in Linear Time.  Proc. CPM (Rank B), LIPIcs 191, pages 7:1–7:16. (2021)
      We show how to construct the bijective Burrow-Wheeler transform (BBWT) in linear time with a modification of the SAIS algorithm computing the suffix array in linear time. The idea is to simulate SAIS while paying attention at the Lyndon factor borders such that the inducing step of SAIS is based on the context within a Lyndon factor, and not on the characters preceding the factor. This gives us a so-called circular suffix array, with which it is easy to obtain the BBWT.  doi  dblp  arxiv  mirror  slide  video  youtube 
  117.  [t12] 
    Dominik Köppl:
    Bijective Burrows Wheeler Transform - Open Problems -.  37th StringMasters. (2021)
     slide 
  118.  [j11] 
    Dominik Köppl:
    Reversed Lempel–Ziv Factorization with Suffix Trees.  Algorithms 14(6) (161), pages 1–26. (2021)
    We apply the suffix tree compositions studied in [j1] for the reversed LZ variant and the respective LPF array variant. The space become twice as big since we index also the reversed text for finding reversed matches during the factorization. On the upside, the time complexities are the same as when computing the standard LZ parsing.  doi  dblp  mirror   1 citation
  119.  [t11] 
    Dominik Köppl:
    (Resource-Constraint + Privacy)-Aware Data Structures Tackling Problems in Bioinformatics.  AFSA first general meeting. (2021)
      slide 
  120.  [c23] 
    Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, Massimiliano Rossi:
    PHONI: Streamed Matching Statistics with Multi-Genome References.  Proc. DCC (Rank B), pages 193–202. (2021)
    We practically implement an algorithm computing the matching statistics with the r-index and a grammar supporting longest common extension (LCE) queries by a single reverse scan over the pattern. This scan is done by classic FM-index backward search steps. Whenever we have a mismatch with the r-index, we issue LCE queries at the text positions of the closest positions in the BWT with characters equal to the pattern character we want to match. The longest such match leads us to the next matching statistics length. Unlike previous algorithms that use two passes over the pattern but have better theoretical time complexities, our proposed algorithm is practically faster since querying the grammar sometimes can be less expensive than a second pass over the pattern.   doi  link  dblp  arxiv  code  slide  video  youtube 
  121.  [t10] 
    Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, Massimiliano Rossi:
    PHONI: Streamed Matching Statistics with Multi-Genome References.  Data Structures in Bioinformatics. (2021)
      Workshop-Presentation of [c23].   33 citations
  122.  [j10] 
    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto:
    Re-Pair in Small Space.  Algorithms 14(1) (5), pages 1–20. (2021)
      We elaborate on the nearly in-place algorithm of [c22]. We derive from these techniques a bit-parallel algorithm, a parallel algorithm (working with multiple threads), and an algorithm working in external memory. We further show that these techniques can be adapted for the computation of the MR-Re-Pair compression variant, that takes not the most frequent bigram per se, but the maximal repeat containing that bigram.  doi  dblp  code  mirror   3 citations
  123.  [j9] 
    Dominik Köppl:
    Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees.  Algorithms 14(2) (44), pages 1–21. (2021)
    First, we propose an application of the suffix tree compositions studied in [j1] for the non-overlapping LZ variant and the respective LPF array variant. This algorithm works in the same space as the algorithm for the standard LZ parsing, and the time complexities are linear or near-linear. Second, we show how to perform substring compression queries for LZ78 in time linear in the number of phrases to compute. With space-efficient suffix tree representations, we get a logarithmic time penalty, which we can slightly improve by using the centroid path-decomposed suffix tree.  doi  dblp  mirror   12 citations
  124. 2020
  125.  [j8] 
    Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    Space-efficient algorithms for computing minimal/shortest unique substrings.  Theor. Comput. Sci. Volume 845, pages 230–242. (2020)
      We enhance our results in [c16] with variations using compressed data structures with time and space trade-offs. On of these are the suffix trees studied in [j1]. We further give the maximum working space needed for each phase during the construction of our data structure.   doi  dblp  arxiv  manuscript   3 citations
  126.  [j7] 
    Shunsuke Kanda, Dominik Köppl, Yasuo Tabei, Kazuhiro Morita, Masao Fuketa:
    Dynamic Path-Decomposed Tries.  ACM JEA 25 (1), pages 1.13:2–1.13:28. (2020)
      We derive a dynamic variant of the centroid-path decomposition of static trees for devising a dynamic trie, where each node stores a keyword, while its children share a common prefix with this keyword. While the keywords are stored prefix-compressed in an auxiliary data structure, the remaining tree is indexed with a compact hash table trie representation such as the one suggested in [c13].   doi  dblp  arxiv  code  manuscript   10 citations
  127.  [c22] 
    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto:
    Re-Pair in Small Space.  Proc. PSC (Rank national), pages 134–147. (2020)
      We provide an algorithm computing the grammar compression re-pair in small up to constant additional space while allowing up to quadratic time. The idea is that we successively use freed-up text space for storing frequency tables storing the most frequent bigrams. We study the conditions in which such a table needs to be updated, or when we can continue the computation with the old table.  link  dblp  mirror  photo  slide  video  youtube 
  128.  [j6] 
    Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    Grammar-compressed Self-index with Lyndon Words.  IPSJ TOM 13 (2), pages 84–92. (2020)
      We build a grammar index on the grammar induced by the Lyndon tree, which uses properties of Lyndon words to accelerate pattern matching as usually done by a grid for grammar indices that tries to divide a pattern at each possible position.  link  arxiv  manuscript   15 citations
  129.  [c21] 
    Jacqueline W. Daykin, Dominik Köppl, David Kübel, Florian Stober:
    On Arithmetically Progressed Suffix Arrays.  Proc. PSC (Rank national), pages 96–110. (2020)
      We exhaustively characterize all strings having an arithmetic progression as a suffix array, and determine the shape of the Burrows-Wheeler transform induced by such suffix arrays. In particular, given an arithmetic progression, we find a uniquely defined string of minimal alphabet size whose suffix array is this progression. This minimal alphabet size can be at most three. Further, this generalizes the results presented in [c6].  link  dblp  arxiv  mirror 
  130.  [j5] 
    Johannes Fischer, Tomohiro I, Dominik Köppl:
    Deterministic Sparse Suffix Sorting in the Restore Model.  ACM Trans. Algorithms 16 (4), pages 50:1–50:53. (2020)
      We provide a full version of [c9] with an additional proof that the upper bound on the number of changed nodes in the edit-sensitive parsing has to be higher by a logarithmic factor than claimed in literature. This observation strengthens the reason of our proposed modification of that grammar, which is not prone to this change.   doi  link  dblp  mirror   9 citations
  131.  [c20] 
    Dominik Köppl, Simon J. Puglisi, Rajeev Raman:
    Fast and Simple Compact Hashing via Bucketing.  Proc. SEA (Rank B), LIPIcs 160, pages 7:1–7:14. (2020)
      We extend the study in [i7] by providing a variant, where buckets are implicitly represented as parts of a meta-bucket, which stores a bit vector for the beginning of a bucket inside the meta-bucket. This improves the average load-factor per bucket, which can become skewed if the maximal allowed bucket size is too small with respect to the input size.  doi  dblp  arxiv  mirror  slide  video  youtube 
  132.  [c19] 
    Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian, Ayumi Shinohara:
    In-Place Bijective Burrows–Wheeler Transforms.  Proc. CPM (Rank B), LIPIcs 161, pages 21:1–21:15. (2020)
      We provide algorithms computing and reverting the bidirectional Burrows-Wheeler transform (bijective BWT) in quadratic time with only constant additional space. Up so far, it was only known how to do the same for the BWT in the same complexities. We additionally give an algorithm for converting a BWT to the bijective BWT or back directly within the same complexities.   doi  link  dblp  arxiv  code  mirror  slide  video  youtube 
  133.  [j4] 
    Roland Glück, Dominik Köppl:
    Computational Aspects of Ordered Integer Partition with Bounds.  Algorithmica 82 (10), pages 2955–2984. (2020)
    We parallelized our algorithm proposed in [c1]. For that, it is possible to generate a dependency graph of the polynomials we want to construct. To maximize parallelization, we traverse this graph in topological order, starting with the polynomials having no dependencies. We empirically could evaluate that this schedule leads to an algorithm that scales very well with increasing number of threads.  doi  dblp  code  Nature SharedIt  manuscript 
  134.  [t9] 
    Dominik Köppl:
    In-Place (Bijective) BWT の構築.  Stringbeginners 2020. (2020)
      slide 
  135.  [c18] 
    Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto:
    Re-Pair in Small Space (Poster).  Proc. DCC (Rank A*), pages 377. (2020)
      Poster presentation of [c22].  doi  link  dblp  arxiv  manuscript  poster  video  youtube 
  136.  [c17] 
    Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    c-Trie++: A Dynamic Trie Tailored for Fast Prefix Searches.  Proc. DCC (Rank A*), pages 243–252. (2020)
      We algorithmically engineer a combination of z-fast tries and compact tries, which allows us to perform fast prefix search queries via word-packing. Its empirical space usage is much lower than other known compact trie implementations while also being among one of the fastest.   doi  link  dblp  arxiv  slide  video 
  137.  [t8] 
    Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian, Ayumi Shinohara:
    In-Place Bijective Burrows–Wheeler Transforms.  Data Structures in Bioinformatics. (2020)
    Workshop-Presentation of [c19].  slide 
  138.  [t7] 
    Dominik Köppl:
    Constructing the Bijective BWT.  The 28th London Stringology Days and London Algorithmic Workshop. (2020)
    Workshop-Presentation of [c24].  mirror   5 citations
  139. 2019
  140.  [i11] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Constructing the Bijective BWT.  Local Proceedings of the 175th アルゴリズム研究会, 研究報告アルゴリズム 175 (19), pages 1–6. (2019)
      Presentation of [c24] in Japanese.  link  manuscript  slide 
  141.  [c16] 
    Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
    Compact Data Structures for Shortest Unique Substring Queries.  Proc. SPIRE (Rank B), LNCS 11811, pages 107–123. (2019)
    We give a lightweight data structure for answering point and interval shortest unique substring (SUS) queries, for which we detect and index minimal unique substrings. While previous data structures already can report a point SUS in constant time, they need words of space linear in text size. Here, we give solutions working in bits of space linear in the text length.   doi  dblp  arxiv  manuscript   5 citations
  142.  [c15] 
    Patrick Dinklage, Jonas Ellert, Johannes Fischer, Dominik Köppl, Manuel Penschuck:
    Bidirectional Text Compression in External Memory.  Proc. ESA (Rank A), pages 41:1–41:16. (2019)
    We give a space-efficient algorithm for the lcpcomp compressor defined in [c11]. We can also compute lcpcomp in external memory for massive datasets efficiently. For the decompression, we give the first algorithm for decompressing an arbitrary bidirectional macro scheme, and give I/O complexities for this algorithm.  doi  dblp  arxiv  mirror  slide 
  143.  [i10] 
    クップル ドミニク, 井 智弘, 古谷 勇, 高畠 嘉将, 酒井 健輔, 後藤 啓介:
    Re-Pair In-Place.  Local Proceedings of the LA Symposium Summer 2019. (2019)
      Presentation of [c22] in Japanese.  manuscript  photo  slide 
  144.  [i9] 
    鶴田 和弥, Dominik Köppl, 神田 峻介, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸:
    Dynamic Trie Tailored for Fast Prefix Searches.  Local Proceedings of the LA Symposium Summer 2019. (2019)
      Presentation of [c17] in Japanese. 
  145.  [i8] 
    三重野 琢也, Dominik Köppl, 中島 祐人, 稲永 俊介, 坂内 英夫, 竹田 正幸:
    最短非反復部分文字列問題に対するコンパクトなデータ構造.  Local Proceedings of the LA Symposium Summer 2019. (2019)
      Presentation of [c16] in Japanese. 
  146.  [t6] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Searching Patterns in the Bijective BWT.  Dagstuhl Seminar 19241 "25 Years of the Burrows-Wheeler Transform", pages 65. (2019)
    Presentation of ideas published in [c14] with more details.  mirror  slide 
  147.  [c14] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Indexing the Bijective BWT.  Proc. CPM (Rank B), LIPIcs 128, pages 17:1–17:14. (2019)
    We augment the bijective Burrows-Wheeler transform with FM-indexing techniques for pattern matching with a potential multiplicative-logarithmic slow down for tracking false and missing occurrences of a pattern. Since the bijective BWT is derived by the previous character of each cyclic rotation of all Lyndon conjugates sorted in the ω-order, a backward search step at the beginning of a Lyndon factor gives us not the previous character but the end of this Lyndon factor. For such cases, the index has to do extra counting for occurrences not in the suffix array interval, or false positives contained in it.   doi  dblp  mirror  slide 
  148.  [i7] 
    Dominik Köppl:
    Separate Chaining Meets Compact Hashing.  Local Proceedings of the 173th アルゴリズム研究会, 研究報告アルゴリズム 173 (5), pages 1–11. (2019)
      We algorithmically engineer a compact hash table with separate chaining, suitable for storing and querying integers with small bit widths.  link  manuscript  photo  slide   7 citations
  149.  [i6] 
    Patrick Dinklage, Jonas Ellert, Johannes Fischer, Dominik Köppl, Manuel Penschuck:
    PLCP配列に基づくテキスト圧縮.  Local Proceedings of the LA Symposium Winter 2018. (2019)
      Presentation of [c15] in Japanese.  manuscript  photo  slide 
  150.  [i5] 
    赤木 亨, 中島 祐人, ドミニク クップル, 稲永 俊介, 坂内 英夫, 竹田 正幸:
    GCIS による文法圧縮テキスト上のパターン照合.  Local Proceedings of the LA Symposium Winter 2018. (2019)
      Presentation of [c26] in Japanese. 
  151.  [j3] 
    Tomohiro I, Dominik Köppl:
    Improved upper bounds on all maximal α-gapped repeats and palindromes.  Theor. Comput. Sci. Volume 753, pages 1–15. (2019)
    We refine the upper bounds stated in [j2] on the maximum number of all maximal α-gapped repeats and palindromes. To this end, we leverage some properties of periodic substrings, and improve the analysis where we map gapped repeats or palindromes to two-dimensional points spawning rectangles that must not overlap.   doi  dblp  manuscript   9 citations
  152. 2018
  153.  [j2] 
    Paweł Gawrychowski and Tomohiro I and Shunsuke Inenaga and Dominik Köppl and Florin Manea:
    Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.  Theory Comput. Syst. 62 (1), pages 162–191. (2018)
    We improve [c7] with tighter combinatorial bounds. We state that the upper bound, which is linear in the text length and α, is tight by a known lower bound. We explicitly give numbers for the upper bounds on the maximum number of all maximal α-gapped repeats and palindromes appearing in a text of length n. We also explicitly give proof details for the palindromic case, which we omitted in the conference version due to page limit restrictions. We also give an algorithm finding all maximal α-gapped palindromes in time linear in α and the text length, which is optimal in the worst case.   doi  link  dblp  Nature SharedIt  mirror 
  154.  [b2] 
    Dominik Köppl:
    Exploring regular structures in strings.  Dissertation at TU Dortmund. (2018)
    We unify the analysis of α-gapped repeats and α-gapped palindromes of our previous papers and give some applications for our algorithm computing LZ77 with the suffix tree. Compared to [j2], we could improve the proofs with some cases neglected in that version. Explanations have been enhanced with elaborated examples.  The analysis of fragile nodes for the lower-bound of the ESP parsing should emphasize that there is an example in which *all* of the analyzed fragile nodes change. The notion of fragile nodes just states that a fragile node can be parsed differently, but in the shown example all studied fragile nodes indeed change.  doi  link  dblp  manuscript  slide   6 citations
  155.  [j1] 
    Johannes Fischer, Tomohiro I, Dominik Köppl, Kunihiko Sadakane:
    Lempel–Ziv Factorization Powered by Space Efficient Suffix Trees.  Algorithmica 80 (7), pages 2048–2081. (2018)
    We unify the results in [c5] and [c8]. We improve the time complexities of the algorithms working with compressed suffix trees to linear. We largely simplified the LZ78 computation by using bits for counting in unary to what extent a suffix tree edge has been explored by the LZ trie when superimposing the suffix tree with the LZ trie.  doi  dblp  Nature SharedIt  manuscript   30 citations
  156.  [t5] 
    Dominik Köppl:
    Plug&Play Kompression mit dem Framework tudocomp.  Vortragsreihe der Regionalgruppe der Gesellschaft für Informatik aus Dortmund. (2018)
      User guide in how to work with the compression framework tudocomp.  manuscript  slide 
  157.  [i4] 
    Dominik Köppl:
    Lempel–Ziv with Integer Coders.  Newsletter of the SoBigData Research Infrastructure, Issue 1. (2018)
    A study of the distribution of distances and lengths of LZ phrases.  mirror 
  158.  [t4] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Indexing the Bijective BWT.  32th Mini-Workshop "Theoretical Computer Science" at TuDo and RUB. (2018)
    Workshop-Presentation of [c14]. 
  159. 2017
  160.  [c13] 
    Johannes Fischer and Dominik Köppl:
    Practical Evaluation of Lempel–Ziv-78 and Lempel–Ziv–Welch Tries.  Proc. SPIRE (Rank B), LNCS 9472, pages 191–207. (2017)
    We conduct an experimental analysis for various practical trie data structures for computing the LZ78 parsing, with focus on some trie representations that use hashing techniques. Here, we present a Monte-Carlo algorithm based on fingerprint-hashing substrings of the text for checking whether substringns are already part of the LZ78 dictionary. For large fingerprints, we could not observe a failure for even hundreds of megabytes of real-word texts, while outpacing other common solutions. We also present a representation of the LZ78 trie with a compact hash table that uses less space than other known solutions.  doi  link  dblp  arxiv  slide 
  161.  [i3] 
    Andre Brehme, Sven Brümmer, Jonas Charfreitag, Jonas Ellert and Jannik Junghänel, Dominik Köppl, Christopher Osthues, Sven Rahmann, Dennis Rohde and Julian Sauer, Jonas Schmidt, Lars Schäpers, Uriel Elias Wiebelitz, Jens Zentgraf:
    PanGeA: Pan-Genome Annotation Indexing Annotated Human Genome Collections.  German Conference on Bioinformatics (GCB). (2017)
    We compare several approaches such as colored de-Brujin graphs, CHICO, journaled string trees and relative LZ for their suitability in maintaining and querying genomic data with high similarity. We empirically evaluated that colored de-Brujin graphs are good pre-filters since small yet efficient implementations exist.   mirror  poster 
  162.  [t3] 
    Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski:
    Indexing the Bijective BWT.  WCTA. (2017)
    Workshop-Presentation of [c14].  manuscript  slide 
  163.  [c12] 
    Hideo Bannai, Shunsuke Inenaga, Dominik Köppl:
    Computing All Distinct Squares in Linear Time for Integer Alphabets.  Proc. CPM (Rank B), LIPIcs 78, pages 22:1–22:18. (2017)
    We present a practical linear-time algorithm computing all distinct squares for integer alphabets. We improve on an algorithm of Gusfield and Stoye, who used the Lempel-Ziv factorization for spotting possible locations of the leftmost occurrences of squares. For that, we used a range minimum query data structure on the longest common prefix factor array to quickly decide whether a substring of a certain length is the leftmost occurrence. With that, we could get the algorithm down to linear time, which was previously only possible with this algorithm for constant-size alphabets. We further studied similar techniques when computing all distinct squares online by using an online construction of the suffix tree augmented with dynamic tree data structures.  The definition of the factors by the LCP array in Sect. 3 is wrong; we need make each factor shorter by one character to be correct. We also have to note that the linear-time computation is already possible with the work of Crochemore et al.: "Extracting powers and periods in a word from its runs structure", TCS'14.  doi  link  dblp  arxiv  code  mirror  photo  slide 
  164.  [c11] 
    Patrick Dinklage, Johannes Fischer, Dominik Köppl, Marvin Löbel, Kunihiko Sadakane:
    Compression with the tudocomp Framework.  Proc. SEA (Rank B), LIPIcs 75, pages 13:1–13:22. (2017)
    We present a C++ compression framework for easy implementation and comparison with well-known compression techniques like LZ77. To this end, we proposed a new bidirectional parsing, called lcpcomp, which is a lexicographic parsing in that it greedily takes the maximum longest longest common prefix values of neighboring suffixes in the suffix array, and replaces one with a reference to the other. Further, we provide an LZ78-variant where factors are enlarged until they are right-maximal repeats. We empirically show that the encoding of both factorizations are competitive with existing compression solutions.  The linear time argument for the compression algorithm in Section 3.2.2. is not complete. The linear time follows from the fact that we look-up m positions for decrease while deleting m positions when creating a factor of length m. Therefore, the time for deleting and decreasing is bounded by the factor lengths, which sums up to O(n).   doi  link  dblp  arxiv  code  manuscript  mirror  slide   23 citations
  165.  [t2] 
    Hideo Bannai, Shunsuke Inenaga, Dominik Köppl:
    Computing All Distinct Squares in Linear Time for Integer Alphabets.  30th Mini-Workshop "Theoretical Computer Science" at TuDo and RUB. (2017)
    Presentation of the result of [c12].  link  slide   29 citations
  166. 2016
  167.  [c10] 
    Johannes Fischer, Dominik Köppl, Florian Kurpicz:
    On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.  Proc. CPM (Rank B), LIPIcs 54, pages 26:1–26:11. (2016)
    We use the merging of suffix array intervals to speed up approximate pattern matching queries, i.e., matching a pattern with a text while allowing an upper bound on the distance (Levenshtein or Hamming distance). Our main tool is that the merging of suffix array intervals corresponding to matched parts of the pattern can be parallelized - a fact that we use when first computing the suffix array intervals of all prefixes and suffixes of parts of the pattern for the case of one error. We finally generalize this to arbitrary error bounds with the result of Huynh et al.  doi  link  dblp  arxiv  mirror 
  168.  [c9] 
    Johannes Fischer and Tomohiro I and Dominik Köppl:
    Deterministic Sparse Suffix Sorting on Rewritable Texts.  Proc. LATIN (Rank B), LNCS 9644, pages 483–496. (2016)
    We devise a deterministic algorithm for sparse suffix sorting in compact space when allowing to reversibly edit the input text. We use a grammar compression technique for fast longest common extension queries, which we write on redundant parts of the text detected while computing the sparse suffix sorting online. Our grammar is based on the edit-sensitive parsing, where our modification makes it possible to bound the number of nodes of a grammar tree deriving a certain part of the text, while being robust to context changes, i.e., two grammar trees containing a large portion of the same substring also have most nodes in common.   doi  link  dblp  arxiv  mirror  slide   17 citations
  169.  [c8] 
    Dominik Köppl, Kunihiko Sadakane:
    Lempel–Ziv Computation in Compressed Space (LZ-CICS).  Proc. DCC (Rank A*), pages 3–12. (2016)
    We adapt the algorithm of [c5] with focus on small alphabets by using the compressed suffix tree. The main obstacle for using the compressed suffix tree for efficient computation of the LZ77 and LZ78 parsing is the inability to perform fast string-depth queries, i.e., the length of a string a node in the suffix tree presents. Here, we provide a solution that emulates suffix links by taking two leaves of a node and compute their ψ-values, which takes us to two leaves whose lowest common ancestor would be connected by a suffix link of that node.  The number of giant nodes can be in the worst case O(n) - O(lg n), not O(n/lg n) like proposed in the paper. This is not a problem since it is sufficient to store the exploration counters of the lowest giant nodes, which are O(n/ lg n) many. A giant node that is not the lowest giant node can adopt one exploration counter of one lowest giant node in its subtree until it got fully explored.  doi  link  dblp  arxiv  manuscript  slide 
  170.  [c7] 
    Paweł Gawrychowski and Tomohiro I and Shunsuke Inenaga and Dominik Köppl and Florin Manea:
    Efficiently Finding All Maximal α-gapped Repeats.  Proc. STACS (Rank B), LIPIcs 47, pages 39:1–39:14. (2016)
    We propose the first algorithm computing all maximal α-gapped repeats in time linear in α and the text length. We additionally give upper bounds on the maximum number of all maximal α-gapped repeats a text of a certain length can have, which matches the asymptotic time bounds of the proposed algorithm, supporting that its time complexity is optimal in the worst case. The previously best known upper bound was quadratic in α.   doi  link  dblp  arxiv  mirror 
  171. 2015
  172.  [t1] 
    Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea:
    Efficiently Finding All Maximal α-gapped Repeats.  28th Mini-Workshop "Theoretical Computer Science" at TuDo and RUB. (2015)
    Presentation of the result of [c7].  link  slide 
  173.  [c6] 
    Dominik Köppl and Tomohiro I:
    Arithmetics on Suffix Arrays of Fibonacci Words.  Proc. WORDS, LNCS 9304, pages 135–146. (2015)
    We study the shapes of the suffix array, its inverse, and the Burrows-Wheeler transform of Fibonacci words and some of its relatives. We discover that the suffix array is an arithmetic progression for even Fibonacci words, and that the inverse suffix array is a rotation of it.  doi  link  dblp  manuscript  slide   4 citations
  174.  [i2] 
    Marcel Bargull, Kada Benadjemia, Benjamin Kramer, David Losch, Jens Quedenfeld, Sven Schrinner, Jan Stricker, Dominik Köppl, Dominik Kopczynski, Henning Timm, Johannes Fischer, Sven Rahmann:
    Variant Tolerant Read Mapping with Locality Sensitive Hashing.  German Conference on Bioinformatics (GCB). (2015)
    We present a read-mapper that uses local-sensitive hashing as a pre-filter and a semi-global alignment against a reference augmented variations for variant-tolerant read-mapping. Most read-mappers work with a single reference genome such that they cannot take common variants into considerations. Using a set of reference genomes of the same species makes it possible to tolerate variants with the hope to increase the accuracy of the read-mapping. While our proposed pre-filter is fast, it produces many false positives, which we eliminate by a careful alignment step using Ukkonen's semi-global alignment algorithm.   doi  mirror  poster 
  175.  [c5] 
    Johannes Fischer and Tomohiro I and Dominik Köppl:
    Lempel Ziv Computation in Small Space (LZ-CISS).  Proc. CPM (Rank B), LNCS 9133, pages 172–184. (2015)
    We present linear-time LZ77 and LZ78 algorithms using a lightweight suffix array implementation whose largest component is the suffix array. Compared to other linear-time algorithms computing LZ77 or LZ78, these algorithms have the lowest space requirements up so far when the alphabet size of the input text is not too small. For that, we heavily relied on overwriting parts of our working space such that in the end we transformed the suffix array into an array storing the output of one of the factorizations.   doi  link  dblp  arxiv  slide   25 citations
  176.  [c4] 
    Don S. Batory and Peter Höfner and Dominik Köppl and Bernhard Möller and Andreas Zelend:
    Structured Document Algebra in Action.  Proc. Software, Services, and Systems, LNCS 8950, pages 291–311. (2015)
    We put software product lines into algebraic context and give examples with extensions to common programming languages to highlight where such modularization helps. Some programming languages like C have macros that can be used as variation points in program code, which can be filled afterwards, for instance with the inclusion of external files. Here, we provide an abstract framework for such kind of substitutions, and present an algebra for working with them.  doi  link  dblp  manuscript   12 citations
  177. 2014
  178.  [i1] 
    Dominik Köppl:
    Dynamic Skyline Computation with the Skyline Breaker Algorithm.  Local Proceedings of the Workshop on Massive Data. (2014)
    We present theoretical thoughts on how to use [c3] for the dynamic skyline problem. We prove that caching helps whenever subsequent queries are within a geometric region of a cached query.   doi  manuscript 
  179. 2013
  180.  [c3] 
    Dominik Köppl:
    Breaking Skyline Computation Down to the Metal: the Skyline Breaker Algorithm.  Proc. IDEAS (Rank B), pages 132–141. (2013)
    We study the effect of LSD-trees for computing the Pareto front, and enhance this tree-based approach with heuristics to improve the execution time empirically. The LSD-tree is a kd-tree whose leaves are enlarged to store buckets of arbitrary size. Because a bucket contains multiple elements before it gets split, the distribution of these elements can be taken into account to decide how to partition a full bucket into two. Such splitting effects the overall running time. We further parallelized our algorithm such that each thread maintains an LSD-tree but uses a synchronized list of output candidates for pre-filtering.   doi  link  dblp  code  mirror   4 citations
  181.  [c2] 
    Florian Wenzel and Dominik Köppl and Werner Kießling:
    Interactive Toolbox for Spatial-Textual Preference Queries.  Proc. SSTD (Rank A), LNCS 8098, pages 462–466. (2013)
    We give a show case for graph database systems that can find Pareto-optimal answers to queries that use spatial or/and textual attributes. We annotated a part of the San-Francisco bay location with points of interests storing textual attributes, and provided a database system that could filter points of interests by specifications in both textual and the spatial domains.   doi  link  dblp  manuscript   8 citations
  182.  [c1] 
    Roland Glück and Dominik Köppl and Günther Wirsching:
    Computational Aspects of Ordered Integer Partition with Upper Bounds.  Proc. SEA (Rank B), LNCS 7933, pages 79–90. (2013)
    We devise an algorithm with fixed-parameter tractability in the dimension size for finding the number of integer partitions for a queried integer if this integer has to be split into at most n parts, where each part has a fixed upper bound. We observed that this computation involves the iterative computation of polynomial summations, for which we used Faulhaber's formula. Experimental results show that a naive algorithm based on recursion is quickly outperformed on five dimensions with reasonably large query numbers.   doi  link  dblp   7 citations
  183. 2012
  184.  [b1] 
    Dominik Köppl:
    Pseudodifferentialoperatoren mit nichtglatten Koeffizienten auf Mannigfaltigkeiten.  Diplomarbeit (German) at Universität Regensburg. (2012)
      We extended the analysis of Hitoshi Kumano-Go's work on pseudo-differential operators to the case of non-smooth components. We also define such pseudo-differential operators on non-smooth manifolds, and show under which properties the transition map for non-smooth pseudo-differential operators is well-defined.  arxiv  manuscript   4 citations

Lectures

Contributions to the Research Community

Special Issue Editorial

PC Co-Chair

PC Memberships

Local Organizations

Grants

Seminar Participations

Promotion of the Youth