This is an old revision of the document!
Publications (Group Members in Bold)
Peer Reviewed Publications
2023
- Lyndon Arrays in Sublinear Time
Hideo Bannai, Jonas Ellert
Accepted at ESA 2023 - Ein Roboter lernt laufen: Vermittlung von Konzepten des verstärkenden Lernens im Informatikunterricht
Jan Laumeyer, Jan Hendrik Krone, Johannes Fischer
Accepted at INFOS'23. - Sliding Window String Indexing in Streams
Philip Bille, Johannes Fischer, Inge Li Gørtz, Max Rishøj Pedersen, Tord Joakim Stordalen
Proc. CPM 2023, 4:1–4:18, Best Student Paper Award. - Bit-Parallel (Compressed) Wavelet Tree Construction
Patrick Dinklage, Johannes Fischer, Florian Kurpicz, Jan-Philipp Tarnowski
Proc. DCC 2023, 81-90. - Optimal Square Detection Over General Alphabets
Jonas Ellert, Paweł Gawrychowski, Garance Gourdel
Proc. SODA 2023, 5220–5242.
2022
- LIVE-Interaktion statt Videomaterial bei der Sensibilisierung für Inklusion und Computerzugänglichkeit! - Im E-Lecture fragen Studierende einen blinden Betroffenen
Kensuke Akao
Proc. DELFI 2022, LNI P-322, 189-194. - A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs
Nico Bertram, Jonas Ellert, Johannes Fischer
Proc. SEA 2022, 10.1-10.15 - Back-to-Front Online Lyndon Forest Construction
Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert and Cyril Nicaud
Proc. CPM 2022, LIPIcs 223, 13:1–13:23
2021
- Engineering Practical Lempel-Ziv Tries
Diego Arroyuelo, Rodrigo Canovas, Johannes Fischer, Dominik Köppl, Marvin Löbel, Gonzalo Navarro, Rajeev Raman
ACM J. Exp. Algor. 26, Article No.: 1.14, pp 1-47. - Wie können wir Lehramtsstudierende auf einen inklusiven Informatikunterricht vorbereiten?
Kensuke Akao, Johannes Fischer
Proc. HDI 2021, 75-83. - Lyndon Words Accelerate Suffix Sorting
Nico Bertram, Jonas Ellert, Johannes Fischer
Proc. ESA 2021, LIPIcs 204, 15:1–15:13. - Practical Wavelet Tree Construction
Patrick Dinklage, Jonas Ellert, Johannes Fischer, Florian Kurpicz, Marvin Löbel
ACM J. Exp. Algor. 26(1), Article No.: 1.8, pp 1–67. - Reflexionsförderung bei Lehramtsstudierenden durch den Einsatz von videobasierten Aufgaben
Johannes Fischer, Martin Weinert
INFOS'21, 261-270. - Zum Stand der Lehramtsausbildung für einen inklusiven Informatikunterricht
Kensuke Akao, Johannes Fischer
INFOS'21, 291-294. - Engineering Predecessor Data Structures for Dynamic Integer Sets
Patrick Dinklage, Johannes Fischer, Alexander Herlez
Proceeding of the 19th International Symposium on Experimental Algorithms (SEA 2021), LIPIcs 190, 7:1–7:19. (arXiv version) - Linear Time Runs Over General Ordered Alphabets
Jonas Ellert, Johannes Fischer
Proc. ICALP 2021, LIPIcs 198, 63:1–63:16. (video presentation on YouTube)
2020
- Fostering Reflection in CS Teacher Education
Johannes Fischer, Nora Romahn, Martin Weinert
ISSEP (CEURWS Volume) 2020: 128-139. - To Project or Not to Project: In Search of the Pathway to Object Orientation
Johannes Fischer, Arno Pasternak
ISSEP (CEURWS Volume) 2020: 31-42 - Practical Performance of Space Efficient Data Structures for Longest Common Extensions
Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, Florian Kurpicz
Proc. ESA, LIPICS 173, Article No. 39; pp. 39:1–39:20. - Deterministic Sparse Suffix Sorting in the Restore Model
Johannes Fischer, Tomohiro I, Dominik Köppl
ACM Transactions on Algorithms 16(4), 50.1-50.53. - LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
Proc. Euro-Par, LNCS 12247, 329–342. (video presentation on YouTube) - 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
Proc. ICALP 2020, LIPIcs 168, 14:1-14.18. (video presentation on TIB) - 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.
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
- Scalable Text Index Construction
Timo Bingmann, Patrick Dinklage, Johannes Fischer, Florian Kurpicz, Enno Ohlebusch, Peter Sanders
Algorithms for Big Data 2022: 252-284 - Videobasierte Aufgaben im Studium des Informatiklehramts
Martin Weinert, Johannes Fischer
Poster, Lehren und Forschen mit Videos in der Lehrkräftebildung, 2021 - Wie läuft die Umsetzung inklusiven Informatikunterrichts tatsächlich? Eine Lehrerumfrage zum inklusionsorienterten Unterricht.
Kensuke Akao, Johannes Fischer
9. Münsteraner Workshop für Schulinformatik 2020, 9-18. ISBN 9783751935555. - Informatik für alle: 18. GI-Fachtagung Informatik und Schule
Arno Pasternak (Hrsg.)
Lecture Notes in Informatics 288, Gesellschaft für Informatik, 2019. - Compressed Range Minimum Queries
Johannes Fischer
In Ming-Yang Kao (ed.): Encyclopedia of Algorithms (2nd edition), 379-382, Springer.