* Optimal Square Detection Over General Alphabets
Jonas Ellert, Paweł Gawrychowski, Garance Gourdel
Accepted at SODA 2023

• Lyndon Arrays Simplified
  Jonas Ellert
  Proc. ESA 2022, LIPIcs 244, 48:1–48:14
• LIVE-Interaktion statt Videomaterial bei der Sensibilisierung für Inklusion und Computerzugänglichkeit! - Im E-Lecture fragen Studierende einen blinden Betroffenen
  Kensuke Akao
  Accepted at DELFI 2022.
• 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

• 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)

• 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.

• 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.

• 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.

• 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.

• Inducing Suffix and LCP Arrays in External Memory

  Timo 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 Space

  Philip 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.

• 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

• 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

• 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.
• Parallel Text Index Construction
  Florian Kurpicz
  PhD-Thesis, 2020.
• Informatik für alle: 18. GI-Fachtagung Informatik und Schule
  Arno Pasternak (Hrsg.)
  Lecture Notes in Informatics 288, Gesellschaft für Informatik, 2019.
• Exploring Regular Structures in Strings
  Dominik Köppl
  PhD-Thesis, 2018.
• Compressed Range Minimum Queries
  Johannes Fischer
  In Ming-Yang Kao (ed.): Encyclopedia of Algorithms (2nd edition), 379-382, Springer.