Publications Markus Lohrey

 

Submitted papers

 

1. Average case analysis of leaf-centric binary tree sources (with Louisa Seelbach and Stephan Wagner)
2. Streaming word problems (with Lukas Lück and Julio Xochitemol)

 

Books and book chapters

 

1.

The compressed word problem for groups SpringerBriefs in Mathematics, 2014

2.

Complexity and Randomness in Group Theory (with Frédérique Bassino, Ilya Kapovich, Alexei Miasnikov, Cyril Nicaud, Andrey Nikolaev, Igor Rivin, Vladimir Shpilrain, Alexander Ushakov and Pascal Weil) De Gruyter, 2020

3.

Parallel Complexity in Group Theory (in Languages and Automata, GAGTA Book 3, edited by Benjamin Steinberg) De Gruyter, 2024

 

 

Invited papers

 

1. Membership problems in infinite groups
   Proceedings of CiE 2024, LNCS 14773, pp. 44-59
   © Springer
2. Compression techniques in group theory
   Proceedings of CiE 2021, LNCS 12813, pp. 330-341
   © Springer
3. Balancing straight-line programs for strings and trees
   Proceedings of CiE 2020, LNCS 12098, pp. 296-300
   © Springer
4. Sliding window algorithms for regular languages (with Moses Ganardi and Danny Hucke)
   Proceedings of LATA 2018, LNCS 10792, pp. 26-35
   © Springer
5. Grammar-based tree compression
   Proceedings of DLT 2015, LNCS 9168, pp. 46-57
   © Springer
6. Equality testing of compressed strings
   Proceedings of WORDS 2015, LNCS 9304, pp. 14-26
   © Springer
7. Temporal logics with local constraints (with Claudia Carapelle)
   Proceedings of CSL 2015, pp. 2-13
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
8. The rational subset membership problem for groups: a survey
   Proceedings of Groups St Andrews 2013, London Mathematical Society Lecture Note Series 422, pp. 368-389
   © Cambridge University Press

 

Journal papers

 

1. Membership problems in finite groups (with Andreas Rosowski and Georg Zetzsche)
   to appear in Journal of Algebra
2. Regular languages in the sliding window model (with Moses Ganardi, Danny Hucke, Konstantinos Mamouras and Tatiana Starikovskaya)
   TheoretiCS, Volume 4, 2025
   online version at EPIsciences
3. Compressed decision problems in hyperbolic groups (with Derek Holt and Saul Schleimer)
   Groups, Geometry, and Dynamics 18(4), pp. 1233-1273, 2024
   © EMS Press
4. The power word problem in graph products (with Florian Stober and Armin Weiß)
   Theory of Computing Systems 68, pp. 403-464, 2024 (special issue for DLT 2022)
   © Springer
5. Knapsack and the power word problem in solvable Baumslag-Solitar groups (with Moses Ganardi and Georg Zetzsche)
   International Journal of Algebra and Computation 33(3), pp. 617-639, 2023
   © World Scientific
6. Subgroup membership in GL(2,Z)
   Theory of Computing Systems 2023 (special issue for STACS 2021)
   © Springer
7. Complexity of word problems for HNN-extensions
   Journal of Computer and System Sciences 135, pp. 145-157, 2023 (special issue for FCT 2021)
   © Elsevier
8. Exponent equations in HNN-extensions (with Michael Figelius)
   Journal of Groups, Complexity, Cryptology 14(2), 2022
   online version at EPIsciences
9. Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems (with Laurent Bartholdi, Michael Figelius and Armin Weiß)
   ACM Transactions on Computation Theory 14 (3-4), 2022
   © ACM
10. Entropy bounds for grammar-based tree compressors (with Danny Hucke and Louisa Seelbach)
    IEEE Transactions on Information Theory 67(11), pp. 7596-7615, 2021
    © IEEE Computer Society Press
11. Closure properties of knapsack semilinear groups (with Michael Figelius and Georg Zetzsche)
    Journal of Algebra 589(1), pp. 437-482, 2022
    © Elsevier
12. Balancing straight-line programs (with Moses Ganardi and Artur Jez)
    Journal of the ACM 68(4), Article No. 27, 2021
    © ACM
13. The smallest grammar problem revisited  (with Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jez and Carl Philipp Reh)
    IEEE Transactions on Information Theory 67(1), pp. 317-328, 2021
    © IEEE Computer Society Press
14. Largest common prefix of a regular tree language (with Sebastian Maneth)
    Journal of Computer and System Sciences 115, pp. 235-245, 2021 (special issue for FCT 2019)
    © Elsevier
