# Publications Markus Lohrey

## Submitted papers

**The smallest grammar problem revisited**(with Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jez and Carl Philipp Reh)**Derandomization for sliding window algorithms with strict correctness**(with Moses Ganardi and Danny Hucke)**Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems**(with Laurent Bartholdi, Michael Figelius and Armin Weiß)

## Books

## Invited papers

**Sliding window algorithms for regular languages**(with Moses Ganardi and Danny Hucke)

Proceedings of LATA 2018, LNCS 10792, pp. 26-35

© Springer**Grammar-based tree compression**

Proceedings of DLT 2015, LNCS 9168, pp. 46-57

© Springer**Equality testing of compressed strings**

Proceedings of WORDS 2015, LNCS 9304, pp. 14-26

© Springer**Temporal logics with local constraints**(with Claudia Carapelle)

Proceedings of CSL 2015, pp. 2-13

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik**The rational subset membership problem for groups: a survey**

Proceedings of Groups St Andrews 2013, London Mathematical Society Lecture Note Series 422, pp. 368-389

© Cambridge University Press

## Journal papers

**Grammar-based compression of unranked trees**(with Adria Gascon, Sebastian Maneth, Carl Philipp Reh and Kurt Sieber)

to appear in Theory of Computing Systems (special issue for CSR 2018)

© Springer**Universal tree source coding using grammar-based compression**(with Moses Ganardi, Danny Hucke and Louisa Seelbach)

IEEE Transactions on Information Theory 65(10), pp. 6399-6413, 2019

© IEEE Computer Society Press**Knapsack in hyperbolic groups**

to appear in Journal of Algebra

© Elsevier**Size-optimal top dag compression**(with Carl Philipp Reh and Kurt Sieber)

Information Processing Letters 147, pp. 27-31, 2019

© Elsevier**The complexity of bisimulation and simulation on finite systems**(with Moses Ganardi and Stefan Göller)

Logical Methods in Computer Science 14(4), 2018

online version**A universal tree balancing theorem**(with Moses Ganardi)

ACM Transactions on Computation Theory 11(1), Article No. 1, 2018

© ACM**Parallel identity testing for skew circuits with big powers and applications**(with Daniel König)

International Journal of Algebra and Computation 28(6), pp. 979-1004, 2018

© World Scientific**An architecture for online-diagnosis systems supporting compressed communication**(with Seungbum Jo, Damian Ludwig, Simon Meckel, Roman Obermaisser and Simon Plasger)

Microprocessors and Microsystems 61, pp. 242-256, 2018 (special issue for Euromicro DSD 2017)

© Elsevier**Circuits and expressions over finite semirings**(with Moses Ganardi, Danny Hucke and Daniel König)

ACM Transactions on Computation Theory 10(4), Article No. 15, 2018

© ACM**Knapsack in graph groups**(with Georg Zetzsche)

Theory of Computing Systems 62(1), pp. 192-246, 2018 (special issue for STACS 2016)

© Springer**Path checking for MTL and TPTL over data words**(with Shiguang Feng and Karin Quaas)

Logical Methods in Computer Science 13(3), 2017

online version**Evaluation of circuits over nilpotent and polycyclic groups**(with Daniel König)

Algorithmica 80(5), pp. 1459-1492, 2018 (special issue for COCOON 2015)

© Springer**Traversing grammar-compressed trees with constant delay**(with Sebastian Maneth and Carl Philipp Reh)

Algorithmica 80(7), pp. 2082-–2105, 2018 (special issue for DCC 2016)

© Springer**Tree compression using string grammars**(with Moses Ganardi, Danny Hucke and Eric Nöth)

Algorithmica 80(3), pp. 885-917, 2018 (special issue for LATIN 2016)

© Springer**Constructing small tree grammars and small circuits for formulas**(with Danny Hucke, Artur Jez, Moses Ganardi and Eric Nöth)

Journal of Computer and System Sciences 86, pp. 136-158, 2017

© Elsevier**Satisfiability of ECTL* with local tree constraints**(with Claudia Carapelle, Shiguang Feng and Alexander Kartzow)

