This is an old revision of the document!
Publications (Group Members in Bold)
Peer Reviewed Publications
2020
- Deterministic Sparse Suffix Sorting in the Restore Model
Johannes Fischer, Tomohiro I, Dominik Köppl
Accepted to ACM Trans. Algorithms. - LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
Accepted to Euro-Par. - Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, Ian Munro, Eva Rotenberg
Accepted to ICALP. (arXiv version) - Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory
Patrick Dinklage, Johannes Fischer, Florian Kurpicz
Proceedings of the 22nd Workshop on Algorithm Engineering and Experiments (ALENEX 2019), 214-228.
2019
- Comparing Approaches for Learning Abstraction and Automation by Object Orientation
Johannes Fischer, Arno Pasternak
Local Proc. ISSEP, 39–47, 2019. - Translating Between Wavelet Tree and Wavelet Matrix Construction
Patrick Dinklage
Proc. Prague Stringology Conference (PSC 2019), 126–136, 2019. - Parallel External Memory Wavelet Tree and Wavelet Matrix Construction
Jonas Ellert, Florian Kurpicz
Proceedings of the 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811, 407–416. - SACABench: Benchmarking Suffix Array Construction
Johannes Bahne, Nico Bertram, Marvin Böcker, Jonas Bode, Johannes Fischer, Hermann Foot, Florian Grieskamp, Florian Kurpicz, Marvin Löbel, Oliver Magiera, Rosa Pink, David Piper, and Christopher Poeplau
Proceedings of the 26th International Symposium on String Processing and Information Retrieval (SPIRE 2019), LNCS 11811, 392–406. - Bidirectional Text Compression in External Memory (arXiv version)
Patrick Dinklage, Jonas Ellert, Johannes Fischer, Dominik Köppl, Manuel Penschuk
Proc. of the 27th Annual European Symposium on Algorithms (ESA 2019), 41:1-41:16, 2019. - Lightweight Distributed Suffix Array Construction
Johannes Fischer, Florian Kurpicz
Proceedings of the 21st Workshop on Algorithm Engineering and Experiments (ALENEX 2019), 27–38, 2019. - Improved Upper Bounds on all Maximal α-gapped Repeats and Palindromes (arXiv version)
Tomohiro I, Dominik Köppl
Theoretical Computer Science, 753: 1–15, 2019.
2018
- Standards for Higher Secondary Education for Computer Science in Germany
Arno Pasternak, Lutz Hellmig and Gerhard Röhner
Proceedings ISSEP 2018, St. Petersburg, Russia, October 10-12, 2018, 117–128.
Informatics in Schools. Fundamentals of Computer Science and Software Engineering - Scalable Construction of Text Indexes with Thrill (arXiv version)
Timo Bingmann, Simon Gog, Florian Kurpicz
Proceedings of the IEEE International Conference on Big Data (BigData 2018), 634–643, 2018. - Lempel-Ziv-78 Compressed String Dictionaries (Nature SharedIt)
Julian Arz, Johannes Fischer
Algorithmica, Special Issue on Compact Data Structures, 80(7): 2012–2047, 2018. - Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees (Nature SharedIt)
Johannes Fischer, Tomohiro I, Dominik Köppl, Kunihiko Sadakane
Algorithmica, Special Issue on Compact Data Structures, 80(7): 2048–2081, 2018. - Tighter Bounds and Optimal Algorithms for all Maximal α-gapped Repeats and Palindromes (Nature SharedIt)
Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea
Theory of Computing Systems, 62(1): 162–191, 2018. - Simple, Fast and Lightweight Parallel Wavelet Tree Construction (arXiv version)
Johannes Fischer, Florian Kurpicz, Marvin Löbel
Proceedings of the 20th Workshop on Algorithm Engineering and Experiments (ALENEX 2018), 9–20, 2018. - Maximum Common Subgraph Problems in Series-Parallel Graphs (arXiv version)
Nils Kriege, Florian Kurpicz, Petra Mutzel
European Journal of Combinatorics (Eur. J. Combin.), 68:79–95, 2018.
2017
- Dismantling DivSufSort (arXiv version)
Johannes Fischer, Florian Kurpicz
Proceedings of the Prague Stringology Conference (PSC 2017), 62–76. - Modularisierung im Informatikunterricht aus lernpsychologischer Perspektive
Johannes Fischer, Arno Pasternak
Proc. INFOS 2017, Lecture Notes in Informatics 274, 247-256. - Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries (arXiv version)
Johannes Fischer, Dominik Köppl
Proceedings of the 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), LNCS 9472, 191–207. - FLOUDS: A Succinct File System Structure
Daniel Peters, Johannes Fischer, Florian Thiel, Jean-Pierre Seifert
FedCSIS 2017 Position Papers, 51-57. - Lempel-Ziv Compression in a Sliding Window
Philip Bille, Patrick Hagge Cording, Johannes Fischer, Inge Li Gørtz
Proceeding of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), LIPIcs 78, 15:1–15:11. - Computing All Distinct Squares in Linear Time for Integer Alphabets (arXiv version)
Hideo Bannai, Shunsuke Inenaga, Dominik Köppl
Proceeding of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), LIPIcs 78, 22:1–22:18.
- Compression with the tudocomp Framework (arXiv version)
Patrick Dinklage, Johannes Fischer, Dominik Köppl, Marvin Löbel, Kunihiko Sadakane
Proceeding of the 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs 75, 13:1–13:22.
- Engineering a Distributed Full-Text Index (arXiv version)
Johannes Fischer, Florian Kurpicz, Peter Sanders
Proceedings of the 19th Workshop on Algorithm Engineering and Experiments (ALENEX 2017), 120-134.
2016
Inducing Suffix and LCP Arrays in External MemoryTimo Bingmann, Johannes Fischer, Vitaly Osipov
Journal of Experimental Algorithmics (JEA) - Special Issue SEA 2014, Regular Papers and Special Issue ALENEX 2013, 2016- Sparse Text Indexing in Small SpacePhilip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj
ACM Transactions on Algorithms (TALG), 2016 - On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching (arXiv version)
Johannes Fischer, Dominik Köppl, Florian Kurpicz
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), LIPIcs 54, 2016, 26:1–26:11 - Deterministic Sparse Suffix Sorting on Rewritable Texts (arXiv version)
Johannes Fischer, Tomohiro I, Dominik Köppl
Proceedings of the 12th Latin American Symposium on Theoretical Informatics (LATIN 2016), LNCS 9644, 483-496 - Lempel Ziv Computation In Compressed Space (LZ-CICS) (arXiv version)
Dominik Köppl, Kunihiko Sadakane
Proceedings of the Data Compression Conference 2016 (DCC 2016), IEEE, 3-12. - Contextualized Teaching in the Lower Secondary Education - Long-term Evaluation of a CS Course from Grade 6 to 10
Arno Pasternak
Proceedings of the 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016), ACM Press, 2016, 657-662 - Efficiently Finding All Maximal α-gapped Repeats
Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea
Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), LIPIcs 47, 39:1-39:14. - GLOUDS: Representing Tree-Like Graphs
Johannes Fischer, Daniel Peters
J. Discrete Algorithms 36: 39-49. - Compressed Range Minimum Queries
Johannes Fischer
In Ming-Yang Kao (ed.): Encyclopedia of Algorithms (2nd edition), 379-382, Springer.
2015
- Inferring Strings from Full Abelian Periods
Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), LNCS 9472, 768-779 - Computer Science Education in North-Rhine Westphalia, Germany – A Case Study
Maria Knobelsdorf, Johannes Magenheim, Torsten Brinda, Dieter Engbring, Ludger Humbert, Arno Pasternak, Ulrik Schroeder, Marco Thomas, Jan Vahrenhold
ACM Transactions on Computing Education (TOCE) 15(2), Article No. 9 - Beyond the Runs Theorem (arXiv version)
Johannes Fischer, Štěpán Holub, Tomohiro I, Moshe Lewenstein
Proceedings of the 22nd Symposium of String Processing and Information Retrieval (SPIRE 2015), LNCS 9309, 277-286 - Approximating LZ77 via Small-Space Multiple-Pattern Matching (arXiv version)
Johannes Fischer, Travis Gagie, Pawel Gawrychowski, Tomasz Kociumaka
Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, 533-544 - Lempel-Ziv Computation in Small Space (arXiv version)
Johannes Fischer, Tomohiro I, Dominik Köppl
Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), LNCS 9133, 172-184 - Alphabet-Dependent String Searching with Wexponential Search Trees (arXiv version)
Johannes Fischer, Pawel Gawrychowski
Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), LNCS 9133, 160-171 - Arithmetics on Suffix Arrays of Fibonacci Words
Dominik Köppl, Tomohiro I
Proceedings of the 10th International Conference on Combinatorics on Words (WORDS 2015), LNCS 9304, 135-146 - A new characterization of maximal repetitions by Lyndon trees
Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta
Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 562-571. - Semi-dynamic compact index for short patterns and succinct van Emde Boas tree
Yoshiaki Matsuoka, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), LNCS 9133, 355-366. - A faster algorithm for computing maximal alpha-gapped repeats in a string
Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Proceedings of the 22nd Symposium on String Processing and Information Retrieval (SPIRE 2015), LNCS 9309, 124-136 - Detecting regularities on grammar-compressed strings
Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa and Ayumi Shinohara
Information and Computation 240:74-89 - Compressed automata for dictionary matching
Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Theoretical Computer Science 578:30-41 - Constructing LZ78 tries and position heaps in linear time for large alphabets.
Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Information Processing Letters 115(9):655-659 - Structured Document Algebra in Action
Don S. Batory, Peter Höfner, Dominik Köppl, Bernhard Möller, Andreas Zelend
Structured Document Algebra in Action. Software, Services, and Systems 2015, LNCS 8950, 291-311 - A Practical Succinct Data Structure for Tree-Like Graphs
Johannes Fischer, Daniel Peters
Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM 2015), LNCS 8973, 65-76
2014
- LZ-Compressed String Dictionaries
Julian Arz, Johannes Fischer
Proc. of the 24th Data Compression Conference (DCC 2014), 322-331 - High-Order Entropy Compressed Bit Vectors with Rank/Select
Kai Beskers, Johannes Fischer
Algorithms 7(4), 608-620 - Inferring Strings from Lyndon factorization
Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), LNCS 8635, Springer, 565-576 - On Maximum Common Subgraph Problems in Series-Parallel Graphs
Nils Kriege, Florian Kurpicz, Petra Mutzel
Proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), LNCS 8986, Springer, 200-212
Other Publications and Preprints
- Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, Ian Munro, Eva Rotenberg