Publications of Markus Lohrey

Journal papers

  1. Algorithmic problems on inverse monoids over virtually-free groups (with Volker Diekert and Nicole Ondrusch), to appear in International Journal of Algebra and Computation
    PS    PDF
  2. Rational subsets of HNN-extensions and amalgamated free products (with Géraud Sénizergues), to appear in International Journal of Algebra and Computation
    PS    PDF
  3. First-order and counting theories of omega-automatic structures (with Dietrich Kuske), to appear in Journal of Symbolic Logic
    PS    PDF
  4. Model-checking hierarchical structures, to appear in Journal of Computer and System Sciences
    PS    PDF
  5. Efficient Memory Representation of XML Document Trees (with Giorgio Busatto and Sebastian Maneth), to appear in Information Systems
    PS    PDF
  6. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch), Information and Computation 205(8), pp. 1212-1234, 2007
    PS    PDF    © Elsevier
  7. When is a graph product of groups virtually-free? (with Géraud Sénizergues), Communications in Algebra 35(2), pp. 617-621, 2007
    PS    PDF
  8. 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)
    PS    PDF    © Elsevier
  9. Logical Aspects of Cayley-Graphs: The Monoid Case (with Dietrich Kuske), International Journal of Algebra and Computation 16(2), pp. 307-340, 2006
    PS    PDF    © World Scientific
  10. Word problems and membership problems on compressed words , SIAM Journal on Computing 35(5), pp. 1210-1240, 2006
    PS    PDF    © SIAM
  11. Axiomatising divergence (with Pedro D'Argenio and Holger Hermanns), Information and Computation 203(2), pp. 115-144, 2005
    PS    PDF    © Elsevier
  12. Decidability and complexity in automatic monoids, International Journal of Foundations of Computer Science 16(4), pp. 707-722, 2005 (special issue for DLT 2004)
    PS    PDF    © World Scientific
  13. Complexity Results for Prefix Grammars (with Holger Petersen), RAIRO - Theoretical Informatics and Applications 39(2), pp. 389-399, 2005
    PS    PDF    © EDP Sciences
  14. Decidable first-order theories of one-step rewriting in trace monoids (with Dietrich Kuske), Theory of Computing Systems 38(1), pp. 38-81, 2005
    PS    PDF    © Springer
  15. Logical Aspects of Cayley-Graphs: The Group Case (with Dietrich Kuske), Annals of Pure and Applied Logic 131(1-3), pp. 263-286, 2005
    PS    PDF    © Elsevier
  16. Bounded MSC communication (with Anca Muscholl), Information and Computation 189(2), pp. 160-181, 2004
    PS    PDF    © Elsevier
  17. Existential and Positive Theories of Equations in Graph Products (with Volker Diekert), Theory of Computing Systems 37(1), pp. 133-156, 2003 (special issue for STACS 2002)
    PS    PDF    © Springer
  18. Realizability of high-level message sequence charts: closing the gaps, Theoretical Computer Science 309(1-3), pp. 529-554, 2003
    PS    PDF    © Elsevier
  19. 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
    PS    PDF    © World Scientific
  20. Confluence Problems for Trace Rewriting, Information and Computation 170, pp. 1-25, 2001
    PS    PDF    © Elsevier
  21. NP-completeness results concerning the transformation of logic programs into attribute grammars, Acta Cybernetica 13, pp. 209-224, 1998
    PS    PDF

Conference papers

  1. Efficient computation in groups via compression (with Saul Schleimer), to appear in Proceedings of CSR 2007
    PS    PDF
  2. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg), Proceedings of LATA 2007
    PS    PDF
  3. PDL with intersection and converse is 2EXP-complete (with Stefan Göller and Carsten Lutz), Proceedings of FOSSACS 2007, LNCS 4423, pp. 198-212
    PS    PDF
  4. Infinite state model-checking of propositional dynamic logics (with Stefan Göller), Proceedings of CSL 2006, LNCS 4207, pp. 349-364
    PS    PDF    © Springer    Technical Report
  5. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller), Proceedings of MFCS 2006, LNCS 4162, pp. 292-304
    PS    PDF    © Springer
  6. Querying and Embedding Compressed Texts (with Yury Lifshits), Proceedings of MFCS 2006, LNCS 4162, pp. 681-692
    PS    PDF    © Springer
  7. Monadic chain logic over iterations and applications to pushdown systems (with Dietrich Kuske), Proceedings of LICS 2006, S. 91-100
    PS    PDF    © IEEE Computer Society Press
  8. Theories of HNN-extensions and amalgamated products (with Géraud Sénizergues), Proceedings of ICALP 2006, LNCS 4052, pp. 504-515
    PS    PDF    © Springer
  9. First-order and counting theories of omega-automatic structures (with Dietrich Kuske), Proceedings of FOSSACS 2006, LNCS 3921, pp. 322-336
    PS    PDF    © Springer
  10. Fixpoint logics on hierarchical structures (with Stefan Göller), Proceedings of FSTTCS 2005, LNCS 3821, pp.483-494
    PS    PDF    © Springer    Technical Report
  11. Tree Automata and XPath on Compressed Trees (with Sebastian Maneth), Proceedings of CIAA 2005, LNCS 3845, pp. 225-237
    PS    PDF    © Springer
  12. Efficient Memory Representation of XML Documents (with Giorgio Busatto and Sebastian Maneth), Proceedings of DBPL 2005, LNCS 3774, pp. 199-216
    PS    PDF    © Springer
  13. Inverse monoids: decidability and complexity of algebraic questions (with Nicole Ondrusch), Proceedings of MFCS 2005, LNCS 3618, pp. 664-675
    PS    PDF    © Springer
  14. Model-checking hierarchical structures, Proceedings of LICS 2005, pp. 168-177
    PS    PDF    © IEEE Computer Society Press
  15. Decidability and complexity in automatic monoids, Proceedings of DLT 2004, LNCS 3340, pp. 308-320
    PS    PDF    © Springer
  16. Word problems on compressed words, Proceedings of ICALP 2004, LNCS 3142, pp. 906-918
    PS    PDF    © Springer
  17. Word equations over graph products (with Volker Diekert), Proceedings of FSTTCS 2003, LNCS 2914, pp. 156-167
    PS    PDF    © Springer
  18. Automatic structures of bounded degree, Proceedings of LPAR 2003, LNAI 2850, pp. 344-358
    PS    PDF    © Springer
  19. Decidable theories of Cayley-graphs (with Dietrich Kuske), Proceedings of STACS 2003, LNCS 2607, pp. 463-474
    PS    PDF    © Springer
  20. Safe realizability of high-level message sequence charts, Proceedings of CONCUR 2002, LNCS 2421, pp. 177-192, 2002
    PS    PDF    © Springer
  21. On the theory of one-step rewriting in trace monoids (with Dietrich Kuske), Proceedings of ICALP 2002, LNCS 2380, pp. 752-763, 2002
    PS    PDF    © Springer
  22. Axiomatising Divergence (with Pedro D'Argenio and Holger Hermanns), Proceedings of ICALP 2002, LNCS 2380, pp. 585-596, 2002
    PS    PDF    © Springer
  23. Bounded MSC communication (with Anca Muscholl), Proceedings of FOSSACS 2002, LNCS 2303, pp. 295-309, 2002
    PS    PDF    © Springer
  24. Existential and positive theories of equations in graph products (with Volker Diekert), Proceedings of STACS 2002, LNCS 2285, pp. 501-512, 2002
    PS    PDF    © Springer
  25. Word problems for 2-homogeneous monoids and symmetric logspace, Proceedings of MFCS 2001, LNCS 2136, pp. 500-511, 2001
    PS    PDF    © Springer
  26. On the parallel complexity of tree automata, Proceedings of RTA 2001, LNCS 2051, pp. 201-216, 2001
    PS    PDF    © Springer
  27. Implementing Luby's algorithm on the Cray T3E (with Jürgen Gross), High Performance Computing in Science and Engineering, pp. 467-477, Springer 2000
    PS    PDF    © Springer
  28. Word problems and confluence problems for restricted semi-Thue systems, Proceedings of RTA 2000, LNCS 1833, pp. 172-186, 2000
    PS    PDF    © Springer
  29. Complexity results for confluence problems, Proceedings of MFCS 99, LNCS 1672, pp. 114-124, 1999
    long version
  30. On the confluence of trace rewriting systems, Proceedings of FSTTCS 98, LNCS 1530, pp. 319-330, 1998
    long version
  31. Priority and maximal progress are completely axiomatisable (extended abstract) (with Holger Hermanns), Proceedings of CONCUR 98, LNCS 1466, pp. 237-252, 1998
    long version

Submited papers

  1. The submonoid and rational subset membership problems for graph groups (with Benjamin Steinberg)
    PS    PDF
  2. Fixpoint logics on hierarchical structures (with Stefan Göller)
    PS    PDF
  3. Partially commutative inverse monoids (with Volker Diekert and Alexander Miller)
    PS    PDF
  4. Word equations over graph products (with Volker Diekert)
    PS    PDF

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
    PS    PDF
  3. The confluence problem for trace rewriting systems (in German), PhD thesis, Stuttgart, 1999
    PS    PDF
Impressum