Theory of Computing Systems 61(2), pp. 689-720, 2017 (special issue for CSR 2015)

© Springer**Processing succinct matrices and vectors**(with Manfred Schmidt-Schauß)

Theory of Computing Systems 61(2), pp. 322-351, 2017 (special issue for CSR 2014)

© Springer**Approximation of smallest linear tree grammars**(with Artur Jez)

Information and Computation 251, pp. 215-251, 2016

© Elsevier**On Boolean closed full trios and rational Kripke frames**(with Dietrich Kuske and Georg Zetzsche)

Theory of Computing Systems 60(3), pp. 438-472, 2017 (special issue for STACS 2014)

© Springer**Satisfiability of ECTL* with constraints**(with Claudia Carapelle and Alexander Kartzow)

Journal of Computer and System Sciences 82(5), pp. 826-855, 2016

© Elsevier**Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups**(with Daniel König and Georg Zetzsche)

Contemporary Mathematics 677 (Algebra and Computer Science), pp. 129-144, 2016

© AMS Press-
**Rational subsets and submonoids of wreath products**(with Benjamin Steinberg and Georg Zetzsche)

Information and Computation 243, pp. 191-204, 2015 (special issue for ICALP 2013)

© Elsevier -
**The complexity of decomposing modal and first-order theories**(with Stefan Göller and Jean Christoph Jung)

ACM Transactions on Computational Logic 16(1), Article No. 9, 2015

© ACM **Rational subsets of unitriangular groups**

International Journal of Algebra and Computation 25(1-2), pp. 113-121 2015

© World Scientific-
**XML compression via DAGs**(with Mireille Bousquet-Mélou, Sebastian Maneth and Eric Nöth)

Theory of Computing Systems 57(4), pp. 1322-1371, 2015 (special issue for ICDT 2013)

© Springer **The first-order theory of ground tree rewrite graphs**(with Stefan Göller)

Logical Methods in Computer Science 10(1), paper 7, 2014

online version-
**XML tree structure compression using RePair**(with Sebastian Maneth and Roy Mennicke)

Information Systems 38(8), pp. 1150-1167, 2013

© Elsevier -
**The isomorphism problem on classes of automatic structures with transitive relations**(with Dietrich Kuske and Jiamou Liu)

Transactions of the American Mathematical Society 365, pp. 5103-5151, 2013

© AMS Press **Tree-automatic well-founded trees**(with Martin Huschenbett, Alexander Kartzow, and Jiamou Liu)

Logical Methods in Computer Science 9(2), paper 10, 2013-
**Branching-time model checking of one-counter processes and timed automata**(with Stefan Göller)

SIAM Journal on Computing 42(3), pp. 884-923, 2013

© SIAM -
**Isomorphism of regular trees and words**(with Christian Mathissen)

Information and Computation 224, pp. 71-105, 2013

© Elsevier -
**Compressed decision problems for graph products of groups and applications to (outer) automorphism groups**(with Niko Haubold and Christian Mathissen)

International Journal of Algebra and Computation 22(8), 2013

© World Scientific -
**The isomorphism problem for omega-automatic trees**(with Dietrich Kuske and Jiamou Liu)

Annals of Pure and Applied Logic 164(1), pp. 30-48, 2013

© Elsevier **Algorithmics on SLP-compressed strings: a survey**

Groups Complexity Cryptology 4(2), pp. 241-299, 2012

© De Gruyter-
**Logspace computations in Coxeter groups and graph groups**(with Volker Diekert and Jonathan Kausch)

Contemporary Mathematics 582 (Computational and Combinatorial Group Theory and Cryptography), pp. 77-94, 2012

© AMS Press -
**Parameter reduction and automata evaluation for grammar-compressed trees**(with Sebastian Maneth and Manfred Schmidt-Schauß)

Journal of Computer and System Sciences 78(5), pp. 1651-1669, 2012

© Elsevier -
**Model-checking hierarchical structures**

Journal of Computer and System Sciences 78(2), pp. 461-490, 2012