15. Derandomization for sliding window algorithms with strict correctness (with Moses Ganardi and Danny Hucke)
    Theory of Computing Systems 65, pp. 1-18, 2021(special issue for CSR 2019)
    © Springer
16. Combined compression of multiple correlated data streams for online-diagnosis systems (with Simon Meckel, Seungbum Jo, Roman Obermaisser and Simon Plasger)
    Microprocessors and Microsystems 77, 2020 (special issue for Euromicro DSD 2019)
    © Elsevier
17. Grammar-based compression of unranked trees (with Adria Gascon, Sebastian Maneth, Carl Philipp Reh and Kurt Sieber)
    Theory of Computing Systems 61(1), pp. 141-176, 2020 (special issue for CSR 2018)
    © Springer
18. Universal tree source coding using grammar-based compression (with Moses Ganardi, Danny Hucke and Louisa Seelbach)
    IEEE Transactions on Information Theory 65(10), pp. 6399-6413, 2019
    © IEEE Computer Society Press
19. Knapsack in hyperbolic groups
    Journal of Algebra 545, pp. 390-415, 2020
    © Elsevier
20. Size-optimal top dag compression (with Carl Philipp Reh and Kurt Sieber)
    Information Processing Letters 147, pp. 27-31, 2019
    © Elsevier
21. The complexity of bisimulation and simulation on finite systems (with Moses Ganardi and Stefan Göller)
    Logical Methods in Computer Science 14(4), 2018
    online version
22. A universal tree balancing theorem (with Moses Ganardi)
    ACM Transactions on Computation Theory 11(1), Article No. 1, 2018
    © ACM
23. Parallel identity testing for skew circuits with big powers and applications (with Daniel König)
    International Journal of Algebra and Computation 28(6), pp. 979-1004, 2018
    © World Scientific
24. An architecture for online-diagnosis systems supporting compressed communication (with Seungbum Jo, Damian Ludwig, Simon Meckel, Roman Obermaisser and Simon Plasger)
    Microprocessors and Microsystems 61, pp. 242-256, 2018 (special issue for Euromicro DSD 2017)
    © Elsevier
25. Circuits and expressions over finite semirings (with Moses Ganardi, Danny Hucke and Daniel König)
    ACM Transactions on Computation Theory 10(4), Article No. 15, 2018
    © ACM
26. Knapsack in graph groups (with Georg Zetzsche)
    Theory of Computing Systems 62(1), pp. 192-246, 2018 (special issue for STACS 2016)
    © Springer
27. Path checking for MTL and TPTL over data words (with Shiguang Feng and Karin Quaas)
    Logical Methods in Computer Science 13(3), 2017
    online version
28. Evaluation of circuits over nilpotent and polycyclic groups (with Daniel König)
    Algorithmica 80(5), pp. 1459-1492, 2018 (special issue for COCOON 2015)
    © Springer
29. Constant-time tree traversal and subtree equality check for grammar-compressed trees (with Sebastian Maneth and Carl Philipp Reh)
    Algorithmica 80(7), pp. 2082-–2105, 2018 (special issue for DCC 2016)
    © Springer
30. Tree compression using string grammars (with Moses Ganardi, Danny Hucke and Eric Nöth)
    Algorithmica 80(3), pp. 885-917, 2018 (special issue for LATIN 2016)
    © Springer
31. Constructing small tree grammars and small circuits for formulas (with Danny Hucke, Artur Jez, Moses Ganardi and Eric Nöth)
    Journal of Computer and System Sciences 86, pp. 136-158, 2017
    © Elsevier
32. Satisfiability of ECTL* with local tree constraints (with Claudia Carapelle, Shiguang Feng and Alexander Kartzow)
    Theory of Computing Systems 61(2), pp. 689-720, 2017 (special issue for CSR 2015)
    © Springer
33. Processing succinct matrices and vectors (with Manfred Schmidt-Schauß)
    Theory of Computing Systems 61(2), pp. 322-351, 2017 (special issue for CSR 2014)
    © Springer
34. Approximation of smallest linear tree grammars (with Artur Jez)
    Information and Computation 251, pp. 215-251, 2016
    © Elsevier
35. On Boolean closed full trios and rational Kripke frames  (with  Dietrich Kuske and Georg Zetzsche)
    Theory of Computing Systems 60(3), pp. 438-472, 2017 (special issue for STACS 2014)
    © Springer
36. Satisfiability of ECTL* with constraints (with Claudia Carapelle and Alexander Kartzow)
    Journal of Computer and System Sciences 82(5), pp. 826-855, 2016
    © Elsevier
37. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups (with Daniel König and Georg Zetzsche)
    Contemporary Mathematics 677 (Algebra and Computer Science), pp. 129-144, 2016
    © AMS Press
38. Rational subsets and submonoids of wreath products (with Benjamin Steinberg and Georg Zetzsche)
    Information and Computation 243, pp. 191-204, 2015 (special issue for ICALP 2013)
    © Elsevier
39. The complexity of decomposing modal and first-order theories (with Stefan Göller and Jean Christoph Jung)
    ACM Transactions on Computational Logic 16(1), Article No. 9, 2015
    © ACM
40. Rational subsets of unitriangular groups
    International Journal of Algebra and Computation 25(1-2), pp. 113-121 2015
    © World Scientific
41. XML compression via DAGs (with Mireille Bousquet-Mélou, Sebastian Maneth and Eric Nöth)
    Theory of Computing Systems 57(4), pp. 1322-1371, 2015 (special issue for ICDT 2013)
    © Springer
42. The first-order theory of ground tree rewrite graphs (with Stefan Göller)
    Logical Methods in Computer Science 10(1), paper 7, 2014
    online version
43. XML tree structure compression using RePair (with Sebastian Maneth and Roy Mennicke)
    Information Systems 38(8), pp. 1150-1167, 2013
    © Elsevier
44. The isomorphism problem on classes of automatic structures with transitive relations (with Dietrich Kuske and Jiamou Liu)
    Transactions of the American Mathematical Society 365, pp. 5103-5151, 2013
    © AMS Press
45. Tree-automatic well-founded trees (with Martin Huschenbett, Alexander Kartzow, and Jiamou Liu)
    Logical Methods in Computer Science 9(2), paper 10, 2013
    online version
46. Branching-time model checking of one-counter processes and timed automata (with Stefan Göller)
    SIAM Journal on Computing 42(3), pp. 884-923, 2013
    © SIAM
47. Isomorphism of regular trees and words (with Christian Mathissen)
    Information and Computation 224, pp. 71-105, 2013
    © Elsevier
48. Compressed decision problems for graph products of groups and applications to (outer) automorphism groups (with Niko Haubold and Christian Mathissen)
    International Journal of Algebra and Computation 22(8), 2013
    © World Scientific
49. The isomorphism problem for omega-automatic trees (with Dietrich Kuske and Jiamou Liu)
    Annals of Pure and Applied Logic 164(1), pp. 30-48, 2013
    © Elsevier
50. Algorithmics on SLP-compressed strings: a survey
    Groups Complexity Cryptology 4(2), pp. 241-299, 2012
    © De Gruyter
51. Logspace computations in Coxeter groups and graph groups (with Volker Diekert and Jonathan Kausch)
    Contemporary Mathematics 582 (Computational and Combinatorial Group Theory and Cryptography), pp. 77-94, 2012
    © AMS Press
52. Parameter reduction and automata evaluation for grammar-compressed trees (with Sebastian Maneth and Manfred Schmidt-Schauß)
    Journal of Computer and System Sciences 78(5), pp. 1651-1669, 2012
    © Elsevier
53. Model-checking hierarchical structures
    Journal of Computer and System Sciences 78(2), pp. 461-490, 2012
    © Elsevier
54. Automatic structures of bounded degree revisited (with Dietrich Kuske)
    Journal of Symbolic Logic 76(4), pp. 1352-1380, 2011
    © Cambridge University Press
55. Compressed word problems in HNN-extensions and amalgamated products (with Niko Haubold)
    Theory of Computing Systems 49(2), pp. 283-305, 2011
    © Springer
56. Leaf languages and string compression
    Information and Computation 209(6), pp. 951-965, 2011
    © Elsevier
57. Tilings and submonoids of metabelian groups (with Benjamin Steinberg)
    Theory of Computing Systems 48(2), pp. 411-427, 2011
    © Springer
58. Fixpoint logics on hierarchical structures (with Stefan Göller)
    Theory of Computing Systems 48(1), pp. 93-131, 2011
    © Springer
59. Compressed membership problems for regular expressions and hierarchical automata
    International Journal of Foundations of Computer Science 21(5), pp. 817-841, 2010
    © World Scientific
60. Submonoids and rational subsets of groups with infinitely many ends (with Benjamin Steinberg)
    Journal of Algebra 324(5), pp. 970-983, 2010
    © Elsevier
61. Some natural decision problems in automatic graphs (with Dietrich Kuske)
    Journal of Symbolic Logic 75(2), pp. 678-710, 2010
    © Cambridge University Press
