Edit Profile (opens in new tab) Lohrey, Markus Co-Author Distance Author ID: lohrey.markus Published as: Lohrey, Markus Documents Indexed: 168 Publications since 1998, including 2 Books and 6 Additional arXiv Preprints Co-Authors: 63 Co-Authors with 138 Joint Publications 1,385 Co-Co-Authors all top 5 Co-Authors 30 single-authored 21 Ganardi, Moses 18 Hucke, Danny 14 Kuske, Dietrich 14 Zetzsche, Georg 13 Göller, Stefan 13 Maneth, Sebastian 10 Diekert, Volker 9 König, Daniel 7 Reh, Carl Philipp 6 Jeż, Artur 6 Kartzow, Alexander 6 Nöth, Eric 6 Steinberg, Benjamin 5 Benkner, Louisa Seelbach 5 Carapelle, Claudia 5 Liu, Jiamou 5 Mathissen, Christian 4 Feng, Shiguang 4 Figelius, Michael 4 Haubold, Niko 4 Schmidt-Schauß, Manfred 3 Hermanns, Holger 3 Ondrusch, Nicole 3 Sénizergues, Géraud 3 Sieber, Kurt 2 D’Argenio, Pedro Rubén 2 Gascón, Adrià 2 Haase, Christoph 2 Jung, Jean Christoph 2 Kausch, Jonathan 2 Kiefer, Stefan 2 Lutz, Carsten 2 Miller, Alexander 2 Muscholl, Anca 2 Quaas, Karin 2 Rosowski, Andreas 2 Schleimer, Saul 2 Weiß, Armin 1 Bannai, Hideo 1 Bartholdi, Laurent 1 Bassino, Frédérique 1 Bau, Alexander 1 Bousquet-Mélou, Mireille 1 Busatto, Giorgio 1 Hirayama, Momoko 1 Holt, Derek F. 1 Huschenbett, Martin 1 Inenaga, Shunsuke 1 Kapovich, Ilya 1 Lifshits, Yury 1 Lück, Lukas 1 Mamouras, Konstantinos 1 Myasnikov, Alexei G. 1 Nicaud, Cyril 1 Peternek, Fabian 1 Petersen, Holger 1 Rivin, Igor 1 Shpilrain, Vladimir 1 Starikovskaya, Tatiana A. 1 Ushakov, Alexander S. 1 Waldmann, Johannes 1 Weil, Pascal 1 Xochitemol, Julio all top 5 Serials 12 Theory of Computing Systems 9 International Journal of Algebra and Computation 8 Information and Computation 6 Journal of Computer and System Sciences 4 Journal of Algebra 4 The Journal of Symbolic Logic 4 Logical Methods in Computer Science 3 IEEE Transactions on Information Theory 3 Algorithmica 2 SIAM Journal on Computing 2 Theoretical Computer Science 2 Annals of Pure and Applied Logic 2 International Journal of Foundations of Computer Science 2 ACM Transactions on Computation Theory 1 Communications in Algebra 1 Information Processing Letters 1 Acta Cybernetica 1 Proceedings of the American Mathematical Society 1 Semigroup Forum 1 Transactions of the American Mathematical Society 1 Journal of the ACM 1 RAIRO. Theoretical Informatics and Applications 1 ACM Transactions on Computational Logic 1 Groups, Complexity, Cryptology 1 SpringerBriefs in Mathematics all top 5 Fields 145 Computer science (68-XX) 57 Group theory and generalizations (20-XX) 53 Mathematical logic and foundations (03-XX) 9 Combinatorics (05-XX) 4 Operations research, mathematical programming (90-XX) 3 Associative rings and algebras (16-XX) 3 Information and communication theory, circuits (94-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 General algebraic systems (08-XX) 1 Probability theory and stochastic processes (60-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 131 Publications have been cited 766 times in 373 Documents Cited by ▼ Year ▼ Algorithmics on SLP-compressed strings: a survey. Zbl 1285.68088 Lohrey, Markus 44 2012 The compressed word problem for groups. Zbl 1391.20003 Lohrey, Markus 30 2014 Word problems and membership problems on compressed words. Zbl 1106.20043 Lohrey, Markus 27 2006 Logical aspects of Cayley-graphs: the group case. Zbl 1063.03005 Kuske, Dietrich; Lohrey, Markus 23 2005 The submonoid and rational subset membership problems for graph groups. Zbl 1156.20052 Lohrey, Markus; Steinberg, Benjamin 19 2008 Parameter reduction and automata evaluation for grammar-compressed trees. Zbl 1246.68114 Lohrey, Markus; Maneth, Sebastian; Schmidt-Schauß, Manfred 18 2012 The complexity of tree automata and XPath on grammar-compressed trees. Zbl 1153.68402 Lohrey, Markus; Maneth, Sebastian 17 2006 Word equations over graph products. Zbl 1186.20041 Diekert, Volker; Lohrey, Markus 15 2008 First-order and counting theories of \(\omega\)-automatic structures. Zbl 1141.03015 Kuske, Dietrich; Lohrey, Markus 14 2008 Decidability and complexity in automatic monoids. Zbl 1146.20314 Lohrey, Markus 14 2005 Efficient computation in groups via compression. Zbl 1188.20027 Lohrey, Markus; Schleimer, Saul 13 2007 Querying and embedding compressed texts. Zbl 1132.68379 Lifshits, Yury; Lohrey, Markus 12 2006 Evaluation of circuits over nilpotent and polycyclic groups. Zbl 1390.68311 König, Daniel; Lohrey, Markus 12 2018 Axiomatising divergence. Zbl 1110.68086 Lohrey, Markus; D’Argenio, Pedro R.; Hermanns, Holger 12 2005 XML compression via directed acyclic graphs. Zbl 1352.68079 Bousquet-Mélou, Mireille; Lohrey, Markus; Maneth, Sebastian; Noeth, Eric 12 2015 The rational subset membership problem for groups: a survey. Zbl 1346.20043 Lohrey, Markus 12 2015 Automata theory on sliding windows. Zbl 1487.68145 Ganardi, Moses; Hucke, Danny; König, Daniel; Lohrey, Markus; Mamouras, Konstantinos 12 2018 Bounded MSC communication. Zbl 1091.68006 Lohrey, Markus; Muscholl, Anca 11 2004 Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. Zbl 1392.68205 König, Daniel; Lohrey, Markus; Zetzsche, Georg 11 2016 Knapsack in graph groups. Zbl 1386.68073 Lohrey, Markus; Zetzsche, Georg 10 2018 Querying regular languages over sliding windows. Zbl 1391.68069 Ganardi, Moses; Hucke, Danny; Lohrey, Markus 10 2016 Logical aspects of Cayley-graphs: the monoid case. Zbl 1151.03003 Kuske, Dietrich; Lohrey, Markus 10 2006 The isomorphism problem on classes of automatic structures with transitive relations. Zbl 1308.03049 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 10 2013 Theories of HNN-extensions and amalgamated products. Zbl 1134.03009 Lohrey, Markus; Sénizergues, Géraud 9 2006 Tilings and submonoids of metabelian groups. Zbl 1229.20025 Lohrey, Markus; Steinberg, Benjamin 9 2011 Grammar-based tree compression. Zbl 1434.68130 Lohrey, Markus 9 2015 Rational subsets of unitriangular groups. Zbl 1330.20048 Lohrey, Markus 9 2015 Isomorphism of regular trees and words. Zbl 1295.68124 Lohrey, Markus; Mathissen, Christian 9 2013 When is a graph product of groups virtually-free? Zbl 1144.20012 Lohrey, Markus; Sénizergues, Géraud 8 2007 Rational subsets in HNN-extensions and amalgamated products. Zbl 1190.20019 Lohrey, Markus; Sénizergues, Géraud 8 2008 Automatic structures of bounded degree revisited. Zbl 1272.03148 Kuske, Dietrich; Lohrey, Markus 8 2011 On the parallel complexity of tree automata. Zbl 0981.68082 Lohrey, Markus 8 2001 Efficient memory representation of XML documents. Zbl 1159.68408 Busatto, Giorgio; Lohrey, Markus; Maneth, Sebastian 8 2005 Existential and positive theories of equations in graph products. Zbl 1067.03017 Diekert, Volker; Lohrey, Markus 8 2004 Evaluating matrix circuits. Zbl 1386.68061 König, Daniel; Lohrey, Markus 8 2015 Approximation of smallest linear tree grammar. Zbl 1359.68152 Jeż, Artur; Lohrey, Markus 8 2014 Knapsack problems for wreath products. Zbl 1491.20078 Ganardi, Moses; König, Daniel; Lohrey, Markus; Zetzsche, Georg 8 2018 Compressed decision problems in hyperbolic groups. Zbl 07559146 Holt, Derek; Lohrey, Markus; Schleimer, Saul 8 2019 Inverse monoids: decidability and complexity of algebraic questions. Zbl 1139.20054 Lohrey, Markus; Ondrusch, Nicole 7 2007 Compressed word problems in HNN-extensions and amalgamated products. Zbl 1235.68106 Haubold, Niko; Lohrey, Markus 7 2011 Priority and maximal progress are completely axiomatisable (extended abstract). Zbl 0940.68054 Hermanns, Holger; Lohrey, Markus 7 1998 PDL with intersection and converse: Satisfiability and infinite-state model checking. Zbl 1181.03034 Göller, Stefan; Lohrey, Markus; Lutz, Carsten 7 2009 Compressed decision problems for graph products and applications to (outer) automorphism groups. Zbl 1267.20050 Haubold, Niko; Lohrey, Markus; Mathissen, Christian 7 2012 Realizability of high-level message sequence charts: closing the gaps. Zbl 1070.68091 Lohrey, Markus 6 2003 Parallel identity testing for skew circuits with big powers and applications. Zbl 1400.68090 König, Daniel; Lohrey, Markus 6 2015 Knapsack in graph groups, HNN-extensions and amalgamated products. Zbl 1380.68229 Lohrey, Markus; Zetzsche, Georg 6 2016 Rational subsets and submonoids of wreath products. Zbl 1332.20038 Lohrey, Markus; Steinberg, Benjamin; Zetzsche, Georg 6 2015 Balancing straight-line programs. Zbl 1499.68162 Ganardi, Moses; Jeż, Artur; Lohrey, Markus 6 2021 Complexity and randomness in group theory. GAGTA book 1. Zbl 1515.20003 Bassino, Frédérique; Kapovich, Ilya; Lohrey, Markus; Miasnikov, Alexei; Nicaud, Cyril; Nikolaev, Andrey; Rivin, Igor; Shpilrain, Vladimir; Ushakov, Alexander; Weil, Pascal 6 2020 The smallest grammar problem revisited. Zbl 1397.68072 Hucke, Danny; Lohrey, Markus; Reh, Carl Philipp 6 2016 Satisfiability of \(\mathsf {ECTL}^*\) with tree constraints. Zbl 1435.03039 Carapelle, Claudia; Feng, Shiguang; Kartzow, Alexander; Lohrey, Markus 5 2015 Constructing small tree grammars and small circuits for formulas. Zbl 1360.68534 Hucke, Danny; Lohrey, Markus; Noeth, Eric 5 2014 Constructing small tree grammars and small circuits for formulas. Zbl 1370.68061 Ganardi, Moses; Hucke, Danny; Jeż, Artur; Lohrey, Markus; Noeth, Eric 5 2017 Safe realizability of high-level message sequence charts. Zbl 1012.68525 Lohrey, Markus 5 2002 Branching-time model checking of one-counter processes and timed automata. Zbl 1275.68092 Göller, Stefan; Lohrey, Markus 5 2013 The isomorphism problem for \(\omega \)-automatic trees. Zbl 1287.03084 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 5 2010 The power word problem. Zbl 07561687 Lohrey, Markus; Weiß, Armin 5 2019 Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. Zbl 07561757 Bartholdi, Laurent; Figelius, Michael; Lohrey, Markus; Weiß, Armin 5 2020 Some natural decision problems in automatic graphs. Zbl 1192.03010 Kuske, Dietrich; Lohrey, Markus 4 2010 Axiomatising divergence. Zbl 1057.68069 Lohrey, Markus; D’Argenio, Pedro R.; Hermanns, Holger 4 2002 Infinite state model-checking of propositional dynamic logics. Zbl 1225.68116 Göller, Stefan; Lohrey, Markus 4 2006 Word problems on compressed words. Zbl 1099.68646 Lohrey, Markus 4 2004 Logspace computations in graph groups and Coxeter groups. Zbl 1283.20043 Diekert, Volker; Kausch, Jonathan; Lohrey, Markus 4 2012 Knapsack in hyperbolic groups. Zbl 1485.20085 Lohrey, Markus 4 2020 Satisfiability of \(\mathrm{CTL}^{*}\) with constraints. Zbl 1391.03017 Carapelle, Claudia; Kartzow, Alexander; Lohrey, Markus 4 2013 Logspace computations in Coxeter groups and graph groups. Zbl 1283.20044 Diekert, Volker; Kausch, Jonathan; Lohrey, Markus 4 2012 Compressed membership problems for regular expressions and hierarchical automata. Zbl 1213.68355 Lohrey, Markus 4 2010 Knapsack and the power word problem in solvable Baumslag-Solitar groups. Zbl 07559438 Lohrey, Markus; Zetzsche, Georg 4 2020 Parallel identity testing for skew circuits with big powers and applications. Zbl 1400.68091 König, Daniel; Lohrey, Markus 4 2018 Grammar-based compression of unranked trees. Zbl 1434.68128 Gascón, Adrià; Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp; Sieber, Kurt 4 2018 Leaf languages and string compression. Zbl 1221.68138 Lohrey, Markus 3 2011 Tree compression using string grammars. Zbl 1384.68016 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Noeth, Eric 3 2018 Word equations over graph products. Zbl 1188.20066 Diekert, Volker; Lohrey, Markus 3 2003 Fixpoint logics on hierarchical structures. Zbl 1172.68542 Göller, Stefan; Lohrey, Markus 3 2005 Parameter reduction in grammar-compressed trees. Zbl 1234.68182 Lohrey, Markus; Maneth, Sebastian; Schmidt-Schauß, Manfred 3 2009 Tree-automatic well-founded trees. Zbl 1358.03042 Kartzow, Alexander; Liu, Jiamou; Lohrey, Markus 3 2012 Compressed tree canonization. Zbl 1440.68148 Lohrey, Markus; Maneth, Sebastian; Peternek, Fabian 3 2015 Path checking for MTL and TPTL over data words. Zbl 1434.68297 Feng, Shiguang; Lohrey, Markus; Quaas, Karin 3 2015 The complexity of decomposing modal and first-order theories. Zbl 1364.03031 Göller, Stefan; Jung, Jean Christoph; Lohrey, Markus 3 2012 Sliding window property testing for regular languages. Zbl 07650239 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Starikovskaya, Tatiana 3 2019 Compression of unordered XML trees. Zbl 1402.68059 Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp 3 2017 First-order and counting theories of \(\omega\)-automatic structures. Zbl 1138.03032 Kuske, Dietrich; Lohrey, Markus 2 2006 Partially commutative inverse monoids. Zbl 1132.20308 Diekert, Volker; Lohrey, Markus; Miller, Alexander 2 2006 PDL with intersection and converse is 2EXP-complete. Zbl 1180.03033 Göller, Stefan; Lohrey, Markus; Lutz, Carsten 2 2007 Algorithmic problems on inverse monoids over virtually free groups. Zbl 1190.20045 Diekert, Volker; Ondrusch, Nicole; Lohrey, Markus 2 2008 Branching-time model checking of one-counter processes. Zbl 1230.68142 Göller, Stefan; Lohrey, Markus 2 2010 Model-checking hierarchical structures. Zbl 1279.68213 Lohrey, Markus 2 2012 Compressed membership in automata with compressed labels. Zbl 1319.68137 Lohrey, Markus; Mathissen, Christian 2 2011 The complexity of knapsack in graph groups. Zbl 1402.68103 Lohrey, Markus; Zetzsche, Georg 2 2017 Tree automata and XPath on compressed trees. Zbl 1172.68517 Lohrey, Markus; Maneth, Sebastian 2 2006 Approximation of smallest linear tree grammar. Zbl 1353.68154 Jeż, Artur; Lohrey, Markus 2 2016 Satisfiability of \(\mathrm{ECTL}^*\) with local tree constraints. Zbl 1435.03040 Carapelle, Claudia; Feng, Shiguang; Kartzow, Alexander; Lohrey, Markus 2 2017 Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints. Zbl 1358.03032 Carapelle, Claudia; Kartzow, Alexander; Lohrey, Markus 2 2016 Tree compression using string grammars. Zbl 1370.68062 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Noeth, Eric 2 2016 On Boolean closed full trios and rational Kripke frames. Zbl 1359.68174 Lohrey, Markus; Zetzsche, Georg 2 2014 Decidable theories of Cayley-graphs. Zbl 1036.03009 Kuske, Dietrich; Lohrey, Markus 2 2003 A note on the existential theory of equations in plain groups. Zbl 1007.03008 Diekert, Volker; Lohrey, Markus 2 2002 Constant-time tree traversal and subtree equality check for grammar-compressed trees. Zbl 1392.68185 Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp 2 2018 The isomorphism problem for \(\omega \)-automatic trees. Zbl 1273.03125 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 2 2013 Submonoids and rational subsets of groups with infinitely many ends. Zbl 1239.20038 Lohrey, Markus; Steinberg, Benjamin 2 2010 Knapsack and the power word problem in solvable Baumslag-Solitar groups. Zbl 1516.20066 Ganardi, Moses; Lohrey, Markus; Zetzsche, Georg 2 2023 Closure properties of knapsack semilinear groups. Zbl 1512.20105 Figelius, Michael; Lohrey, Markus; Zetzsche, Georg 1 2022 Balancing straight-line programs. Zbl 1499.68162 Ganardi, Moses; Jeż, Artur; Lohrey, Markus 6 2021 Compression techniques in group theory. Zbl 07495180 Lohrey, Markus 1 2021 Complexity and randomness in group theory. GAGTA book 1. Zbl 1515.20003 Bassino, Frédérique; Kapovich, Ilya; Lohrey, Markus; Miasnikov, Alexei; Nicaud, Cyril; Nikolaev, Andrey; Rivin, Igor; Shpilrain, Vladimir; Ushakov, Alexander; Weil, Pascal 6 2020 Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. Zbl 07561757 Bartholdi, Laurent; Figelius, Michael; Lohrey, Markus; Weiß, Armin 5 2020 Knapsack in hyperbolic groups. Zbl 1485.20085 Lohrey, Markus 4 2020 Knapsack and the power word problem in solvable Baumslag-Solitar groups. Zbl 07559438 Lohrey, Markus; Zetzsche, Georg 4 2020 Compressed decision problems in hyperbolic groups. Zbl 07559146 Holt, Derek; Lohrey, Markus; Schleimer, Saul 8 2019 The power word problem. Zbl 07561687 Lohrey, Markus; Weiß, Armin 5 2019 Sliding window property testing for regular languages. Zbl 07650239 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Starikovskaya, Tatiana 3 2019 Derandomization for sliding window algorithms with strict correctness. Zbl 1517.68421 Ganardi, Moses; Hucke, Danny; Lohrey, Markus 1 2019 Universal tree source coding using grammar-based compression. Zbl 1432.94072 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Benkner, Louisa Seelbach 1 2019 Size-optimal top dag compression. Zbl 1473.68061 Lohrey, Markus; Reh, Carl Philipp; Sieber, Kurt 1 2019 Largest common prefix of a regular tree language. Zbl 07160829 Lohrey, Markus; Maneth, Sebastian 1 2019 Evaluation of circuits over nilpotent and polycyclic groups. Zbl 1390.68311 König, Daniel; Lohrey, Markus 12 2018 Automata theory on sliding windows. Zbl 1487.68145 Ganardi, Moses; Hucke, Danny; König, Daniel; Lohrey, Markus; Mamouras, Konstantinos 12 2018 Knapsack in graph groups. Zbl 1386.68073 Lohrey, Markus; Zetzsche, Georg 10 2018 Knapsack problems for wreath products. Zbl 1491.20078 Ganardi, Moses; König, Daniel; Lohrey, Markus; Zetzsche, Georg 8 2018 Parallel identity testing for skew circuits with big powers and applications. Zbl 1400.68091 König, Daniel; Lohrey, Markus 4 2018 Grammar-based compression of unranked trees. Zbl 1434.68128 Gascón, Adrià; Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp; Sieber, Kurt 4 2018 Tree compression using string grammars. Zbl 1384.68016 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Noeth, Eric 3 2018 Constant-time tree traversal and subtree equality check for grammar-compressed trees. Zbl 1392.68185 Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp 2 2018 Randomized sliding window algorithms for regular languages. Zbl 1499.68175 Ganardi, Moses; Hucke, Danny; Lohrey, Markus 2 2018 Sliding windows over context-free languages. Zbl 1510.68121 Ganardi, Moses; Jez, Artur; Lohrey, Markus 2 2018 Average case analysis of leaf-centric binary tree sources. Zbl 1510.68019 Seelbach Benkner, Louisa; Lohrey, Markus 2 2018 Sliding window algorithms for regular languages. Zbl 1504.68100 Ganardi, Moses; Hucke, Danny; Lohrey, Markus 2 2018 Knapsack in hyperbolic groups. Zbl 1515.68153 Lohrey, Markus 2 2018 Constructing small tree grammars and small circuits for formulas. Zbl 1370.68061 Ganardi, Moses; Hucke, Danny; Jeż, Artur; Lohrey, Markus; Noeth, Eric 5 2017 Compression of unordered XML trees. Zbl 1402.68059 Lohrey, Markus; Maneth, Sebastian; Reh, Carl Philipp 3 2017 The complexity of knapsack in graph groups. Zbl 1402.68103 Lohrey, Markus; Zetzsche, Georg 2 2017 Satisfiability of \(\mathrm{ECTL}^*\) with local tree constraints. Zbl 1435.03040 Carapelle, Claudia; Feng, Shiguang; Kartzow, Alexander; Lohrey, Markus 2 2017 Path checking for MTL and TPTL over data words. Zbl 1459.68118 Feng, Shiguang; Lohrey, Markus; Quaas, Karin 1 2017 Computing quantiles in Markov chains with multi-dimensional costs. Zbl 1457.68112 Haase, Christoph; Kiefer, Stefan; Lohrey, Markus 1 2017 Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. Zbl 1392.68205 König, Daniel; Lohrey, Markus; Zetzsche, Georg 11 2016 Querying regular languages over sliding windows. Zbl 1391.68069 Ganardi, Moses; Hucke, Danny; Lohrey, Markus 10 2016 Knapsack in graph groups, HNN-extensions and amalgamated products. Zbl 1380.68229 Lohrey, Markus; Zetzsche, Georg 6 2016 The smallest grammar problem revisited. Zbl 1397.68072 Hucke, Danny; Lohrey, Markus; Reh, Carl Philipp 6 2016 Approximation of smallest linear tree grammar. Zbl 1353.68154 Jeż, Artur; Lohrey, Markus 2 2016 Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints. Zbl 1358.03032 Carapelle, Claudia; Kartzow, Alexander; Lohrey, Markus 2 2016 Tree compression using string grammars. Zbl 1370.68062 Ganardi, Moses; Hucke, Danny; Lohrey, Markus; Noeth, Eric 2 2016 XML compression via directed acyclic graphs. Zbl 1352.68079 Bousquet-Mélou, Mireille; Lohrey, Markus; Maneth, Sebastian; Noeth, Eric 12 2015 The rational subset membership problem for groups: a survey. Zbl 1346.20043 Lohrey, Markus 12 2015 Grammar-based tree compression. Zbl 1434.68130 Lohrey, Markus 9 2015 Rational subsets of unitriangular groups. Zbl 1330.20048 Lohrey, Markus 9 2015 Evaluating matrix circuits. Zbl 1386.68061 König, Daniel; Lohrey, Markus 8 2015 Parallel identity testing for skew circuits with big powers and applications. Zbl 1400.68090 König, Daniel; Lohrey, Markus 6 2015 Rational subsets and submonoids of wreath products. Zbl 1332.20038 Lohrey, Markus; Steinberg, Benjamin; Zetzsche, Georg 6 2015 Satisfiability of \(\mathsf {ECTL}^*\) with tree constraints. Zbl 1435.03039 Carapelle, Claudia; Feng, Shiguang; Kartzow, Alexander; Lohrey, Markus 5 2015 Compressed tree canonization. Zbl 1440.68148 Lohrey, Markus; Maneth, Sebastian; Peternek, Fabian 3 2015 Path checking for MTL and TPTL over data words. Zbl 1434.68297 Feng, Shiguang; Lohrey, Markus; Quaas, Karin 3 2015 The complexity of decomposing modal and first-order theories. Zbl 1354.03053 Göller, Stefan; Jung, Jean-Christoph; Lohrey, Markus 1 2015 Temporal logics with local constraints (invited talk). Zbl 1373.03020 Carapelle, Claudia; Lohrey, Markus 1 2015 The compressed word problem for groups. Zbl 1391.20003 Lohrey, Markus 30 2014 Approximation of smallest linear tree grammar. Zbl 1359.68152 Jeż, Artur; Lohrey, Markus 8 2014 Constructing small tree grammars and small circuits for formulas. Zbl 1360.68534 Hucke, Danny; Lohrey, Markus; Noeth, Eric 5 2014 On Boolean closed full trios and rational Kripke frames. Zbl 1359.68174 Lohrey, Markus; Zetzsche, Georg 2 2014 The first-order theory of ground tree rewrite graphs. Zbl 1325.68121 Göller, Stefan; Lohrey, Markus 1 2014 The isomorphism problem on classes of automatic structures with transitive relations. Zbl 1308.03049 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 10 2013 Isomorphism of regular trees and words. Zbl 1295.68124 Lohrey, Markus; Mathissen, Christian 9 2013 Branching-time model checking of one-counter processes and timed automata. Zbl 1275.68092 Göller, Stefan; Lohrey, Markus 5 2013 Satisfiability of \(\mathrm{CTL}^{*}\) with constraints. Zbl 1391.03017 Carapelle, Claudia; Kartzow, Alexander; Lohrey, Markus 4 2013 The isomorphism problem for \(\omega \)-automatic trees. Zbl 1273.03125 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 2 2013 Tree-automatic well-founded trees. Zbl 1297.03024 Huschenbett, Martin; Kartzow, Alexander; Liu, Jiamou; Lohrey, Markus 1 2013 Rational subsets and submonoids of wreath products. Zbl 1293.20036 Lohrey, Markus; Steinberg, Benjamin; Zetzsche, Georg 1 2013 Algorithmics on SLP-compressed strings: a survey. Zbl 1285.68088 Lohrey, Markus 44 2012 Parameter reduction and automata evaluation for grammar-compressed trees. Zbl 1246.68114 Lohrey, Markus; Maneth, Sebastian; Schmidt-Schauß, Manfred 18 2012 Compressed decision problems for graph products and applications to (outer) automorphism groups. Zbl 1267.20050 Haubold, Niko; Lohrey, Markus; Mathissen, Christian 7 2012 Logspace computations in graph groups and Coxeter groups. Zbl 1283.20043 Diekert, Volker; Kausch, Jonathan; Lohrey, Markus 4 2012 Logspace computations in Coxeter groups and graph groups. Zbl 1283.20044 Diekert, Volker; Kausch, Jonathan; Lohrey, Markus 4 2012 Tree-automatic well-founded trees. Zbl 1358.03042 Kartzow, Alexander; Liu, Jiamou; Lohrey, Markus 3 2012 The complexity of decomposing modal and first-order theories. Zbl 1364.03031 Göller, Stefan; Jung, Jean Christoph; Lohrey, Markus 3 2012 Model-checking hierarchical structures. Zbl 1279.68213 Lohrey, Markus 2 2012 Tilings and submonoids of metabelian groups. Zbl 1229.20025 Lohrey, Markus; Steinberg, Benjamin 9 2011 Automatic structures of bounded degree revisited. Zbl 1272.03148 Kuske, Dietrich; Lohrey, Markus 8 2011 Compressed word problems in HNN-extensions and amalgamated products. Zbl 1235.68106 Haubold, Niko; Lohrey, Markus 7 2011 Leaf languages and string compression. Zbl 1221.68138 Lohrey, Markus 3 2011 Compressed membership in automata with compressed labels. Zbl 1319.68137 Lohrey, Markus; Mathissen, Christian 2 2011 Compressed word problems for inverse monoids. Zbl 1343.68145 Lohrey, Markus 1 2011 Isomorphism of regular trees and words. Zbl 1333.68126 Lohrey, Markus; Mathissen, Christian 1 2011 Compression of rewriting systems for termination analysis. Zbl 1356.68116 Bau, Alexander; Lohrey, Markus; Nöth, Eric; Waldmann, Johannes 1 2011 The isomorphism problem for \(\omega \)-automatic trees. Zbl 1287.03084 Kuske, Dietrich; Liu, Jiamou; Lohrey, Markus 5 2010 Some natural decision problems in automatic graphs. Zbl 1192.03010 Kuske, Dietrich; Lohrey, Markus 4 2010 Compressed membership problems for regular expressions and hierarchical automata. Zbl 1213.68355 Lohrey, Markus 4 2010 Branching-time model checking of one-counter processes. Zbl 1230.68142 Göller, Stefan; Lohrey, Markus 2 2010 Submonoids and rational subsets of groups with infinitely many ends. Zbl 1239.20038 Lohrey, Markus; Steinberg, Benjamin 2 2010 PDL with intersection and converse: Satisfiability and infinite-state model checking. Zbl 1181.03034 Göller, Stefan; Lohrey, Markus; Lutz, Carsten 7 2009 Parameter reduction in grammar-compressed trees. Zbl 1234.68182 Lohrey, Markus; Maneth, Sebastian; Schmidt-Schauß, Manfred 3 2009 Automatic structures of bounded degree revisited. Zbl 1257.03032 Kuske, Dietrich; Lohrey, Markus 1 2009 The submonoid and rational subset membership problems for graph groups. Zbl 1156.20052 Lohrey, Markus; Steinberg, Benjamin 19 2008 Word equations over graph products. Zbl 1186.20041 Diekert, Volker; Lohrey, Markus 15 2008 First-order and counting theories of \(\omega\)-automatic structures. Zbl 1141.03015 Kuske, Dietrich; Lohrey, Markus 14 2008 Rational subsets in HNN-extensions and amalgamated products. Zbl 1190.20019 Lohrey, Markus; Sénizergues, Géraud 8 2008 Algorithmic problems on inverse monoids over virtually free groups. Zbl 1190.20045 Diekert, Volker; Ondrusch, Nicole; Lohrey, Markus 2 2008 Leaf languages and string compression. Zbl 1248.68311 Lohrey, Markus 1 2008 Partially commutative inverse monoids. Zbl 1156.20049 Diekert, Volker; Lohrey, Markus; Miller, Alexander 1 2008 Efficient computation in groups via compression. Zbl 1188.20027 Lohrey, Markus; Schleimer, Saul 13 2007 When is a graph product of groups virtually-free? Zbl 1144.20012 Lohrey, Markus; Sénizergues, Géraud 8 2007 Inverse monoids: decidability and complexity of algebraic questions. Zbl 1139.20054 Lohrey, Markus; Ondrusch, Nicole 7 2007 PDL with intersection and converse is 2EXP-complete. Zbl 1180.03033 Göller, Stefan; Lohrey, Markus; Lutz, Carsten 2 2007 ...and 31 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 498 Authors 74 Lohrey, Markus 13 Jeż, Artur 13 Kuske, Dietrich 13 Myasnikov, Alexei G. 11 Diekert, Volker 11 Zetzsche, Georg 10 Bollig, Benedikt 10 Maneth, Sebastian 10 Weiß, Armin 8 Schmidt-Schauß, Manfred 7 Ganardi, Moses 6 Gray, Robert D. 6 Inenaga, Shunsuke 6 Stephan, Frank 5 Gagie, Travis 5 Gastin, Paul 5 Genest, Blaise 5 Göller, Stefan 5 Holt, Derek F. 5 Kartzow, Alexander 5 König, Daniel 5 Muscholl, Anca 5 Seidl, Helmut 5 Steinberg, Benjamin 5 Ushakov, Alexander S. 4 Bille, Philip 4 Ciobanu, Laura 4 Finkel, Olivier 4 Fu, Yuxi 4 Hucke, Danny 4 Jain, Sanjay 4 Kharlampovich, Olga G. 4 Khoussainov, Bakhadyr M. 4 Navarro, Gonzalo 4 Okhotin, Alexander 4 Rees, Sarah 4 Sangnier, Arnaud 4 Semukhin, Pavel 4 Silva, Pedro V. 4 van Glabbeek, Robert Jan 4 Weimann, Oren 4 Abu Zaid, Faried 3 Bell, Paul C. 3 Bravetti, Mario 3 Carapelle, Claudia 3 Demri, Stéphane P. 3 Feng, Shiguang 3 Fortin, Marie-Josée 3 Gawrychowski, Paweł 3 Gørtz, Inge Li 3 Haubold, Niko 3 Hermanns, Holger 3 Jeandel, Emmanuel 3 Kaiser, Lukasz 3 Kosche, Maria 3 Koss, Tore 3 Landau, Gad M. 3 Löbel, Raphaela 3 Luttenberger, Michael 3 Manea, Florin 3 Mathissen, Christian 3 Nöth, Eric 3 Potapov, Igor 3 Quaas, Karin 3 Reh, Carl Philipp 3 Schlicht, Philipp 3 Tiskin, Alexandre 3 Varghese, Olga 3 Vassileva, Svetla 3 Wallner, Michael 2 Aubrun, Nathalie 2 Baader, Franz 2 Bannai, Hideo 2 Bárány, Vince 2 Barbieri, Sebastián 2 Barth, Dominik 2 Beck, Moritz 2 Benkner, Louisa Seelbach 2 Bertoni, Alberto 2 Cain, Alan J. 2 Casals-Ruiz, Montserrat 2 Cenzer, Douglas 2 Choffrut, Christian 2 Dhar, Amit Kumar 2 Dolinka, Igor 2 Dose, Titus 2 Eberhard, Sebastian 2 Elder, Murray J. 2 Elkind, Edith 2 Engelfriet, Joost 2 Figelius, Michael 2 Filiot, Emmanuel 2 Fleischer, Lukas 2 Fujiyoshi, Akio 2 Garreta, Albert 2 Gascón, Adrià 2 Gelle, Kitti 2 Genitrini, Antoine 2 Gittenberger, Bernhard 2 Glaßer, Christian ...and 398 more Authors all top 5 Cited in 70 Serials 28 Information and Computation 25 Theoretical Computer Science 23 Theory of Computing Systems 22 International Journal of Algebra and Computation 18 Journal of Algebra 13 Journal of Computer and System Sciences 9 Logical Methods in Computer Science 8 Algorithmica 8 International Journal of Foundations of Computer Science 6 Information Processing Letters 5 The Journal of Symbolic Logic 5 Semigroup Forum 4 Journal of Symbolic Computation 4 Formal Methods in System Design 4 Groups, Complexity, Cryptology 3 Communications in Algebra 3 Israel Journal of Mathematics 3 Mathematics of Computation 3 Journal of Combinatorial Theory. Series A 3 Transactions of the American Mathematical Society 3 Journal of Logical and Algebraic Methods in Programming 2 Acta Informatica 2 Discrete Mathematics 2 Algebra and Logic 2 Proceedings of the American Mathematical Society 2 SIAM Journal on Computing 2 Siberian Mathematical Journal 2 European Journal of Combinatorics 2 Annals of Pure and Applied Logic 2 Journal of Automated Reasoning 2 Formal Aspects of Computing 2 MSCS. Mathematical Structures in Computer Science 2 Journal of Mathematical Sciences (New York) 2 Izvestiya: Mathematics 2 Journal of Group Theory 2 ACM Transactions on Computational Logic 2 Journal of Algebra and its Applications 2 Journal of Discrete Algorithms 2 Journal of Applied Logic 2 Bulletin of Mathematical Sciences 1 Communications in Mathematical Physics 1 Advances in Mathematics 1 Bulletin of the London Mathematical Society 1 Canadian Mathematical Bulletin 1 Geometriae Dedicata 1 Information Sciences 1 Inventiones Mathematicae 1 Memoirs of the American Mathematical Society 1 Studia Logica 1 Synthese 1 Discrete & Computational Geometry 1 Random Structures & Algorithms 1 Discrete Mathematics and Applications 1 International Journal of Computer Mathematics 1 Computational Complexity 1 Journal of Logic, Language and Information 1 Journal of Applied Non-Classical Logics 1 Topology Proceedings 1 The Electronic Journal of Combinatorics 1 Fundamenta Informaticae 1 Algebraic & Geometric Topology 1 Journal of the Australian Mathematical Society 1 Central European Journal of Mathematics 1 Sibirskie Èlektronnye Matematicheskie Izvestiya 1 Groups, Geometry, and Dynamics 1 Journal of Topology and Analysis 1 Algorithms 1 RAIRO. Theoretical Informatics and Applications 1 Computability 1 Prikladnaya Diskretnaya Matematika all top 5 Cited in 25 Fields 287 Computer science (68-XX) 118 Group theory and generalizations (20-XX) 97 Mathematical logic and foundations (03-XX) 35 Combinatorics (05-XX) 6 Information and communication theory, circuits (94-XX) 5 Number theory (11-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Manifolds and cell complexes (57-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Functional analysis (46-XX) 2 Geometry (51-XX) 2 Operations research, mathematical programming (90-XX) 1 General algebraic systems (08-XX) 1 Commutative algebra (13-XX) 1 Associative rings and algebras (16-XX) 1 Category theory; homological algebra (18-XX) 1 Topological groups, Lie groups (22-XX) 1 Abstract harmonic analysis (43-XX) 1 Differential geometry (53-XX) 1 General topology (54-XX) 1 Probability theory and stochastic processes (60-XX) 1 Numerical analysis (65-XX) 1 Quantum theory (81-XX) Citations by Year