© Elsevier -
**Automatic structures of bounded degree revisited**(with Dietrich Kuske)

Journal of Symbolic Logic 76(4), pp. 1352-1380, 2011

© Association of Symbolic Logic -
**Compressed word problems in HNN-extensions and amalgamated products**(with Niko Haubold)

Theory of Computing Systems 49(2), pp. 283-305, 2011

© Springer -
**Leaf languages and string compression**

Information and Computation 209(6), pp. 951-965, 2011

© Elsevier **Tilings and submonoids of metabelian groups**(with Benjamin Steinberg)

Theory of Computing Systems 48(2), pp. 411-427, 2011

© Springer-
**Fixpoint logics on hierarchical structures**(with Stefan Göller)

Theory of Computing Systems 48(1), pp. 93-131, 2011

© Springer **Compressed membership problems for regular expressions and hierarchical automata**

International Journal of Foundations of Computer Science 21(5), pp. 817-841, 2010

© World Scientific**Submonoids and rational subsets of groups with infinitely many ends**(with Benjamin Steinberg)

Journal of Algebra 324(5), pp. 970-983, 2010

© Elsevier-
**Some natural decision problems in automatic graphs**(with Dietrich Kuske)

Journal of Symbolic Logic 75(2), pp. 678-710, 2010

© Association of Symbolic Logic **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-
**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 -
**Partially commutative inverse monoids**(with Volker Diekert and Alexander Miller)

Semigroup Forum 77(2), pp. 196-226, 2008

© Springer -
**Word equations over graph products**(with Volker Diekert)

International Journal of Algebra and Computation 18(3), pp. 493-533, 2008

© World Scientific -
**The submonoid and rational subset membership problems for graph groups**(with Benjamin Steinberg)

Journal of Algebra 320(2), pp. 728-755, 2008

© Elsevier -
**Efficient Memory Representation of XML Document Trees**(with Giorgio Busatto and Sebastian Maneth)

Information Systems 33(4-5), pp. 456-474, 2008

© Elsevier **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**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-
**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 -
**Inverse monoids: decidability and complexity of algebraic questions**(with Nicole Ondrusch)

Information and Computation 205(8), pp. 1212-1234, 2007

© Elsevier **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-
**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 -
**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 -
**Word problems and membership problems on compressed words**

SIAM Journal on Computing 35(5), pp. 1210-1240, 2006