62. An automata theoretic approach to the generalized word problem in graphs of groups (with Benjamin Steinberg)
    Proceedings of the AMS 138, pp. 445-453, 2010
    © AMS Press
63. PDL with intersection and converse: satisfiability and infinite-state model checking (with Stefan Göller and Carsten Lutz)
    Journal of Symbolic Logic 74(1), pp. 279-314, 2009
    © Cambridge University Press
64. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller)
    Semigroup Forum 77(2), pp. 196-226, 2008
    © Springer
65. Word equations over graph products (with Volker Diekert)
    International Journal of Algebra and Computation 18(3), pp. 493-533, 2008
    © World Scientific
66. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg)
    Journal of Algebra 320(2), pp. 728-755, 2008
    © Elsevier
67. Efficient Memory Representation of XML Document Trees (with Giorgio Busatto and Sebastian Maneth)
    Information Systems 33(4-5), pp. 456-474, 2008
    © Elsevier
68. Algorithmic problems on inverse monoids over virtually-free groups (with Volker Diekert and Nicole Ondrusch)
    International Journal of Algebra and Computation 18(1), pp. 181-208, 2008
    © World Scientific
69. Rational subsets of HNN-extensions and amalgamated free products (with Géraud Sénizergues)
    International Journal of Algebra and Computation 18(1), pp. 111-163, 2008
    © World Scientific
70. First-order and counting theories of omega-automatic structures (with Dietrich Kuske)
    Journal of Symbolic Logic 73(1), pp. 129-150, 2008
    © Cambridge University Press
71. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch)
    Information and Computation 205(8), pp. 1212-1234, 2007
    © Elsevier
72. When is a graph product of groups virtually-free? (with Géraud Sénizergues)
    Communications in Algebra 35(2), pp. 617-621, 2007
    © Taylor & Francis
73. The complexity of tree automata and XPath on grammar-compressed trees (with Sebastian Maneth)
    Theoretical Computer Science 363(2), pp. 196-210, 2006 (special issue for CIAA 2005)
    © Elsevier
74. Logical aspects of Cayley-graphs: The monoid case (with Dietrich Kuske)
    International Journal of Algebra and Computation 16(2), pp. 307-340, 2006
    © World Scientific
75. Word problems and membership problems on compressed words
    SIAM Journal on Computing 35(5), pp. 1210-1240, 2006
    © SIAM
