Markus Lohrey
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Markus Lohrey has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Carsten Lutz
Leipzig University
1 shared publication - Dietrich Kuske
Institut für Algebra, Technische Universität Dresden, D-01062 Dresden, Germany
1 shared publication Géraud Sénizergues
University of Bordeaux I, LaBRI , France
1 shared publication- Holger Petersen
Universität Stuttgart
1 shared publication - Sebastian Maneth
NICTA Australia
1 shared publication - Stefan Göller
Universität Leipzig
1 shared publication
Latest Publications
- 12 March 2009
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 74 (1) , 279-314
PDL with intersection and converse: satisfiability and infinite-state model checking
We study satisfiability and infinite-state model checking in ICPDL, which extends Propositional Dynamic Logic (PDL) with intersection and converse operators on programs. The two main results of this paper are that (i) satisfiability is in 2ΕΧΡΤΙΜΕ, thus 2ΕΧΡΤΙΜΕ-complete by an existing lower bound, and (ii) infinite-state model checking of basic process algebras and pushdown systems is also 2ΕΧΡΤΙΜΕ-complete. Both upper bounds are obtained by polynomial time computable reductions to ω-regular tree satisfiability in ICPDL, a reasoning problem that we introduce specifically for this purpose. This problem is then reduced to the emptiness problem for alternating two-way automata on infinite trees. Our approach to (i) also provides a shorter and more elegant proof of Danecki's difficult result that satisfiability in IPDL is in 2ΕΧΡΤΙΜΕ. We prove the lower bound(s) for infinite-state model checking using an encoding of alternating Turing machines.
- 12 March 2009
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 74 (1) , 279-314
PDL with intersection and converse: satisfiability and infinite-state model checking
We study satisfiability and infinite-state model checking in ICPDL, which extends Propositional Dynamic Logic (PDL) with intersection and converse operators on programs. The two main results of this paper are that (i) satisfiability is in 2ΕΧΡΤΙΜΕ, thus 2ΕΧΡΤΙΜΕ-complete by an existing lower bound, and (ii) infinite-state model checking of basic process algebras and pushdown systems is also 2ΕΧΡΤΙΜΕ-complete. Both upper bounds are obtained by polynomial time computable reductions to ω-regular tree satisfiability in ICPDL, a reasoning problem that we introduce specifically for this purpose. This problem is then reduced to the emptiness problem for alternating two-way automata on infinite trees. Our approach to (i) also provides a shorter and more elegant proof of Danecki's difficult result that satisfiability in IPDL is in 2ΕΧΡΤΙΜΕ. We prove the lower bound(s) for infinite-state model checking using an encoding of alternating Turing machines.
- 26 January 2007
- Published by Taylor & Francis in Communications in Algebra
- Vol. 35 (2) , 617-621
When Is a Graph Product of Groups Virtually-Free?
Those graph products of groups that are virtually-free are characterized.
- 26 January 2007
- Published by Taylor & Francis in Communications in Algebra
- Vol. 35 (2) , 617-621
When Is a Graph Product of Groups Virtually-Free?
Those graph products of groups that are virtually-free are characterized.
- 28 October 2006
- Published by Elsevier in Theoretical Computer Science
- Vol. 363 (2) , 196-210
The complexity of tree automata and XPath on grammar-compressed trees
- 28 October 2006
- Published by Elsevier in Theoretical Computer Science
- Vol. 363 (2) , 196-210
The complexity of tree automata and XPath on grammar-compressed trees
- Open Access
- 15 April 2005
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 39 (2) , 391-401
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
- 15 April 2005
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 39 (2) , 391-401
Open AccessComplexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
- 29 July 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 38 (1) , 39-81
Decidable First-Order Theories of One-Step Rewriting in Trace Monoids
- 29 July 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 38 (1) , 39-81
Decidable First-Order Theories of One-Step Rewriting in Trace Monoids
- 1 January 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 37 (1) , 133-156
Existential and Positive Theories of Equations in Graph Products
- 1 January 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 37 (1) , 133-156
Existential and Positive Theories of Equations in Graph Products