© SIAM -
**Axiomatising divergence**(with Pedro D'Argenio and Holger Hermanns)

Information and Computation 203(2), pp. 115-144, 2005

© Elsevier -
**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 **Complexity results for prefix grammars**(with Holger Petersen)

RAIRO - Theoretical Informatics and Applications 39(2), pp. 389-399, 2005

© EDP Sciences-
**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 -
**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 -
**Bounded MSC communication**(with Anca Muscholl)

Information and Computation 189(2), pp. 160-181, 2004

© Elsevier -
**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 -
**Realizability of high-level message sequence charts: closing the gaps**

Theoretical Computer Science 309(1-3), pp. 529-554, 2003

© Elsevier **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**Confluence problems for trace rewriting**

Information and Computation 170, pp. 1-25, 2001

© Elsevier**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

**Sliding window property testing for regular languages**(with Moses Ganardi, Danny Hucke and Tatiana Starikovskaya)

to appear in Proceedings of ISAAC 2019**Balancing straight-line programs**(with Moses Ganardi and Artur Jez)

to appear in Proceedings of FOCS 2019

arxiv version**The power word problem**(with Armin Weiß)

Proceedings of MFCS 2019

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Combined compression of multiple correlated data streams for online-diagnosis systems**(with Seungbum Jo, Simon Meckel, Roman Obermaisser and Simon Plasger)

to appear in Proceedings of Euromicro DSD 2019**Largest common prefix of a regular tree languages**(with Sebastian Maneth)

Proceedings of FCT 2019, LNCS 11651, pp. 95-108

© Springer**Entropy bounds for grammar-based tree compressors**(with Danny Hucke and Louisa Seelbach)

to appear in Proceedings of ISIT 2019

© IEEE Computer Society Press arxiv version**Derandomization for sliding window algorithms with strict correctness**(with Moses Ganardi and Danny Hucke)

Proceedings of CSR 2019, LNCS 11532, pp. 237-249

© Springer journal version**Compressed decision problems in hyperbolic groups**(with Derek Holt and Saul Schleimer)

Proceedings of STACS 2019

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Knapsack in hyperbolic groups**

Proceedings of Reachability Problems 2018, LNCS 11123, pp. 87-102

© Springer arxiv version journal version**Average case analysis of leaf-centric binary tree sources**(with Louisa Seelbach)

Proceedings of MFCS 2018

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Sliding windows over context-free languages**(with Moses Ganardi and Artur Jez )

Proceedings of MFCS 2018

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik**Randomized sliding window algorithms for regular languages**(with Moses Ganardi and Danny Hucke)

Proceedings of ICALP 2018

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Grammar-based compression of unranked trees**(with Adria Gascon, Sebastian Maneth, Carl Philipp Reh and Kurt Sieber)

Proceedings of CSR 2018, LNCS 10846, pp. 118-131

© Springer arxiv version journal version**Knapsack problems for wreath products**(with Moses Ganardi, Daniel König and Georg Zetzsche)

Proceedings of STACS 2018

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Automata theory on sliding windows**(with Moses Ganardi, Danny Hucke, Daniel König and Konstantinos Mamouras)

Proceedings of STACS 2018

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Counting problems for Parikh images**(with Christoph Haase and Stefan Kiefer)

Proceedings of MFCS 2017

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**An architecture for online-diagnosis systems supporting compressed communication**(with Seungbum Jo, Damian Ludwig, Simon Meckel, Roman Obermaisser and Simon Plasger)

Proceedings of Euromicro DSD 2017, pp. 62-69

© IEEE Computer Society Press journal version**Universal tree source coding using grammar-based compression**(with Danny Hucke)

Proceedings of IEEE ISIT 2017, pp. 1753-1757

© IEEE Computer Society Press arxiv version journal version**Computing quantiles in Markov chains with multi-dimensional costs**(with Christoph Haase and Stefan Kiefer)

Proceedings of LICS 2017

© IEEE Computer Society Press**Circuit evaluation for finite semirings**(with Moses Ganardi, Danny Hucke and Daniel König)

Proceedings of STACS 2017

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version journal version**The complexity of knapsack in graph groups**(with Georg Zetzsche)

Proceedings of STACS 2017

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version**Compression of unordered XML trees**(with Sebastian Maneth and Carl Philipp Reh)

Proceedings of ICDT 2017

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik**Querying regular languages over sliding-windows**(with Moses Ganardi and Danny Hucke)

Proceedings of FSTTCS 2016

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik**The smallest grammar problem revisited**(with Danny Hucke and Carl Philipp Reh)

Proceedings of SPIRE 2016, LNCS 9954, pp. 35-49 (**Best paper award**)

© Springer journal version**On the parallel complexity of bisimulation over finite systems**(with Moses Ganardi and Stefan Göller)

Proceedings of CSL 2016

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik journal version**Traversing grammar-compressed trees with constant delay**(with Sebastian Maneth and Carl Philipp Reh)

Proceedings of DCC 2016, pp. 546-555

© IEEE Computer Society Press arxiv version journal version**Knapsack in graph groups, HNN-extensions and amalgamated products**(with Georg Zetzsche)

Proceedings of STACS 2016

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik

arxiv version**Tree compression using string grammars**(with Moses Ganardi, Danny Hucke and Eric Nöth)

Proceedings of LATIN 2016, LNCS 9644, pp. 590-604

© Springer arxiv version journal version**Parallel identity testing for skew circuits with big powers and applications**(with Daniel König)

Proceedings of MFCS 2015, LNCS 9235, pp. 445-458

© Springer arxiv version journal version**Path checking for MTL and TPTL over data words**(with Shiguang Feng and Karin Quaas)

Proceedings of DLT 2015, LNCS 9168, pp. 326-339

© Springer arxiv version journal version**Evaluating matrix circuits**(with Daniel König)

Proceedings of COCOON 2015, LNCS 9198, pp. 235-248

© Springer journal version**Compressed tree canonization**(with Sebastian Maneth and Fabian Peternek)

Proceedings of ICALP 2015, LNCS 9135, pp. 337-349

© Springer arxiv version**Satisfiability of ECTL with tree constraints**(with Claudia Carapelle, Alexander Kartzow and Shiguang Feng)

Proceedings of CSR 2015, LNCS 9139, pp. 94-108

© Springer arxiv version journal version**Constructing small tree grammars and small circuits for formulas**(with Danny Hucke and Eric Nöth)

Proceedings of FSTTCS 2014, pp. 457-468

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik arxiv version journal version**Processing succinct matrices and vectors**(with Manfred Schmidt-Schauß)

Proceedings of CSR 2014, LNCS 8476, pp. 245--258

© Springer arxiv version journal version**On Boolean closed full trios and rational Kripke frames**(with Georg Zetzsche)

Proceedings of STACS 2014, pp. 530-541

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik

journal version**Approximation of smallest linear tree grammars**(with Artur Jez)

Proceedings of STACS 2014, pp. 445-457

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik

journal version**Satisfiability of CTL* with constraints**(with Claudia Carapelle and Alexander Kartzow)

Proceedings of CONCUR 2013, LNCS 8052, pp. 455-469

© Springer journal version**Rational subsets and submonoids of wreath products**(with Benjamin Steinberg and Georg Zetzsche)

Proceedings of ICALP 2013, LNCS 7966, pp. 361-372

© Springer arxiv version journal version**Compression of rewriting systems for termination analysis**(with Alexander Bau, Eric Nöth and Johannes Waldmann)

Proceedings of RTA 2013, pp. 97-112

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik**XML compression via DAGs**(with Sebastian Maneth and Eric Nöth)

Proceedings of ICDT 2013, pp. 69-80

© ACM journal version**The complexity of decomposing modal and first-order theories**(with Stefan Göller and Jean Christoph Jung)

Proceedings of LICS 2012, pp. 325-334

© IEEE Computer Society Press journal version**Tree-automatic well-founded trees**(with Alexander Kartzow and Jiamou Liu)

Proceedings of CiE 2012, LNCS 7318, pp. 363-373

© Springer arxiv version journal version**Logspace computations in graph groups and Coxeter groups**(with Volker Diekert and Jonathan Kausch)

Proceedings of LATIN 2012, LNCS 7256, pp. 243-254

© Springer journal version**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 journal version**Compressed word problems for inverse monoids**

Proceedings of MFCS 2011, LNCS 6907, pp. 448-459

© Springer long version**Isomorphism of regular trees and words**(with Christian Mathissen)

Proceedings of ICALP 2011, LNCS 6756, pp. 210-221

© Springer journal version**Compressed membership in automata with compressed labels**(with Christian Mathissen)

Proceedings of CSR 2011, LNCS 6651, pp. 275-288

© Springer**Tree structure compression with RePair**(with Sebastian Maneth and Roy Mennicke)

Proceedings of DCC 2011, pp. 353-362

© IEEE Computer Society Press journal version very detailed version**The isomorphism problem for omega-automatic trees**(with Dietrich Kuske and Jiamou Liu)

Proceedings of CSL 2010, LNCS 6247, pp. 396-410

© Springer journal version**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)**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**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 journal version**Automatic structures of bounded degree revisited**(with Dietrich Kuske)