76. Axiomatising divergence (with Pedro D'Argenio and Holger Hermanns)
    Information and Computation 203(2), pp. 115-144, 2005
    © Elsevier
77. Decidability and complexity in automatic monoids
    International Journal of Foundations of Computer Science 16(4), pp. 707-722, 2005 (special issue for DLT 2004)
    © World Scientific
78. Complexity results for prefix grammars (with Holger Petersen)
    RAIRO - Theoretical Informatics and Applications 39(2), pp. 389-399, 2005
    © EDP Sciences
79. Decidable first-order theories of one-step rewriting in trace monoids (with Dietrich Kuske)
    Theory of Computing Systems 38(1), pp. 38-81, 2005
    © Springer
80. Logical aspects of Cayley-graphs: The group case (with Dietrich Kuske)
    Annals of Pure and Applied Logic 131(1-3), pp. 263-286, 2005
    © Elsevier
81. Bounded MSC communication (with Anca Muscholl)
    Information and Computation 189(2), pp. 160-181, 2004
    © Elsevier
82. Existential and positive theories of equations in graph products (with Volker Diekert)
    Theory of Computing Systems 37(1), pp. 133-156, 2004 (special issue for STACS 2002)
    © Springer
83. Realizability of high-level message sequence charts: closing the gaps
    Theoretical Computer Science 309(1-3), pp. 529-554, 2003
    © Elsevier
84. A note on the existential theory of equations in plain groups (with Volker Diekert)
    International Journal of Algebra and Computation 12, pp. 1-7, 2002
    © World Scientific
85. Confluence problems for trace rewriting
    Information and Computation 170, pp. 1-25, 2001
    © Elsevier
86. NP-completeness results concerning the transformation of logic programs into attribute grammars
    Acta Cybernetica 13(3), pp. 209-224, 1998
    © Institute of Informatics, University of Szeged

 

Conference papers

 

1. Streaming in graph products (with Julio Xochitemol)
   Proceedings of MFCS 2024
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
2. Enumeration for MSO-queries on compressed trees (with Markus Schmid)
   Proceedings of the ACM on Management of Data, Volume 2, Issue 2 (Proceedings of PODS 2024)
   © ACM   arxiv version
3. On the complexity of diameter and related problems in permutation groups (with Andreas Rosowski)
   Proceedings of ICALP 2023
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
4. Low-latency sliding window algorithms for formal languages (with Moses Ganardi, Louis Jachiet and Thomas Schwentick)
   Proceedings of FSTTCS 2022
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
5. Membership problems in finite groups (with Andreas Rosowski and Georg Zetzsche)
   Proceedings of MFCS 2022
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
6. Streaming word problems (with Lukas Lück)
   Proceedings of MFCS 2022
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
7. Exponent equations in HNN-extensions (with Michael Figelius)
   Proceedings of ISSAC 2022, pp. 293-301
   © ACM   arxiv version   journal version
8. Complexity of word problems for HNN-extensions
   Proceedings of FCT 2021, LNCS 12867, pp.371-384
   © Springer   arxiv version   journal version
9. Subgroup membership in GL(2,Z)
   Proceedings of STACS 2021
   online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   journal version
10. A comparison of empirical tree entropies (with Danny Hucke and Louisa Seelbach)
    Proceedings of SPIRE 2020, LNCS 12303, pp. 232-246
    © Springer   arxiv version
11. Knapsack and the power word problem in solvable Baumslag-Solitar groups (with Georg Zetzsche)
    Proceedings of MFCS 2020
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
12. Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems (with Laurent Bartholdi, Michael Figelius and Armin Weiß)
    Proceedings of CCC 2020
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
13. The complexity of knapsack problems in wreath products (with Michael Figelius, Moses Ganardi and Georg Zetzsche)
    Proceedings of ICALP 2020
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
14. Sliding window property testing for regular languages  (with Moses Ganardi, Danny Hucke and Tatiana Starikovskaya)
    Proceedings of ISAAC 2019
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
15. Balancing straight-line programs  (with Moses Ganardi and Artur Jez)
    Proceedings of FOCS 2019, pp. 1169-1183
    © IEEE Computer Society Press   arxiv version   journal version
16. The power word problem (with Armin Weiß)
    Proceedings of MFCS 2019
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
17. Combined compression of multiple correlated data streams for online-diagnosis systems (with Seungbum Jo, Simon Meckel, Roman Obermaisser and Simon Plasger)
    Proceedings of Euromicro DSD 2019, pp. 166-173
    © IEEE Computer Society Press   journal version
18. Largest common prefix of a regular tree languages (with Sebastian Maneth)
    Proceedings of FCT 2019, LNCS 11651, pp. 95-108
    © Springer   journal version
19. Entropy bounds for grammar-based tree compressors (with Danny Hucke and Louisa Seelbach)
    Proceedings of ISIT 2019, pp. 1687-1691
    © IEEE Computer Society Press   arxiv version   journal version
20. Derandomization for sliding window algorithms with strict correctness (with Moses Ganardi and Danny Hucke)
    Proceedings of CSR 2019, LNCS 11532, pp. 237-249
    © Springer   journal version
21. Compressed decision problems in hyperbolic groups (with Derek Holt and Saul Schleimer)
    Proceedings of STACS 2019
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
22. Knapsack in hyperbolic groups
    Proceedings of Reachability Problems 2018, LNCS 11123, pp. 87-102
    © Springer   arxiv version   journal version
23. Average case analysis of leaf-centric binary tree sources (with Louisa Seelbach)
    Proceedings of MFCS 2018
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
24. Sliding windows over context-free languages (with Moses Ganardi and Artur Jez )
    Proceedings of MFCS 2018
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
25. Randomized sliding window algorithms for regular languages (with Moses Ganardi and Danny Hucke)
    Proceedings of ICALP 2018
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
26. Grammar-based compression of unranked trees (with Adria Gascon, Sebastian Maneth, Carl Philipp Reh and Kurt Sieber)
    Proceedings of CSR 2018, LNCS 10846, pp. 118-131
    © Springer   arxiv version   journal version
27. Knapsack problems for wreath products (with Moses Ganardi, Daniel König and Georg Zetzsche)
    Proceedings of STACS 2018
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
28. Automata theory on sliding windows (with Moses Ganardi, Danny Hucke, Daniel König and Konstantinos Mamouras)
    Proceedings of STACS 2018
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
29. Counting problems for Parikh images (with Christoph Haase and Stefan Kiefer)
    Proceedings of MFCS 2017
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
30. An architecture for online-diagnosis systems supporting compressed communication (with Seungbum Jo, Damian Ludwig, Simon Meckel, Roman Obermaisser and Simon Plasger)
    Proceedings of Euromicro DSD 2017, pp. 62-69
    © IEEE Computer Society Press   journal version
31. Universal tree source coding using grammar-based compression (with Danny Hucke)
    Proceedings of IEEE ISIT 2017, pp. 1753-1757
    © IEEE Computer Society Press   arxiv version   journal version
32. Computing quantiles in Markov chains with multi-dimensional costs (with Christoph Haase and Stefan Kiefer)
    Proceedings of LICS 2017
    © IEEE Computer Society Press
33. Circuit evaluation for finite semirings (with Moses Ganardi, Danny Hucke and Daniel König)
    Proceedings of STACS 2017
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version   journal version
34. The complexity of knapsack in graph groups (with Georg Zetzsche)
    Proceedings of STACS 2017
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   arxiv version
35. Compression of unordered XML trees (with Sebastian Maneth and Carl Philipp Reh)
    Proceedings of ICDT 2017
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
36. Querying regular languages over sliding-windows (with Moses Ganardi and Danny Hucke)
    Proceedings of FSTTCS 2016
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
37. The smallest grammar problem revisited (with Danny Hucke and Carl Philipp Reh)
    Proceedings of SPIRE 2016, LNCS 9954, pp. 35-49 (Best paper award)
    © Springer   journal version
38. On the parallel complexity of bisimulation over finite systems (with Moses Ganardi and Stefan Göller)
    Proceedings of CSL 2016
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   journal version
39. Traversing grammar-compressed trees with constant delay (with Sebastian Maneth and Carl Philipp Reh)
    Proceedings of DCC 2016, pp. 546-555
    © IEEE Computer Society Press   arxiv version   journal version
40. Knapsack in graph groups, HNN-extensions and amalgamated products (with Georg Zetzsche)
    Proceedings of STACS 2016
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
    arxiv version
41. Tree compression using string grammars (with Moses Ganardi, Danny Hucke and Eric Nöth)
    Proceedings of LATIN 2016, LNCS 9644, pp. 590-604
    © Springer   arxiv version   journal version
42. Parallel identity testing for skew circuits with big powers and applications (with Daniel König)   
    Proceedings of MFCS 2015, LNCS 9235, pp. 445-458
    © Springer   arxiv version   journal version
43. Path checking for MTL and TPTL over data words  (with Shiguang Feng and Karin Quaas)
    Proceedings of DLT 2015, LNCS 9168, pp. 326-339
    © Springer   arxiv version   journal version
44. Evaluating matrix circuits (with Daniel König)
    Proceedings of COCOON 2015, LNCS 9198, pp. 235-248
    © Springer   journal version
45. Compressed tree canonization (with Sebastian Maneth and Fabian Peternek)   
    Proceedings of ICALP 2015, LNCS 9135, pp. 337-349
    © Springer   arxiv version
46. Satisfiability of ECTL with tree constraints  (with Claudia Carapelle, Alexander Kartzow and Shiguang Feng)
    Proceedings of CSR 2015, LNCS 9139, pp. 94-108
    © Springer   arxiv version   journal version
47. Constructing small tree grammars and small circuits for formulas (with Danny Hucke and Eric Nöth)
    Proceedings of FSTTCS 2014, pp. 457-468
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik    arxiv version   journal version
48. Processing succinct matrices and vectors (with Manfred Schmidt-Schauß)
    Proceedings of CSR 2014, LNCS 8476, pp. 245--258
    © Springer   arxiv version    journal version
49. On Boolean closed full trios and rational Kripke frames (with Georg Zetzsche)
    Proceedings of STACS 2014, pp. 530-541
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
    journal version
50. Approximation of smallest linear tree grammars (with Artur Jez)
    Proceedings of STACS 2014, pp. 445-457
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
    journal version
51. Satisfiability of CTL* with constraints (with Claudia Carapelle and Alexander Kartzow)
    Proceedings of CONCUR 2013, LNCS 8052, pp. 455-469
    © Springer   journal version
52. Rational subsets and submonoids of wreath products (with Benjamin Steinberg and Georg Zetzsche)
    Proceedings of ICALP 2013, LNCS 7966, pp. 361-372
    © Springer   arxiv version    journal version
53. Compression of rewriting systems for termination analysis (with Alexander Bau, Eric Nöth and Johannes Waldmann)
    Proceedings of RTA 2013, pp. 97-112
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik
54. XML compression via DAGs (with Sebastian Maneth and Eric Nöth)
    Proceedings of ICDT 2013, pp. 69-80
    © ACM    journal version
55. The complexity of decomposing modal and first-order theories (with Stefan Göller and Jean Christoph Jung)
    Proceedings of LICS 2012, pp. 325-334
    © IEEE Computer Society Press   journal version
56. Tree-automatic well-founded trees (with Alexander Kartzow and Jiamou Liu)
    Proceedings of CiE 2012, LNCS 7318, pp. 363-373
    © Springer   arxiv version   journal version
57. Logspace computations in graph groups and Coxeter groups (with Volker Diekert and Jonathan Kausch)
    Proceedings of LATIN 2012, LNCS 7256, pp. 243-254
    © Springer   journal version
58. The first-order theory of ground tree rewrite graphs (with Stefan Göller)
    Proceedings of FSTTCS 2011, pp.276-287
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   journal version
59. Compressed word problems for inverse monoids
    Proceedings of MFCS 2011, LNCS 6907, pp. 448-459
    © Springer   long version
60. Isomorphism of regular trees and words (with Christian Mathissen)
    Proceedings of ICALP 2011, LNCS 6756, pp. 210-221
    © Springer   journal version
61. Compressed membership in automata with compressed labels (with Christian Mathissen)
    Proceedings of CSR 2011, LNCS 6651, pp. 275-288
    © Springer
62. Tree structure compression with RePair (with Sebastian Maneth and Roy Mennicke)
    Proceedings of DCC 2011, pp. 353-362
    © IEEE Computer Society Press   journal version   very detailed version
63. The isomorphism problem for omega-automatic trees (with Dietrich Kuske and Jiamou Liu)
    Proceedings of CSL 2010, LNCS 6247, pp. 396-410
    © Springer   journal version
64. Compressed conjugacy and the word problem for outer automorphism groups of graph groups (with Niko Haubold and Christian Mathissen)
    Proceedings of DLT 2010, LNCS 6224, pp. 218-230
    © Springer   journal version ( Compressed decision problems for graph products of groups and applications to (outer) automorphism groups)
65. The isomorphism problem on classes of automatic structures (with Dietrich Kuske and Jiamou Liu)
    Proceedings of LICS 2010, pp. 160-169
    © IEEE Computer Society Press   journal version
66. Branching-time model checking of one-counter processes (with Stefan Göller)
    Proceedings of STACS 2010, pp. 405-416
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   journal version
67. Automatic structures of bounded degree revisited (with Dietrich Kuske)
    Proceedings of CSL 2009, LNCS 5771, pp. 364-378
    © Springer   journal version
68. Compressed word problems in HNN-extensions and amalgamated products (with Niko Haubold)
    Proceedings of CSR 2009, LNCS 5675, pp. 237-249
    © Springer   journal version
69. Parameter reduction in grammar-compressed trees (with Sebastian Maneth and Manfred Schmidt-Schauß)
    Proceedings of FOSSACS 2009, LNCS 5504, pp. 212-226
    © Springer   journal version
70. Leaf languages and string compression
    Proceedings of FSTTCS 2008, pp. 292-303
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik   journal version
71. Euler paths and ends in automatic and recursive graphs (with Dietrich Kuske)
    Proceedings of AFL 2008, pp. 245-256
    journal version (Some natural decision problems in automatic graphs)
72. Hamiltonicity of automatic graphs (with Dietrich Kuske)
    Proceedings of IFIP-TCS 2008, pp. 445-459
    © Springer   journal version (Some natural decision problems in automatic graphs)
73. Efficient computation in groups via compression (with Saul Schleimer)
    Proceedings of CSR 2007, LNCS 4649, pp. 249-258
    © Springer   long version
74. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg)
    Proceedings of LATA 2007, pp. 367-378
    journal version
