Publications Markus Lohrey
Submitted papers
 Regular languages in the sliding window model (with Moses Ganardi, Danny Hucke, Konstantinos Mamouras and Tatiana Starikovskaya)
 Entropy bounds for grammarbased tree compressors (with Danny Hucke and Louisa Seelbach)
Books

Invited papers
 Balancing straightline programs for strings and trees
Proceedings of CiE 2020, LNCS 12098, pp. 296300
© Springer  Sliding window algorithms for regular
languages (with Moses
Ganardi and Danny
Hucke)
Proceedings of LATA 2018, LNCS 10792, pp. 2635
© Springer  Grammarbased tree
compression
Proceedings of DLT 2015, LNCS 9168, pp. 4657
© Springer  Equality testing of
compressed strings
Proceedings of WORDS 2015, LNCS 9304, pp. 1426
© Springer  Temporal logics with local
constraints (with Claudia
Carapelle)
Proceedings of CSL 2015, pp. 213
online version at Schloss Dagstuhl LeibnizZentrum 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. 368389
© Cambridge University Press
Journal papers
 Balancing straightline programs (with Moses
Ganardi and Artur Jez)
to appear in Journal of the 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. 317328, 2020
© IEEE Computer Society Press  Largest common prefix of a regular tree language
(with Sebastian Maneth)
Journal of Computer and System Sciences 115, pp. 235245, 2020 (special issue for FCT 2019)
© Elsevier  Derandomization for sliding window algorithms
with strict correctness (with Moses
Ganardi and Danny
Hucke)
to appear in Theory of Computing Systems (special issue for CSR 2019)
© Springer  Combined compression of multiple correlated data streams for onlinediagnosis systems
(with
Simon Meckel, Seungbum Jo,
Roman Obermaisser and Simon Plasger)
Microprocessors and Microsystems 77, 2020 (special issue for Euromicro DSD 2019)
© Elsevier  Grammarbased compression of unranked
trees (with Adria Gascon,
Sebastian
Maneth,
Carl Philipp Reh and Kurt
Sieber)
Theory of Computing Systems 61(1), pp. 141176, 2020 (special issue for CSR 2018)
© Springer  Universal tree source coding using
grammarbased compression (with Moses
Ganardi, Danny
Hucke and Louisa
Seelbach)
IEEE Transactions on Information Theory 65(10), pp. 63996413, 2019
© IEEE Computer Society Press  Knapsack in hyperbolic groups
Journal of Algebra 545, pp. 390415, 2020
© Elsevier  Sizeoptimal top dag
compression (with
Carl Philipp Reh and Kurt
Sieber)
Information Processing Letters 147, pp. 2731, 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. 9791004, 2018
© World Scientific  An architecture
for onlinediagnosis systems supporting compressed
communication (with Seungbum Jo,
Damian Ludwig,
Simon Meckel,
Roman Obermaisser and Simon Plasger)
Microprocessors and Microsystems 61, pp. 242256, 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. 192246, 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. 14591492, 2018 (special issue for COCOON 2015)
© Springer  Traversing grammarcompressed trees
with constant delay (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. 885917, 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. 136158, 2017
© Elsevier  Satisfiability of ECTL* with local tree
constraints (with Claudia
Carapelle,
Shiguang Feng and Alexander
Kartzow)
Theory of Computing Systems 61(2), pp. 689720, 2017 (special issue for CSR 2015)
© Springer  Processing
succinct matrices and vectors (with
Manfred SchmidtSchauß)
Theory of Computing Systems 61(2), pp. 322351, 2017 (special issue for CSR 2014)
© Springer  Approximation of smallest linear tree
grammars (with Artur Jez)
Information and Computation 251, pp. 215251, 2016
© Elsevier  On Boolean closed full trios and rational
Kripke frames (with
Dietrich Kuske and
Georg Zetzsche)
Theory of Computing Systems 60(3), pp. 438472, 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. 826855, 2016
© Elsevier  Knapsack and subset
sum problems in nilpotent, polycyclic, and cocontextfree
groups (with Daniel
König and
Georg Zetzsche)
Contemporary Mathematics 677 (Algebra and Computer Science), pp. 129144, 2016
© AMS Press 
Rational subsets and
submonoids of wreath products (with Benjamin
Steinberg and
Georg Zetzsche)
Information and Computation 243, pp. 191204, 2015 (special issue for ICALP 2013)
© Elsevier 
The complexity of
decomposing modal and firstorder 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(12), pp. 113121 2015
© World Scientific 
XML compression via
DAGs (with Mireille
BousquetMélou, Sebastian
Maneth and Eric
Nöth)
Theory of Computing Systems 57(4), pp. 13221371, 2015 (special issue for ICDT 2013)
© Springer  The
firstorder 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. 11501167, 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. 51035151, 2013
© AMS Press  Treeautomatic
wellfounded trees (with
Martin Huschenbett, Alexander
Kartzow, and Jiamou Liu)
Logical Methods in Computer Science 9(2), paper 10, 2013 
Branchingtime model
checking of onecounter processes and timed
automata (with Stefan
Göller)
SIAM Journal on Computing 42(3), pp. 884923, 2013
© SIAM 
Isomorphism of regular
trees and words (with Christian
Mathissen)
Information and Computation 224, pp. 71105, 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
omegaautomatic trees (with
Dietrich Kuske and Jiamou Liu)
Annals of Pure and Applied Logic 164(1), pp. 3048, 2013
© Elsevier  Algorithmics on
SLPcompressed strings: a survey
Groups Complexity Cryptology 4(2), pp. 241299, 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. 7794, 2012
© AMS Press  Parameter reduction and automata evaluation
for grammarcompressed trees (with Sebastian
Maneth and
Manfred SchmidtSchauß)
Journal of Computer and System Sciences 78(5), pp. 16511669, 2012
© Elsevier  Modelchecking hierarchical
structures
Journal of Computer and System Sciences 78(2), pp. 461490, 2012
© Elsevier 
Automatic structures of
bounded degree revisited (with
Dietrich Kuske)
Journal of Symbolic Logic 76(4), pp. 13521380, 2011
© Association of Symbolic Logic  Compressed word problems in
HNNextensions and amalgamated products (with
Niko
Haubold)
Theory of Computing Systems 49(2), pp. 283305, 2011
© Springer 
Leaf languages and string
compression
Information and Computation 209(6), pp. 951965, 2011
© Elsevier  Tilings and submonoids
of metabelian groups (with Benjamin
Steinberg)
Theory of Computing Systems 48(2), pp. 411427, 2011
© Springer  Fixpoint logics on hierarchical
structures (with Stefan
Göller)
Theory of Computing Systems 48(1), pp. 93131, 2011
© Springer  Compressed membership
problems for regular expressions and hierarchical
automata
International Journal of Foundations of Computer Science 21(5), pp. 817841, 2010
© World Scientific  Submonoids and rational
subsets of groups with infinitely many ends
(with Benjamin
Steinberg)
Journal of Algebra 324(5), pp. 970983, 2010
© Elsevier 
Some natural
decision problems in automatic graphs (with
Dietrich Kuske)
Journal of Symbolic Logic 75(2), pp. 678710, 2010
© Association of Symbolic Logic  An automata theoretic
approach to the generalized word problem in graphs of
groups (with Benjamin
Steinberg)
Proceedings of the AMS 138, pp. 445453, 2010
© AMS Press 
PDL with intersection and
converse: satisfiability and infinitestate model
checking (with Stefan
Göller and Carsten
Lutz)
Journal of Symbolic Logic 74(1), pp. 279314, 2009
© Association of Symbolic Logic  Partially commutative inverse
monoids (with Volker
Diekert and Alexander Miller)
Semigroup Forum 77(2), pp. 196226, 2008
© Springer  Word equations over graph
products (with Volker
Diekert)
International Journal of Algebra and Computation 18(3), pp. 493533, 2008
© World Scientific  The
submonoid and rational subset membership problems for graph
groups (with Benjamin
Steinberg)
Journal of Algebra 320(2), pp. 728755, 2008
© Elsevier 
Efficient Memory
Representation of XML Document Trees (with
Giorgio Busatto and Sebastian
Maneth)
Information Systems 33(45), pp. 456474, 2008
© Elsevier  Algorithmic problems on
inverse monoids over virtuallyfree groups
(with Volker
Diekert and Nicole Ondrusch)
International Journal of Algebra and Computation 18(1), pp. 181208, 2008
© World Scientific  Rational subsets of
HNNextensions and amalgamated free products
(with Géraud
Sénizergues)
International Journal of Algebra and Computation 18(1), pp. 111163, 2008
© World Scientific  Firstorder and counting theories of
omegaautomatic structures (with
Dietrich Kuske)
Journal of Symbolic Logic 73(1), pp. 129150, 2008
© Association of Symbolic Logic  Inverse
monoids: decidability and complexity of algebraic
questions (with Nicole Ondrusch)
Information and Computation 205(8), pp. 12121234, 2007
© Elsevier  When is a graph
product of groups virtuallyfree? (with
Géraud
Sénizergues)
Communications in Algebra 35(2), pp. 617621, 2007
© Taylor & Francis  The
complexity of tree automata and XPath on grammarcompressed
trees (with Sebastian
Maneth)
Theoretical Computer Science 363(2), pp. 196210, 2006 (special issue for CIAA 2005)
© Elsevier  Logical aspects of Cayleygraphs: The
monoid case (with
Dietrich Kuske)
International Journal of Algebra and Computation 16(2), pp. 307340, 2006
© World Scientific  Word
problems and membership problems on compressed
words
SIAM Journal on Computing 35(5), pp. 12101240, 2006
© SIAM 
Axiomatising
divergence (with Pedro D'Argenio
and Holger
Hermanns)
Information and Computation 203(2), pp. 115144, 2005
© Elsevier  Decidability and complexity in automatic
monoids
International Journal of Foundations of Computer Science 16(4), pp. 707722, 2005 (special issue for DLT 2004)
© World Scientific  Complexity results for
prefix grammars (with
Holger Petersen)
RAIRO  Theoretical Informatics and Applications 39(2), pp. 389399, 2005
© EDP Sciences  Decidable firstorder theories of
onestep rewriting in trace monoids (with
Dietrich Kuske)
Theory of Computing Systems 38(1), pp. 3881, 2005
© Springer  Logical aspects of Cayleygraphs: The
group case (with
Dietrich Kuske)
Annals of Pure and Applied Logic 131(13), pp. 263286, 2005
© Elsevier 
Bounded MSC
communication (with Anca Muscholl)
Information and Computation 189(2), pp. 160181, 2004
© Elsevier  Existential and positive theories of
equations in graph products (with Volker
Diekert)
Theory of Computing Systems 37(1), pp. 133156, 2004 (special issue for STACS 2002)
© Springer 
Realizability of highlevel
message sequence charts: closing the gaps
Theoretical Computer Science 309(13), pp. 529554, 2003
© Elsevier  A note on the
existential theory of equations in plain
groups (with Volker
Diekert)
International Journal of Algebra and Computation 12, pp. 17, 2002
© World Scientific  Confluence problems for
trace rewriting
Information and Computation 170, pp. 125, 2001
© Elsevier  NPcompleteness results
concerning the transformation of logic programs into
attribute grammars
Acta Cybernetica 13(3), pp. 209224, 1998
© Institute of Informatics, University of Szeged
Conference papers
 Subgroup membership in GL(2,Z)
to appear in Proceedings of STACS 2021
online version at Schloss Dagstuhl LeibnizZentrum für Informatik  A comparison of empirical tree entropies
(with Danny
Hucke and Louisa
Seelbach)
Proceedings of SPIRE 2020, LNCS 12303, pp. 232246
arxiv version  Knapsack and the power word problem in solvable BaumslagSolitar groups (with Georg Zetzsche)
to appear in Proceedings of MFCS 2020
arxiv version  Groups with
ALOGTIMEhard word problems and PSPACEcomplete compressed
word problems (with Laurent
Bartholdi, Michael
Figelius and Armin
Weiß)
Proceedings of CCC 2020
online version at Schloss Dagstuhl LeibnizZentrum für Informatik arxiv 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 LeibnizZentrum 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 LeibnizZentrum für Informatik arxiv version  Balancing
straightline programs (with Moses
Ganardi and Artur Jez)
Proceedings of FOCS 2019, pp. 11691183
© IEEE Computer Society Press arxiv version journal version  The power word problem (with
Armin
Weiß)
Proceedings of MFCS 2019
online version at Schloss Dagstuhl LeibnizZentrum für Informatik arxiv version  Combined compression of multiple correlated
data streams for onlinediagnosis systems
(with Seungbum Jo,
Simon Meckel,
Roman Obermaisser and Simon Plasger)
Proceedings of Euromicro DSD 2019, pp. 166173
© IEEE Computer Society Press journal version  Largest common prefix of a
regular tree languages (with Sebastian
Maneth)
Proceedings of FCT 2019, LNCS 11651, pp. 95108
© Springer journal version  Entropy bounds for grammarbased tree
compressors (with Danny
Hucke and Louisa
Seelbach)
Proceedings of ISIT 2019, pp. 16871691
© 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. 237249
© Springer journal version  Compressed decision
problems in hyperbolic groups (with
Derek Holt and Saul
Schleimer)
Proceedings of STACS 2019
online version at Schloss Dagstuhl LeibnizZentrum für Informatik arxiv version  Knapsack in hyperbolic groups
Proceedings of Reachability Problems 2018, LNCS 11123, pp. 87102
© Springer arxiv version journal version  Average case
analysis of leafcentric binary tree sources
(with Louisa
Seelbach)
Proceedings of MFCS 2018
online version at Schloss Dagstuhl LeibnizZentrum für Informatik arxiv version  Sliding windows over contextfree
languages (with Moses
Ganardi and Artur Jez )
Proceedings of MFCS 2018
online version at Schloss Dagstuhl LeibnizZentrum 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 LeibnizZentrum für Informatik arxiv version  Grammarbased compression
of unranked trees (with Adria Gascon,
Sebastian
Maneth,
Carl Philipp Reh and Kurt
Sieber)
Proceedings of CSR 2018, LNCS 10846, pp. 118131
© 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 LeibnizZentrum 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 LeibnizZentrum 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 LeibnizZentrum für Informatik arxiv version  An architecture for
onlinediagnosis systems supporting compressed
communication (with Seungbum Jo,
Damian Ludwig,
Simon Meckel,
Roman Obermaisser and Simon Plasger)
Proceedings of Euromicro DSD 2017, pp. 6269
© IEEE Computer Society Press journal version  Universal tree
source coding using grammarbased compression
(with Danny
Hucke)
Proceedings of IEEE ISIT 2017, pp. 17531757
© IEEE Computer Society Press arxiv version journal version  Computing quantiles
in Markov chains with multidimensional 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 LeibnizZentrum 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 LeibnizZentrum 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 LeibnizZentrum für Informatik  Querying
regular languages over slidingwindows (with
Moses
Ganardi and Danny
Hucke)
Proceedings of FSTTCS 2016
online version at Schloss Dagstuhl LeibnizZentrum für Informatik  The smallest grammar
problem revisited (with
Danny Hucke and
Carl Philipp Reh)
Proceedings of SPIRE 2016, LNCS 9954, pp. 3549 (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 LeibnizZentrum für Informatik journal version  Traversing
grammarcompressed trees with constant delay
(with Sebastian
Maneth and
Carl Philipp Reh)
Proceedings of DCC 2016, pp. 546555
© IEEE Computer Society Press arxiv version journal version  Knapsack in graph
groups, HNNextensions and amalgamated
products (with
Georg Zetzsche)
Proceedings of STACS 2016
online version at Schloss Dagstuhl LeibnizZentrum 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. 590604
© 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. 445458
© 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. 326339
© Springer arxiv version journal version  Evaluating matrix
circuits (with Daniel
König)
Proceedings of COCOON 2015, LNCS 9198, pp. 235248
© Springer journal version  Compressed tree
canonization (with Sebastian
Maneth and Fabian
Peternek)
Proceedings of ICALP 2015, LNCS 9135, pp. 337349
© Springer arxiv version  Satisfiability of ECTL
with tree constraints
(with Claudia
Carapelle, Alexander
Kartzow and
Shiguang Feng)
Proceedings of CSR 2015, LNCS 9139, pp. 94108
© 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. 457468
online version at Schloss Dagstuhl LeibnizZentrum für Informatik arxiv version journal version  Processing succinct
matrices and vectors (with
Manfred SchmidtSchauß)
Proceedings of CSR 2014, LNCS 8476, pp. 245258
© Springer arxiv version journal version  On Boolean closed full
trios and rational Kripke frames (with
Georg Zetzsche)
Proceedings of STACS 2014, pp. 530541
online version at Schloss Dagstuhl LeibnizZentrum für Informatik
journal version  Approximation of
smallest linear tree grammars (with Artur Jez)
Proceedings of STACS 2014, pp. 445457
online version at Schloss Dagstuhl LeibnizZentrum für Informatik
journal version  Satisfiability of CTL*
with constraints (with Claudia
Carapelle and Alexander
Kartzow)
Proceedings of CONCUR 2013, LNCS 8052, pp. 455469
© Springer journal version  Rational subsets and
submonoids of wreath products (with Benjamin
Steinberg and
Georg Zetzsche)
Proceedings of ICALP 2013, LNCS 7966, pp. 361372
© 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. 97112
online version at Schloss Dagstuhl LeibnizZentrum für Informatik  XML compression via
DAGs (with Sebastian
Maneth and Eric
Nöth)
Proceedings of ICDT 2013, pp. 6980
© ACM journal version  The complexity of
decomposing modal and firstorder theories
(with Stefan
Göller and Jean
Christoph Jung)
Proceedings of LICS 2012, pp. 325334
© IEEE Computer Society Press journal version  Treeautomatic
wellfounded trees (with Alexander
Kartzow and Jiamou Liu)
Proceedings of CiE 2012, LNCS 7318, pp. 363373
© 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. 243254
© Springer journal version  The firstorder theory
of ground tree rewrite graphs (with Stefan
Göller)
Proceedings of FSTTCS 2011, pp.276287
online version at Schloss Dagstuhl LeibnizZentrum für Informatik journal version  Compressed word problems
for inverse monoids
Proceedings of MFCS 2011, LNCS 6907, pp. 448459
© Springer long version  Isomorphism of regular
trees and words (with Christian
Mathissen)
Proceedings of ICALP 2011, LNCS 6756, pp. 210221
© Springer journal version  Compressed
membership in automata with compressed labels
(with Christian
Mathissen)
Proceedings of CSR 2011, LNCS 6651, pp. 275288
© Springer  Tree structure compression
with RePair (with Sebastian
Maneth and
Roy Mennicke)
Proceedings of DCC 2011, pp. 353362
© IEEE Computer Society Press journal version very detailed version  The isomorphism problem
for omegaautomatic trees (with
Dietrich Kuske and Jiamou Liu)
Proceedings of CSL 2010, LNCS 6247, pp. 396410
© 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. 218230
© 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. 160169
© IEEE Computer Society Press journal version  Branchingtime model
checking of onecounter processes (with
Stefan
Göller)
Proceedings of STACS 2010, pp. 405416
online version at Schloss Dagstuhl LeibnizZentrum für Informatik journal version  Automatic structures of
bounded degree revisited (with
Dietrich Kuske)
Proceedings of CSL 2009, LNCS 5771, pp. 364378
© Springer journal version  Compressed word problems
in HNNextensions and amalgamated products
(with Niko
Haubold)
Proceedings of CSR 2009, LNCS 5675, pp. 237249
© Springer journal version  Parameter reduction in
grammarcompressed trees (with Sebastian
Maneth and
Manfred SchmidtSchauß)
Proceedings of FOSSACS 2009, LNCS 5504, pp. 212226
© Springer journal version  Leaf languages and
string compression
Proceedings of FSTTCS 2008, pp. 292303
online version at Schloss Dagstuhl LeibnizZentrum für Informatik journal version  Euler paths and ends in
automatic and recursive graphs (with
Dietrich Kuske)
Proceedings of AFL 2008, pp. 245256
journal version (Some natural decision problems in automatic graphs)  Hamiltonicity of
automatic graphs (with
Dietrich Kuske)
Proceedings of IFIPTCS 2008, pp. 445459
© 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. 249258
© Springer long version  The submonoid and rational
subset membership problems for graph groups
(with Benjamin
Steinberg)
Proceedings of LATA 2007, pp. 367378
journal version  PDL with intersection
and converse is 2EXPcomplete (with Stefan
Göller and Carsten
Lutz)
Proceedings of FOSSACS 2007, LNCS 4423, pp. 198212
© Springer journal version (PDL with intersection and converse: satisfiability and infinitestate model checking)  Infinite state
modelchecking of propositional dynamic logics
(with Stefan
Göller)
Proceedings of CSL 2006, LNCS 4207, pp. 349364
© Springer journal version (PDL with intersection and converse: satisfiability and infinitestate model checking)
technical report  Partially commutative
inverse monoids (with Volker
Diekert and Alexander Miller)
Proceedings of MFCS 2006, LNCS 4162, pp. 292304
© Springer journal version  Querying and embedding
compressed texts (with Yury Lifshits)
Proceedings of MFCS 2006, LNCS 4162, pp. 681692
© Springer  Monadic chain logic over
iterations and applications to pushdown
systems (with
Dietrich Kuske)
Proceedings of LICS 2006, pp. 91100
© IEEE Computer Society Press  Theories of
HNNextensions and amalgamated products (with
Géraud
Sénizergues)
Proceedings of ICALP 2006, LNCS 4052, pp. 504515
© Springer  Firstorder and counting
theories of omegaautomatic structures (with
Dietrich Kuske)
Proceedings of FOSSACS 2006, LNCS 3921, pp. 322336
© Springer journal version  Fixpoint logics on
hierarchical structures (with Stefan
Göller)
Proceedings of FSTTCS 2005, LNCS 3821, pp. 483494
© Springer technical report journal version  Tree Automata and XPath
on compressed trees (with Sebastian
Maneth)
Proceedings of CIAA 2005, LNCS 3845, pp. 225237 (Best paper award)
© Springer journal version (The complexity of tree automata and XPath on grammarcompressed trees)  Efficient memory
representation of XML documents (with Giorgio
Busatto and Sebastian
Maneth)
Proceedings of DBPL 2005, LNCS 3774, pp. 199216
© Springer journal version  Inverse monoids:
decidability and complexity of algebraic
questions (with Nicole Ondrusch)
Proceedings of MFCS 2005, LNCS 3618, pp. 664675
© Springer journal version  Modelchecking
hierarchical structures
Proceedings of LICS 2005, pp. 168177
© IEEE Computer Society Press journal version  Decidability and
complexity in automatic monoids
Proceedings of DLT 2004, LNCS 3340, pp. 308320
© Springer journal version  Word problems on
compressed words
Proceedings of ICALP 2004, LNCS 3142, pp. 906918
© 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. 156167
© Springer journal version  Automatic structures of
bounded degree
Proceedings of LPAR 2003, LNAI 2850, pp. 344358
© Springer  Decidable theories of
Cayleygraphs (with
Dietrich Kuske)
Proceedings of STACS 2003, LNCS 2607, pp. 463474
© Springer journal version (group case) journal version (monoid case)  Safe realizability of
highlevel message sequence charts
Proceedings of CONCUR 2002, LNCS 2421, pp. 177192, 2002
© Springer journal version (Realizability of highlevel message sequence charts: closing the gaps)  On the theory of
onestep rewriting in trace monoids (with
Dietrich Kuske)
Proceedings of ICALP 2002, LNCS 2380, pp. 752763, 2002
© Springer journal version (Decidable firstorder theories of onestep rewriting in trace monoids)  Axiomatising
divergence (with Pedro D'Argenio
and Holger
Hermanns)
Proceedings of ICALP 2002, LNCS 2380, pp. 585596, 2002
© Springer journal version  Bounded MSC
communication (with Anca Muscholl)
Proceedings of FOSSACS 2002, LNCS 2303, pp. 295309, 2002
© Springer journal version  Existential and positive
theories of equations in graph products (with
Volker
Diekert)
Proceedings of STACS 2002, LNCS 2285, pp. 501512, 2002
© Springer journal version  Word problems for
2homogeneous monoids and symmetric logspace
Proceedings of MFCS 2001, LNCS 2136, pp. 500511, 2001
© Springer  On the parallel complexity
of tree automata
Proceedings of RTA 2001, LNCS 2051, pp. 201216, 2001
© Springer  Implementing Luby's
algorithm on the Cray T3E (with Jürgen Gross)
High Performance Computing in Science and Engineering, pp. 467477, Springer 2000
© Springer  Word problems and
confluence problems for restricted semiThue
systems
Proceedings of RTA 2000, LNCS 1833, pp. 172186, 2000
© Springer  Complexity results for
confluence problems
Proceedings of MFCS 99, LNCS 1672, pp. 114124, 1999
© Springer long version  On the confluence of
trace rewriting systems
Proceedings of FSTTCS 98, LNCS 1530, pp. 319330, 1998
© Springer long version  Priority and maximal
progress are completely axiomatisable (extended
abstract) (with Holger
Hermanns)
Proceedings of CONCUR 98, LNCS 1466, pp. 237252, 1998
© Springer long version
Others
 Equations in
HNNextensions
(with Géraud Sénizergues)  Positive theories of
HNNextensions 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