Proceedings of CSL 2009, LNCS 5771, pp. 364-378

© Springer journal version**Compressed word problems in HNN-extensions and amalgamated products**(with Niko Haubold)

Proceedings of CSR 2009, LNCS 5675, pp. 237-249

© Springer journal version**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**Leaf languages and string compression**

Proceedings of FSTTCS 2008, pp. 292-303

online version at Schloss Dagstuhl Leibniz-Zentrum für Informatik journal version**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)**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)**Efficient computation in groups via compression**(with Saul Schleimer)

Proceedings of CSR 2007, LNCS 4649, pp. 249-258

© Springer long version**The submonoid and rational subset membership problems for graph groups**(with Benjamin Steinberg)

Proceedings of LATA 2007, pp. 367-378

journal version**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)**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**Partially commutative inverse monoids**(with Volker Diekert and Alexander Miller)

Proceedings of MFCS 2006, LNCS 4162, pp. 292-304

© Springer journal version**Querying and embedding compressed texts**(with Yury Lifshits)

Proceedings of MFCS 2006, LNCS 4162, pp. 681-692

© Springer**Monadic chain logic over iterations and applications to pushdown systems**(with Dietrich Kuske)

Proceedings of LICS 2006, pp. 91-100

© IEEE Computer Society Press**Theories of HNN-extensions and amalgamated products**(with Géraud Sénizergues)