75. PDL with intersection and converse is 2EXP-complete (with Stefan Göller and Carsten Lutz)
    Proceedings of FOSSACS 2007, LNCS 4423, pp. 198-212
    © Springer   journal version (PDL with intersection and converse: satisfiability and infinite-state model checking)
76. Infinite state model-checking of propositional dynamic logics (with Stefan Göller)
    Proceedings of CSL 2006, LNCS 4207, pp. 349-364
    © Springer   journal version (PDL with intersection and converse: satisfiability and infinite-state model checking)
    technical report
77. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller)
    Proceedings of MFCS 2006, LNCS 4162, pp. 292-304
    © Springer   journal version
78. Querying and embedding compressed texts (with Yury Lifshits)
    Proceedings of MFCS 2006, LNCS 4162, pp. 681-692
    © Springer
79. Monadic chain logic over iterations and applications to pushdown systems (with Dietrich Kuske)
    Proceedings of LICS 2006, pp. 91-100
    © IEEE Computer Society Press
80. Theories of HNN-extensions and amalgamated products (with Géraud Sénizergues)
    Proceedings of ICALP 2006, LNCS 4052, pp. 504-515
    © Springer
81. First-order and counting theories of omega-automatic structures (with Dietrich Kuske)
    Proceedings of FOSSACS 2006, LNCS 3921, pp. 322-336
    © Springer   journal version
