Veröffentlichungen von Markus Lohrey

Journalarbeiten

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

Konferenzarbeiten

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

Eingereichte Arbeiten

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

Weiteres

  1. Manuscripts on equations in HNN-extensions and amalgamated products
    (mit Géraud Sénizergues)
  2. Computational aspects of infinite monoids, Habilitationsschrift, Stuttgart, 2003
    PS    PDF
  3. Das Konfluenzproblem für Spurersetzungssysteme, Dissertation, Stuttgart, 1999
    PS    PDF
Markus Lohrey
Zimmer: 0.042
Telefon: (0711-)7816-408
E-Mail: lohrey@informatik.uni-stuttgart.de

Impressum