Publications of Markus Lohrey
This page will be no longer updated. If your are not automatically redirected, please follow this
link.
Submitted papers
Rational subsets and submonoids of wreath products
(with
Benjamin Steinberg
and
Georg Zetzsche
)
XML compression via DAGs
(with
Mireille Bousquet-Mélou
,
Sebastian Maneth
and
Eric Nöth
)
The complexity of decomposing modal and first-order theories
(with
Stefan Göller
and
Jean Christoph Jung
)
Journal papers
The first-order theory of ground tree rewrite graphs
(with
Stefan Göller
)
to appear in Logical Methods in Computer Science, 2014
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:10), pp. 1-44, 2013
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
© American Mathematical Society
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
© Association of Symbolic Logic
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
© 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. 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
© Association of Symbolic Logic
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
© Association of Symbolic Logic
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
On Boolean closed full trios and rational Kripke frames
(with
Georg Zetzsche
)
to appear in Proceedings of STACS 2014
Approximation of smallest linear tree grammars
(with
Artur Jez
)
to appear in Proceedings of STACS 2014
long version
Satisfiability of CTL* with constraints
(with
Claudia Carapelle
and
Alexander Kartzow
)
Proceedings of CONCUR 2013, LNCS 8052, pp. 455-469
long version
Rational subsets and submonoids of wreath products
(with
Benjamin Steinberg
and
Georg Zetzsche
)
Proceedings of ICALP 2013, LNCS 7966, pp. 361-372
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
long 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
long 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
© 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
Manuscripts on equations in HNN-extensions and amalgamated 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