82. Fixpoint logics on hierarchical structures (with Stefan Göller)
    Proceedings of FSTTCS 2005, LNCS 3821, pp. 483-494
    © Springer   technical report   journal version
83. Tree Automata and XPath on compressed trees (with Sebastian Maneth)
    Proceedings of CIAA 2005, LNCS 3845, pp. 225-237 (Best paper award)
    © Springer   journal version (The complexity of tree automata and XPath on grammar-compressed trees)
84. Efficient memory representation of XML documents (with Giorgio Busatto and Sebastian Maneth)
    Proceedings of DBPL 2005, LNCS 3774, pp. 199-216
    © Springer   journal version
85. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch)
    Proceedings of MFCS 2005, LNCS 3618, pp. 664-675
    © Springer   journal version
86. Model-checking hierarchical structures
    Proceedings of LICS 2005, pp. 168-177
    © IEEE Computer Society Press   journal version
87. Decidability and complexity in automatic monoids
    Proceedings of DLT 2004, LNCS 3340, pp. 308-320
    © Springer   journal version
88. Word problems on compressed words
    Proceedings of ICALP 2004, LNCS 3142, pp. 906-918
    © Springer   journal version (Word problems and membership problems on compressed words)
89. Word equations over graph products (with Volker Diekert)
    Proceedings of FSTTCS 2003, LNCS 2914, pp. 156-167
    © Springer   journal version
