Publications of Markus Lohrey

Submitted papers

  1. Branching-time model checking of one-counter processes and timed automata (with Stefan Göller)

  2. The isomorphism problem for omega-automatic trees (with Dietrich Kuske and Jiamou Liu)

Journal papers

  1. Logspace computations in Coxeter groups and graph groups (with Volker Diekert and Jonathan Kausch)
    to appear in Contemporary Mathematics (Proceedings of the AMS Special Session on Computational Algebra, Groups, and Applications)

  2. Compressed decision problems for graph products of groups and applications to (outer) automorphism groups (with Niko Haubold and Christian Mathissen)
    to appear in International Journal of Algebra and Computation

  3. The isomorphism problem on classes of automatic structures with transitive relations (with Dietrich Kuske and Jiamou Liu)
    to appear in Transactions of the American Mathematical Society

  4. Parameter reduction and automata evaluation for grammar-compressed trees (with Sebastian Maneth and Manfred Schmidt-Schauß)
    Journal of Computer and System Sciences
    © Elsevier

  5. Model-checking hierarchical structures
    Journal of Computer and System Sciences 78(2), pp. 461-490, 2012
    © Elsevier

  6. Automatic structures of bounded degree revisited (with Dietrich Kuske)
    Journal of Symbolic Logic 76(4), pp. 1352-1380, 2011
    © Association of Symbolic Logic

  7. Compressed word problems in HNN-extensions and amalgamated products (with Niko Haubold)
    Theory of Computing Systems 49(2), pp. 283-305, 2011
    © Springer

  8. Leaf languages and string compression
    Information and Computation 209(6), pp. 951-965, 2011
    © Elsevier

  9. Tilings and submonoids of metabelian groups (with Benjamin Steinberg)
    Theory of Computing Systems 48(2), pp. 411-427, 2011
    © Springer

  10. Fixpoint logics on hierarchical structures (with Stefan Göller)
    Theory of Computing Systems 48(1), pp. 93-131, 2011
    © Springer

  11. Compressed membership problems for regular expressions and hierarchical automata
    International Journal of Foundations of Computer Science 21(5), pp. 817-841, 2010
    © World Scientific

  12. Submonoids and rational subsets of groups with infinitely many ends (with Benjamin Steinberg)
    Journal of Algebra 324(5), pp. 970-983, 2010
    © Elsevier

  13. Some natural decision problems in automatic graphs (with Dietrich Kuske)
    Journal of Symbolic Logic 75(2), pp. 678-710, 2010
    © Association of Symbolic Logic

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

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

  16. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller)
    Semigroup Forum 77(2), pp. 196-226, 2008
    © Springer

  17. Word equations over graph products (with Volker Diekert)
    International Journal of Algebra and Computation 18(3), pp. 493-533, 2008
    © World Scientific

  18. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg)
    Journal of Algebra 320(2), pp. 728-755, 2008
    © Elsevier

  19. Efficient Memory Representation of XML Document Trees (with Giorgio Busatto and Sebastian Maneth)
    Information Systems 33(4-5), pp. 456-474, 2008
    © Elsevier

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

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

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

  23. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch)
    Information and Computation 205(8), pp. 1212-1234, 2007
    © Elsevier

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

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

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

  27. Word problems and membership problems on compressed words
    SIAM Journal on Computing 35(5), pp. 1210-1240, 2006
    © SIAM

  28. Axiomatising divergence (with Pedro D'Argenio and Holger Hermanns)
    Information and Computation 203(2), pp. 115-144, 2005
    © Elsevier

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

  30. Complexity results for prefix grammars (with Holger Petersen)
    RAIRO - Theoretical Informatics and Applications 39(2), pp. 389-399, 2005
    © EDP Sciences

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

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

  33. Bounded MSC communication (with Anca Muscholl)
    Information and Computation 189(2), pp. 160-181, 2004
    © Elsevier

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

  35. Realizability of high-level message sequence charts: closing the gaps
    Theoretical Computer Science 309(1-3), pp. 529-554, 2003
    © Elsevier

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

  37. Confluence problems for trace rewriting
    Information and Computation 170, pp. 1-25, 2001
    © Elsevier

  38. 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. The complexity of decomposing modal and first-order theories (with Stefan Göller and Jean Christoph Jung)
    to appear in Proceedings of LICS 2012
    long version

  2. Tree-automatic well-founded trees (with Alexander Kartzow and Jiamou Liu)
    to appear in Proceedings of CiE 2012
    long version

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

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

  5. Compressed word problems for inverse monoids
    Proceedings of MFCS 2011, LNCS 6907, pp. 448-459
    © Springer    long version

  6. Isomorphism of regular trees and words (with Christian Mathissen)
    Proceedings of ICALP 2011, LNCS 6756, pp. 210-221
    © Springer    long version

  7. Compressed membership in automata with compressed labels (with Christian Mathissen)
    Proceedings of CSR 2011, LNCS 6651, pp. 275-288
    © Springer

  8. Tree structure compression with RePair (with Sebastian Maneth and Roy Mennicke)
    Proceedings of DCC 2011, pp. 353-362
    © IEEE Computer Society Press    long version

  9. The isomorphism problem for omega-automatic trees (with Dietrich Kuske and Jiamou Liu)
    Proceedings of CSL 2010, LNCS 6247, pp. 396-410
    © Springer    long version

  10. 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)

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

  12. 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    long version

  13. Automatic structures of bounded degree revisited (with Dietrich Kuske)
    Proceedings of CSL 2009, LNCS 5771, pp. 364-378
    © Springer    journal version

  14. Compressed word problems in HNN-extensions and amalgamated products (with Niko Haubold)
    Proceedings of CSR 2009, LNCS 5675, pp. 237-249
    © Springer    journal version

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

  16. Leaf languages and string compression
    Proceedings of FSTTCS 2008, pp. 292-303
    online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik    journal version

  17. 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)

  18. 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)

  19. Efficient computation in groups via compression (with Saul Schleimer)
    Proceedings of CSR 2007, LNCS 4649, pp. 249-258
    © Springer    long version

  20. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg)
    Proceedings of LATA 2007, pp. 367-378
    journal version

  21. 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)

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

  23. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller)
    Proceedings of MFCS 2006, LNCS 4162, pp. 292-304
    © Springer    journal version

  24. Querying and Embedding Compressed Texts (with Yury Lifshits)
    Proceedings of MFCS 2006, LNCS 4162, pp. 681-692
    © Springer

  25. Monadic chain logic over iterations and applications to pushdown systems (with Dietrich Kuske)
    Proceedings of LICS 2006, pp. 91-100
    © IEEE Computer Society Press

  26. Theories of HNN-extensions and amalgamated products (with Géraud Sénizergues)
    Proceedings of ICALP 2006, LNCS 4052, pp. 504-515
    © Springer

  27. First-order and counting theories of omega-automatic structures (with Dietrich Kuske)
    Proceedings of FOSSACS 2006, LNCS 3921, pp. 322-336
    © Springer    journal version

  28. Fixpoint logics on hierarchical structures (with Stefan Göller)
    Proceedings of FSTTCS 2005, LNCS 3821, pp. 483-494
    © Springer    technical report    journal version

  29. 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)

  30. Efficient Memory Representation of XML Documents (with Giorgio Busatto and Sebastian Maneth)
    Proceedings of DBPL 2005, LNCS 3774, pp. 199-216
    © Springer    journal version

  31. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch)
    Proceedings of MFCS 2005, LNCS 3618, pp. 664-675
    © Springer    journal version

  32. Model-checking hierarchical structures
    Proceedings of LICS 2005, pp. 168-177
    © IEEE Computer Society Press    journal version

  33. Decidability and complexity in automatic monoids
    Proceedings of DLT 2004, LNCS 3340, pp. 308-320
    © Springer    journal version

  34. 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)

  35. Word equations over graph products (with Volker Diekert)
    Proceedings of FSTTCS 2003, LNCS 2914, pp. 156-167
    © Springer    journal version

  36. Automatic structures of bounded degree
    Proceedings of LPAR 2003, LNAI 2850, pp. 344-358
    © Springer

  37. 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)

  38. 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)

  39. 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)

  40. Axiomatising divergence (with Pedro D'Argenio and Holger Hermanns)
    Proceedings of ICALP 2002, LNCS 2380, pp. 585-596, 2002
    © Springer    journal version

  41. Bounded MSC communication (with Anca Muscholl)
    Proceedings of FOSSACS 2002, LNCS 2303, pp. 295-309, 2002
    © Springer    journal version

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

  43. Word problems for 2-homogeneous monoids and symmetric logspace
    Proceedings of MFCS 2001, LNCS 2136, pp. 500-511, 2001
    © Springer

  44. On the parallel complexity of tree automata
    Proceedings of RTA 2001, LNCS 2051, pp. 201-216, 2001
    © Springer

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

  46. Word problems and confluence problems for restricted semi-Thue systems
    Proceedings of RTA 2000, LNCS 1833, pp. 172-186, 2000
    © Springer

  47. Complexity results for confluence problems
    Proceedings of MFCS 99, LNCS 1672, pp. 114-124, 1999
    © Springer    long version

  48. On the confluence of trace rewriting systems
    Proceedings of FSTTCS 98, LNCS 1530, pp. 319-330, 1998
    © Springer    long version

  49. 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. Manuscripts on equations in HNN-extensions and amalgamated products
    (with Géraud Sénizergues)

  2. Computational aspects of infinite monoids
    Habilitation thesis, Stuttgart, 2003

  3. Das Konfluenzproblem für Spurersetzungssysteme (in German)
    PhD thesis, Stuttgart, 1999
Impressum