Proceedings of ICALP 2006, LNCS 4052, pp. 504-515

© Springer**First-order and counting theories of omega-automatic structures**(with Dietrich Kuske)

Proceedings of FOSSACS 2006, LNCS 3921, pp. 322-336

© Springer journal version**Fixpoint logics on hierarchical structures**(with Stefan Göller)

Proceedings of FSTTCS 2005, LNCS 3821, pp. 483-494

© Springer technical report journal version**Tree Automata and XPath on compressed trees**(with Sebastian Maneth)

Proceedings of CIAA 2005, LNCS 3845, pp. 225-237 (**Best paper award**)

© Springer journal version (The complexity of tree automata and XPath on grammar-compressed trees)**Efficient memory representation of XML documents**(with Giorgio Busatto and Sebastian Maneth)

Proceedings of DBPL 2005, LNCS 3774, pp. 199-216

© Springer journal version**Inverse monoids: decidability and complexity of algebraic questions**(with Nicole Ondrusch)

Proceedings of MFCS 2005, LNCS 3618, pp. 664-675

© Springer journal version**Model-checking hierarchical structures**

Proceedings of LICS 2005, pp. 168-177

© IEEE Computer Society Press journal version**Decidability and complexity in automatic monoids**

Proceedings of DLT 2004, LNCS 3340, pp. 308-320

© Springer journal version**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)**Word equations over graph products**(with Volker Diekert)

Proceedings of FSTTCS 2003, LNCS 2914, pp. 156-167

© Springer journal version**Automatic structures of bounded degree**

Proceedings of LPAR 2003, LNAI 2850, pp. 344-358

© Springer**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)**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)**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)**Axiomatising divergence**(with Pedro D'Argenio and Holger Hermanns)

Proceedings of ICALP 2002, LNCS 2380, pp. 585-596, 2002

© Springer journal version**Bounded MSC communication**(with Anca Muscholl)

Proceedings of FOSSACS 2002, LNCS 2303, pp. 295-309, 2002

© Springer journal version**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**Word problems for 2-homogeneous monoids and symmetric logspace**

Proceedings of MFCS 2001, LNCS 2136, pp. 500-511, 2001

© Springer**On the parallel complexity of tree automata**

Proceedings of RTA 2001, LNCS 2051, pp. 201-216, 2001

© Springer**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**Word problems and confluence problems for restricted semi-Thue systems**

Proceedings of RTA 2000, LNCS 1833, pp. 172-186, 2000

© Springer**Complexity results for confluence problems**

Proceedings of MFCS 99, LNCS 1672, pp. 114-124, 1999

© Springer long version**On the confluence of trace rewriting systems**

Proceedings of FSTTCS 98, LNCS 1530, pp. 319-330, 1998

© Springer long version**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

**Equations in HNN-extensions**

(with Géraud Sénizergues)**Positive theories of HNN-extensions and amalgamated free products**

(with Géraud Sénizergues)**Computational aspects of infinite monoids**

Habilitation thesis, Stuttgart, 2003**Das Konfluenzproblem für Spurersetzungssysteme**(in German)

PhD thesis, Stuttgart, 1999

Impressum