90. Automatic structures of bounded degree
    Proceedings of LPAR 2003, LNAI 2850, pp. 344-358
    © Springer
91. Decidable theories of Cayley-graphs (with Dietrich Kuske)
    Proceedings of STACS 2003, LNCS 2607, pp. 463-474
    © Springer   journal version (group case)   journal version (monoid case)
92. Safe realizability of high-level message sequence charts
    Proceedings of CONCUR 2002, LNCS 2421, pp. 177-192, 2002
    © Springer   journal version (Realizability of high-level message sequence charts: closing the gaps)
93. On the theory of one-step rewriting in trace monoids (with Dietrich Kuske)
    Proceedings of ICALP 2002, LNCS 2380, pp. 752-763, 2002
    © Springer   journal version (Decidable first-order theories of one-step rewriting in trace monoids)
94. Axiomatising divergence (with Pedro D'Argenio and Holger Hermanns)
    Proceedings of ICALP 2002, LNCS 2380, pp. 585-596, 2002
    © Springer   journal version
95. Bounded MSC communication (with Anca Muscholl)
    Proceedings of FOSSACS 2002, LNCS 2303, pp. 295-309, 2002
    © Springer   journal version
96. Existential and positive theories of equations in graph products (with Volker Diekert)
    Proceedings of STACS 2002, LNCS 2285, pp. 501-512, 2002
    © Springer   journal version
97. Word problems for 2-homogeneous monoids and symmetric logspace
    Proceedings of MFCS 2001, LNCS 2136, pp. 500-511, 2001
    © Springer
98. On the parallel complexity of tree automata
    Proceedings of RTA 2001, LNCS 2051, pp. 201-216, 2001
    © Springer
99. Implementing Luby's algorithm on the Cray T3E (with Jürgen Gross)
    High Performance Computing in Science and Engineering, pp. 467-477, Springer 2000
    © Springer
100. Word problems and confluence problems for restricted semi-Thue systems
     Proceedings of RTA 2000, LNCS 1833, pp. 172-186, 2000
     © Springer
101. Complexity results for confluence problems
     Proceedings of MFCS 99, LNCS 1672, pp. 114-124, 1999
     © Springer   long version
102. On the confluence of trace rewriting systems
     Proceedings of FSTTCS 98, LNCS 1530, pp. 319-330, 1998
     © Springer   long version
103. Priority and maximal progress are completely axiomatisable (extended abstract) (with Holger Hermanns)
     Proceedings of CONCUR 98, LNCS 1466, pp. 237-252, 1998
     © Springer   long version

 

Others

 

1. Equations in HNN-extensions
   (with Géraud Sénizergues)
2. Positive theories of HNN-extensions and amalgamated free products
   (with Géraud Sénizergues)
3. Computational aspects of infinite monoids
   Habilitation thesis, Stuttgart, 2003
4. Das Konfluenzproblem für Spurersetzungssysteme (in German)
   PhD thesis, Stuttgart, 1999

---

Impressum