Veröffentlichungen von Markus Lohrey
Journalarbeiten
- 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
- Rational subsets of HNN-extensions and amalgamated free
products (mit Géraud Sénizergues), erscheint
in International Journal of Algebra and Computation
PS
PDF
- First-order and counting theories of omega-automatic structures
(mit Dietrich Kuske),
erscheint in Journal of Symbolic Logic
PS
PDF
- Model-checking hierarchical structures, erscheint in Journal
of Computer and System Sciences
PS
PDF
- Efficient Memory Representation of XML Document Trees (mit
Giorgio Busatto und Sebastian Maneth), erscheint in Information Systems
PS
PDF
- Inverse monoids: decidability and complexity of algebraic
questions (mit Nicole Ondrusch), Information and Computation 205(8), S. 1212-1234, 2007
PS
PDF
© Elsevier
- 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
- 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
- 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
- Word problems and membership problems on compressed words ,
SIAM Journal on Computing 35(5), S. 1210-1240, 2006
PS
PDF
© SIAM
- Axiomatising divergence (mit Pedro D'Argenio und Holger
Hermanns), Information and Computation 203(2), S. 115-144, 2005
PS
PDF
© Elsevier
- 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
- Complexity results for prefix grammars (mit Holger
Petersen), RAIRO - Theoretical Informatics and Applications 39(2), S. 389-399, 2005
PS
PDF
© EDP Sciences
- 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
- 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
- Bounded MSC communication (mit Anca Muscholl),
Information and Computation 189(2), S. 160-181, 2004
PS
PDF
© Elsevier
- 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
- Realizability of high-level message sequence charts:
closing the gaps, Theoretical Computer Science 309(1-3), S. 529-554, 2003
PS
PDF
© Elsevier
- 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
- Confluence problems for trace rewriting,
Information and Computation 170, S. 1-25, 2001
PS
PDF
© Elsevier
- NP-completeness results concerning the transformation of logic programs into
attribute grammars, Acta Cybernetica 13, S. 209-224, 1998
PS
PDF
Konferenzarbeiten
- Efficient computation in groups via compression (mit Saul
Schleimer), erscheint in Proceedings of CSR 2007
PS
PDF
- The submonoid and rational subset membership problems for graph
groups (mit Benjamin Steinberg), Proceedings of LATA 2007
PS
PDF
- 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
- 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
- Partially commutative inverse monoids (mit Volker Diekert und Alexander Miller),
Proceedings of MFCS 2006, LNCS 4162, S. 292-304
PS
PDF
© Springer
- Querying and Embedding Compressed Texts (mit Yury Lifshits),
Proceedings of MFCS 2006, LNCS 4162, S. 681-692
PS
PDF
© Springer
- 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
- Theories of HNN-extensions and amalgamated products (mit Géraud
Sénizergues),
Proceedings of ICALP 2006, LNCS 4052, S. 504-515
PS
PDF
© Springer
- First-order and counting theories of omega-automatic structures (mit Dietrich Kuske),
Proceedings of FOSSACS 2006, LNCS 3921, S. 322-336
PS
PDF
© Springer
- Fixpoint logics on hierarchical structures (mit Stefan
Göller), Proceedings of FSTTCS 2005, LNCS 3821, S. 483-494
PS
PDF
© Springer
Technischer Bericht
- Tree Automata and XPath on Compressed Trees (mit Sebastian Maneth),
Proceedings of CIAA 2005, LNCS 3845, S. 225-237
PS
PDF
- Efficient Memory Representation of XML Documents (mit Giorgio
Busatto und Sebastian Maneth), Proceedings of DBPL 2005, LNCS 3774, S. 199-216
PS
PDF
© Springer
- Inverse monoids: decidability and complexity of algebraic
questions (mit Nicole Ondrusch),
Proceedings of MFCS 2005, LNCS 3618, S. 664-675
PS
PDF
© Springer
- Model-checking hierarchical structures,
Proceedings of LICS 2005, S. 168-177
PS
PDF
©
IEEE Computer Society Press
- Decidability and complexity in automatic monoids, Proceedings of DLT 2004,
LNCS 3340, S. 308-320
PS
PDF
© Springer
- Word problems on compressed words, Proceedings of ICALP 2004,
LNCS 3142, S. 906-918
PS
PDF
© Springer
- Word equations over graph products
(mit Volker Diekert), Proceedings of FSTTCS 2003, LNCS 2914, S. 156-167
PS
PDF
© Springer
- Automatic structures of bounded degree,
Proceedings of LPAR 2003, LNAI 2850, S. 344-358
PS
PDF
© Springer
- Decidable theories of Cayley-graphs (mit Dietrich Kuske),
Proceedings of STACS 2003, LNCS 2607, S. 463-474
PS
PDF
© Springer
- Safe realizability of high-level message sequence charts,
Proceedings of CONCUR 2002, LNCS 2421, S. 177-192, 2002
PS
PDF
© Springer
- 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
- Axiomatising divergence (mit Pedro D'Argenio und Holger Hermanns),
Proceedings of ICALP 2002, LNCS 2380, S. 585-596, 2002
PS
PDF
© Springer
- Bounded MSC communication (mit Anca Muscholl),
Proceedings of FOSSACS 2002, LNCS 2303, S. 295-309, 2002
PS
PDF
© Springer
- 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
- Word problems for 2-homogeneous monoids and
symmetric logspace,
Proceedings of MFCS 2001, LNCS 2136, S. 500-511, 2001
PS
PDF
© Springer
- On the parallel complexity of tree automata,
Proceedings of RTA 2001, LNCS 2051, S. 201-216, 2001
PS
PDF
© Springer
- 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
- Word problems and confluence problems for restricted semi-Thue systems,
Proceedings of RTA 2000, LNCS 1833, S. 172-186, 2000
PS
PDF
© Springer
- Complexity results for confluence problems,
Proceedings of MFCS 99, LNCS 1672, S. 114-124, 1999
Langversion
- On the confluence of trace rewriting systems,
Proceedings of FSTTCS 98, LNCS 1530, S. 319-330, 1998
Langversion
- 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
- The submonoid and rational subset membership problems for graph
groups (mit Benjamin Steinberg)
PS
PDF
- Fixpoint logics on hierarchical structures (mit Stefan
Göller)
PS
PDF
- Partially commutative inverse monoids (mit Volker Diekert und Alexander Miller)
PS
PDF
- Word equations over graph products
(mit Volker Diekert)
PS
PDF
Weiteres
-
Manuscripts on equations in HNN-extensions and
amalgamated products
(mit Géraud Sénizergues)
- Computational aspects of infinite monoids,
Habilitationsschrift, Stuttgart, 2003
PS
PDF
- 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