Publications Markus Lohrey
Submitted papers
- Average case analysis of leaf-centric binary tree sources (with Louisa Seelbach and Stephan Wagner)
- 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
- Membership problems in infinite
groups
Proceedings of CiE 2024, LNCS 14773, pp. 44-59
© Springer - Compression techniques in group
theory
Proceedings of CiE 2021, LNCS 12813, pp. 330-341
© Springer - Balancing straight-line programs for strings
and trees
Proceedings of CiE 2020, LNCS 12098, pp. 296-300
© Springer - Sliding window algorithms for regular
languages (with Moses Ganardi
and Danny
Hucke)
Proceedings of LATA 2018, LNCS 10792, pp. 26-35
© Springer - Grammar-based tree
compression
Proceedings of DLT 2015, LNCS 9168, pp. 46-57
© Springer - Equality testing of
compressed strings
Proceedings of WORDS 2015, LNCS 9304, pp. 14-26
© Springer - 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 - 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
- Parameterized complexity of factorization problems (with
Andreas Rosowski)
to appear in Discrete Mathematics and Theoretical Computer Science - Membership problems in finite
groups (with
Andreas Rosowski and Georg Zetzsche)
Journal of Algebra 675, pp. 23-58, 2025
© Elsevier - 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 - Compressed decision problems in hyperbolic
groups (with
Derek Holt and Saul
Schleimer)
Groups, Geometry, and Dynamics 18(4), pp. 1233-1273, 2024
© EMS Press - 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 - 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 - Subgroup membership in GL(2,Z)
Theory of Computing Systems 2023 (special issue for STACS 2021)
© Springer - Complexity of
word problems for HNN-extensions
Journal of Computer and System Sciences 135, pp. 145-157, 2023 (special issue for FCT 2021)
© Elsevier - Exponent
equations in HNN-extensions (with Michael
Figelius)
Journal of Groups, Complexity, Cryptology 14(2), 2022
online version at EPIsciences - 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 - 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 - Closure properties of knapsack semilinear
groups (with Michael
Figelius and Georg
Zetzsche)
Journal of Algebra 589(1), pp. 437-482, 2022
© Elsevier - Balancing
straight-line programs (with Moses Ganardi
and Artur
Jez)
Journal of the ACM 68(4), Article No. 27, 2021
© ACM - 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 - 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 - 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 - 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 - 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 - 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 - Knapsack in hyperbolic groups
Journal of Algebra 545, pp. 390-415, 2020
© Elsevier - Size-optimal top dag
compression (with
Carl Philipp Reh and Kurt
Sieber)
Information Processing Letters 147, pp. 27-31, 2019
© Elsevier - 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 - A universal
tree balancing theorem (with Moses Ganardi)
ACM Transactions on Computation Theory 11(1), Article No. 1, 2018
© ACM - 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 - 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 - 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 - Knapsack in graph
groups (with Georg Zetzsche)
Theory of Computing Systems 62(1), pp. 192-246, 2018 (special issue for STACS 2016)
© Springer - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Approximation of smallest linear tree
grammars (with Artur Jez)
Information and Computation 251, pp. 215-251, 2016
© Elsevier - 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 - Satisfiability of ECTL* with
constraints (with Claudia
Carapelle and Alexander
Kartzow)
Journal of Computer and System Sciences 82(5), pp. 826-855, 2016
© Elsevier - 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 -
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 -
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 - Rational subsets of
unitriangular groups
International Journal of Algebra and Computation 25(1-2), pp. 113-121 2015
© World Scientific -
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 - 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 -
XML tree structure
compression using RePair (with Sebastian
Maneth and
Roy Mennicke)
Information Systems 38(8), pp. 1150-1167, 2013
© Elsevier -
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 - 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 -
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 -
Isomorphism of regular
trees and words (with Christian
Mathissen)
Information and Computation 224, pp. 71-105, 2013
© Elsevier -
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 -
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 - Algorithmics on
SLP-compressed strings: a survey
Groups Complexity Cryptology 4(2), pp. 241-299, 2012
© De Gruyter -
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 - 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 - Model-checking hierarchical
structures
Journal of Computer and System Sciences 78(2), pp. 461-490, 2012
© Elsevier -
Automatic structures of
bounded degree revisited (with
Dietrich Kuske)
Journal of Symbolic Logic 76(4), pp. 1352-1380, 2011
© Cambridge University Press - Compressed word problems in
HNN-extensions and amalgamated products (with
Niko
Haubold)
Theory of Computing Systems 49(2), pp. 283-305, 2011
© Springer -
Leaf languages and string
compression
Information and Computation 209(6), pp. 951-965, 2011
© Elsevier - Tilings and submonoids
of metabelian groups (with Benjamin
Steinberg)
Theory of Computing Systems 48(2), pp. 411-427, 2011
© Springer - Fixpoint logics on hierarchical
structures (with Stefan
Göller)
Theory of Computing Systems 48(1), pp. 93-131, 2011
© Springer - Compressed membership
problems for regular expressions and hierarchical
automata
International Journal of Foundations of Computer Science 21(5), pp. 817-841, 2010
© World Scientific - Submonoids and rational
subsets of groups with infinitely many ends
(with Benjamin
Steinberg)
Journal of Algebra 324(5), pp. 970-983, 2010
© Elsevier -
Some natural
decision problems in automatic graphs (with
Dietrich Kuske)
Journal of Symbolic Logic 75(2), pp. 678-710, 2010
© Cambridge University Press - 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 -
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 - Partially commutative inverse
monoids (with Volker
Diekert and Alexander Miller)
Semigroup Forum 77(2), pp. 196-226, 2008
© Springer - Word equations over graph
products (with Volker
Diekert)
International Journal of Algebra and Computation 18(3), pp. 493-533, 2008
© World Scientific - The
submonoid and rational subset membership problems for graph
groups (with Benjamin
Steinberg)
Journal of Algebra 320(2), pp. 728-755, 2008
© Elsevier -
Efficient Memory
Representation of XML Document Trees (with
Giorgio Busatto and Sebastian
Maneth)
Information Systems 33(4-5), pp. 456-474, 2008
© Elsevier - 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 - 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 - 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 - Inverse
monoids: decidability and complexity of algebraic
questions (with Nicole Ondrusch)
Information and Computation 205(8), pp. 1212-1234, 2007
© Elsevier - 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 - 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 - 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 - Word
problems and membership problems on compressed
words
SIAM Journal on Computing 35(5), pp. 1210-1240, 2006
© SIAM -
Axiomatising
divergence (with Pedro D'Argenio
and Holger
Hermanns)
Information and Computation 203(2), pp. 115-144, 2005
© Elsevier - 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 - Complexity results for
prefix grammars (with
Holger Petersen)
RAIRO - Theoretical Informatics and Applications 39(2), pp. 389-399, 2005
© EDP Sciences - 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 - 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 -
Bounded MSC
communication (with Anca Muscholl)
Information and Computation 189(2), pp. 160-181, 2004
© Elsevier - 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 -
Realizability of high-level
message sequence charts: closing the gaps
Theoretical Computer Science 309(1-3), pp. 529-554, 2003
© Elsevier - 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 - Confluence problems for
trace rewriting
Information and Computation 170, pp. 1-25, 2001
© Elsevier - 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
- FO-query enumeration over SLP-compressed structures of bounded degree (with Sebastian Manet and Markus Schmid)
Proceedings of MFCS 2025
online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version - Finding cycle types in permutation groups with few generators (with
Andreas Rosowski)
Proceedings of COCOON 2025, LNCS 15984, pp.367-380
© Springer - 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 - 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 - 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 - 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 - 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 - 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 - Exponent equations in
HNN-extensions (with Michael
Figelius)
Proceedings of ISSAC 2022, pp. 293-301
© ACM arxiv version journal version - Complexity of word problems for
HNN-extensions
Proceedings of FCT 2021, LNCS 12867, pp.371-384
© Springer arxiv version journal version - Subgroup membership
in GL(2,Z)
Proceedings of STACS 2021
online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik journal version - A comparison of
empirical tree entropies (with Danny
Hucke and Louisa
Seelbach)
Proceedings of SPIRE 2020, LNCS 12303, pp. 232-246
© Springer arxiv version - 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 - 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 - 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 - 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 - 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 - The power word problem (with
Armin
Weiß)
Proceedings of MFCS 2019
online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version - 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 - Largest common prefix of a
regular tree languages (with Sebastian
Maneth)
Proceedings of FCT 2019, LNCS 11651, pp. 95-108
© Springer journal version - 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 - 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 - 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 - Knapsack in hyperbolic groups
Proceedings of Reachability Problems 2018, LNCS 11123, pp. 87-102
© Springer arxiv version journal version - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Computing quantiles
in Markov chains with multi-dimensional costs
(with Christoph
Haase and Stefan
Kiefer)
Proceedings of LICS 2017
© IEEE Computer Society Press - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - Evaluating matrix
circuits (with Daniel
König)
Proceedings of COCOON 2015, LNCS 9198, pp. 235-248
© Springer journal version - Compressed tree
canonization (with Sebastian
Maneth and Fabian
Peternek)
Proceedings of ICALP 2015, LNCS 9135, pp. 337-349
© Springer arxiv version - 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 - 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 - Processing succinct
matrices and vectors (with
Manfred Schmidt-Schauß)
Proceedings of CSR 2014, LNCS 8476, pp. 245--258
© Springer arxiv version journal version - 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 - 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 - Satisfiability of CTL*
with constraints (with Claudia
Carapelle and Alexander
Kartzow)
Proceedings of CONCUR 2013, LNCS 8052, pp. 455-469
© Springer journal version - 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 - 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 - XML compression via
DAGs (with Sebastian
Maneth and Eric
Nöth)
Proceedings of ICDT 2013, pp. 69-80
© ACM journal version - 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 - 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 - 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 - 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 - Compressed word problems
for inverse monoids
Proceedings of MFCS 2011, LNCS 6907, pp. 448-459
© Springer long version - Isomorphism of regular
trees and words (with Christian
Mathissen)
Proceedings of ICALP 2011, LNCS 6756, pp. 210-221
© Springer journal version - Compressed
membership in automata with compressed labels
(with Christian
Mathissen)
Proceedings of CSR 2011, LNCS 6651, pp. 275-288
© Springer - 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 - 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 - 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) - 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 - 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 - Automatic structures of
bounded degree revisited (with
Dietrich Kuske)
Proceedings of CSL 2009, LNCS 5771, pp. 364-378
© Springer journal version - Compressed word problems
in HNN-extensions and amalgamated products
(with Niko
Haubold)
Proceedings of CSR 2009, LNCS 5675, pp. 237-249
© Springer journal version - 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 - Leaf languages and
string compression
Proceedings of FSTTCS 2008, pp. 292-303
online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik journal version - 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) - 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) - Efficient computation in
groups via compression (with Saul Schleimer)
Proceedings of CSR 2007, LNCS 4649, pp. 249-258
© Springer long version - The submonoid and rational
subset membership problems for graph groups
(with Benjamin
Steinberg)
Proceedings of LATA 2007, pp. 367-378
journal version - 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) - 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 - Partially commutative
inverse monoids (with Volker
Diekert and Alexander Miller)
Proceedings of MFCS 2006, LNCS 4162, pp. 292-304
© Springer journal version - Querying and embedding
compressed texts (with Yury Lifshits)
Proceedings of MFCS 2006, LNCS 4162, pp. 681-692
© Springer - Monadic chain logic over
iterations and applications to pushdown
systems (with
Dietrich Kuske)
Proceedings of LICS 2006, pp. 91-100
© IEEE Computer Society Press - Theories of
HNN-extensions and amalgamated products (with
Géraud
Sénizergues)
Proceedings of ICALP 2006, LNCS 4052, pp. 504-515
© Springer - First-order and counting
theories of omega-automatic structures (with
Dietrich Kuske)
Proceedings of FOSSACS 2006, LNCS 3921, pp. 322-336
© Springer journal version - Fixpoint logics on
hierarchical structures (with Stefan
Göller)
Proceedings of FSTTCS 2005, LNCS 3821, pp. 483-494
© Springer technical report journal version - 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) - Efficient memory
representation of XML documents (with Giorgio
Busatto and Sebastian
Maneth)
Proceedings of DBPL 2005, LNCS 3774, pp. 199-216
© Springer journal version - Inverse monoids:
decidability and complexity of algebraic
questions (with Nicole Ondrusch)
Proceedings of MFCS 2005, LNCS 3618, pp. 664-675
© Springer journal version - Model-checking
hierarchical structures
Proceedings of LICS 2005, pp. 168-177
© IEEE Computer Society Press journal version - Decidability and
complexity in automatic monoids
Proceedings of DLT 2004, LNCS 3340, pp. 308-320
© Springer journal version - 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) - Word equations over
graph products (with Volker
Diekert)
Proceedings of FSTTCS 2003, LNCS 2914, pp. 156-167
© Springer journal version - Automatic structures of
bounded degree
Proceedings of LPAR 2003, LNAI 2850, pp. 344-358
© Springer - 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) - 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) - 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) - Axiomatising
divergence (with Pedro D'Argenio
and Holger
Hermanns)
Proceedings of ICALP 2002, LNCS 2380, pp. 585-596, 2002
© Springer journal version - Bounded MSC
communication (with Anca Muscholl)
Proceedings of FOSSACS 2002, LNCS 2303, pp. 295-309, 2002
© Springer journal version - 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 - Word problems for
2-homogeneous monoids and symmetric logspace
Proceedings of MFCS 2001, LNCS 2136, pp. 500-511, 2001
© Springer - On the parallel complexity
of tree automata
Proceedings of RTA 2001, LNCS 2051, pp. 201-216, 2001
© Springer - 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 - Word problems and
confluence problems for restricted semi-Thue
systems
Proceedings of RTA 2000, LNCS 1833, pp. 172-186, 2000
© Springer - Complexity results for
confluence problems
Proceedings of MFCS 99, LNCS 1672, pp. 114-124, 1999
© Springer long version - On the confluence of
trace rewriting systems
Proceedings of FSTTCS 98, LNCS 1530, pp. 319-330, 1998
© Springer long version - 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
- Equations in
HNN-extensions
(with Géraud Sénizergues) - Positive theories of
HNN-extensions and amalgamated free products
(with Géraud Sénizergues) - Computational aspects of
infinite monoids
Habilitation thesis, Stuttgart, 2003 - Das Konfluenzproblem für
Spurersetzungssysteme (in German)
PhD thesis, Stuttgart, 1999
Impressum