Markus Lohrey

According to our database1, Markus Lohrey
  • authored at least 166 papers between 1998 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
On Boolean Closed Full Trios and Rational Kripke Frames.
Theory Comput. Syst., 2017

Processing Succinct Matrices and Vectors.
Theory Comput. Syst., 2017

Satisfiability of ECTL∗ with Local Tree Constraints.
Theory Comput. Syst., 2017

Constructing small tree grammars and small circuits for formulas.
J. Comput. Syst. Sci., 2017

Knapsack Problems for Wreath Products.
CoRR, 2017

Universal Tree Source Coding Using Grammar-Based Compression.
CoRR, 2017

Approximation ratio of RePair.
CoRR, 2017

A universal tree balancing theorem.
CoRR, 2017

Querying languages over sliding windows.
CoRR, 2017

The Complexity of Knapsack in Graph Groups.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Circuit Evaluation for Finite Semirings.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Counting Problems for Parikh Images.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Computing quantiles in Markov chains with multi-dimensional costs.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Universal tree source coding using grammar-based compression.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Compression of Unordered XML Trees.
Proceedings of the 20th International Conference on Database Theory, 2017

An Architecture for Online-Diagnosis Systems Supporting Compressed Communication.
Proceedings of the Euromicro Conference on Digital System Design, 2017

2016
Satisfiability of ECTL with constraints.
J. Comput. Syst. Sci., 2016

Approximation of smallest linear tree grammar.
Inf. Comput., 2016

Computation over Compressed Structured Data (Dagstuhl Seminar 16431).
Dagstuhl Reports, 2016

The Complexity of Knapsack in Graph Groups.
CoRR, 2016

Efficient Quantile Computation in Markov Chains via Counting Problems for Parikh Images.
CoRR, 2016

Circuit Evaluation for Finite Semirings.
CoRR, 2016

Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Smallest Grammar Problem Revisited.
Proceedings of the String Processing and Information Retrieval, 2016

Tree Compression Using String Grammars.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Querying Regular Languages over Sliding Windows.
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Traversing Grammar-Compressed Trees with Constant Delay.
Proceedings of the 2016 Data Compression Conference, 2016

On the Parallel Complexity of Bisimulation on Finite Systems.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015
The Complexity of Decomposing Modal and First-Order Theories.
ACM Trans. Comput. Log., 2015

XML Compression via Directed Acyclic Graphs.
Theory Comput. Syst., 2015

Rational subsets of unitriangular groups.
IJAC, 2015

Rational subsets and submonoids of wreath products.
Inf. Comput., 2015

Knapsack in graph groups, HNN-extensions and amalgamated products.
CoRR, 2015

Traversing Grammar-Compressed Trees with Constant Delay.
CoRR, 2015

Compressed Tree Canonization.
CoRR, 2015

Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups.
CoRR, 2015

Parallel Identity Testing for Skew Circuits with Big Powers and Applications.
CoRR, 2015

Evaluating Matrix Circuits.
CoRR, 2015

Tree compression using string grammars.
CoRR, 2015

Parallel Identity Testing for Skew Circuits with Big Powers and Applications.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Compressed Tree Canonization.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Grammar-Based Tree Compression.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Path Checking for MTL and TPTL over Data Words.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Equality Testing of Compressed Strings.
Proceedings of the Combinatorics on Words - 10th International Conference, 2015

Satisfiability of ECTL* with Tree Constraints.
Proceedings of the Computer Science - Theory and Applications, 2015

Temporal Logics with Local Constraints (Invited Talk).
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

Evaluating Matrix Circuits.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014
The First-Order Theory of Ground Tree Rewrite Graphs
Logical Methods in Computer Science, 2014

Processing Succinct Matrices and Vectors.
CoRR, 2014

Constructing small tree grammars and small circuits for formulas.
CoRR, 2014

Path-Checking for MTL and TPTL over Data Words.
CoRR, 2014

Satisfiability of ECTL* with tree constraints.
CoRR, 2014

On Boolean closed full trios and rational Kripke frames.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Approximation of smallest linear tree grammar.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Constructing Small Tree Grammars and Small Circuits for Formulas.
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Processing Succinct Matrices and Vectors.
Proceedings of the Computer Science - Theory and Applications, 2014

The Compressed Word Problem for Groups.
Springer Briefs in Mathematics, Springer, ISBN: 978-1-4939-0747-2, 2014

2013
Branching-Time Model Checking of One-Counter Processes and Timed Automata.
SIAM J. Comput., 2013

XML tree structure compression using RePair.
Inf. Syst., 2013

Isomorphism of regular trees and words.
Inf. Comput., 2013

Rational Subsets and Submonoids of Wreath Products
CoRR, 2013

Tree-Automatic Well-Founded Trees
Logical Methods in Computer Science, 2013

Approximation of smallest linear tree grammar.
CoRR, 2013

Satisfiability of CTL* with constraints.
CoRR, 2013

XML Compression via DAGs.
CoRR, 2013

The isomorphism problem for ω-automatic trees.
Ann. Pure Appl. Logic, 2013

Compression of Rewriting Systems for Termination Analysis.
Proceedings of the 24th International Conference on Rewriting Techniques and Applications, 2013

XML compression via DAGs.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Rational Subsets and Submonoids of Wreath Products.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Satisfiability of CTL* with Constraints.
Proceedings of the CONCUR 2013 - Concurrency Theory - 24th International Conference, 2013

2012
Parameter reduction and automata evaluation for grammar-compressed trees.
J. Comput. Syst. Sci., 2012

Model-checking hierarchical structures.
J. Comput. Syst. Sci., 2012

Compressed Decision Problems for Graph Products and Applications to (outer) Automorphism Groups.
IJAC, 2012

Algorithmics on SLP-compressed strings: A survey.
Groups Complexity Cryptology, 2012

The Complexity of Decomposing Modal and First-Order Theories.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Logspace Computations in Graph Groups and Coxeter Groups.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Tree-Automatic Well-Founded Trees.
Proceedings of the How the World Computes, 2012

2011
Tilings and Submonoids of Metabelian Groups.
Theory Comput. Syst., 2011

Compressed Word Problems in HNN-extensions and Amalgamated Products.
Theory Comput. Syst., 2011

Fixpoint Logics over Hierarchical Structures.
Theory Comput. Syst., 2011

Automatic structures of bounded degree revisited.
J. Symb. Log., 2011

Leaf languages and string compression.
Inf. Comput., 2011

Isomorphism of regular trees and words
CoRR, 2011

Compressed Word Problems for Inverse Monoids.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Isomorphism of Regular Trees and Words.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

The First-Order Theory of Ground Tree Rewrite Graphs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Tree Structure Compression with RePair.
Proceedings of the 2011 Data Compression Conference (DCC 2011), 2011

Compressed Membership in Automata with Compressed Labels.
Proceedings of the Computer Science - Theory and Applications, 2011

2010
Some natural decision problems in automatic graphs.
J. Symb. Log., 2010

Compressed Membership Problems for Regular Expressions and Hierarchical Automata.
Int. J. Found. Comput. Sci., 2010

Tree structure compression with RePair
CoRR, 2010

The Isomorphism Problem for omega-Automatic Trees
CoRR, 2010

The Isomorphism Problem On Classes of Automatic Structures
CoRR, 2010

Branching-time Model Checking of One-counter Processes.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

The Isomorphism Problem on Classes of Automatic Structures.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

The Isomorphism Problem for omega-Automatic Trees.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009
PDL with intersection and converse: satisfiability and infinite-state model checking.
J. Symb. Log., 2009

Branching-time model checking of one-counter processes
CoRR, 2009

Branching-time model checking of one-counter processes
CoRR, 2009

Parameter Reduction in Grammar-Compressed Trees.
Proceedings of the Foundations of Software Science and Computational Structures, 2009

Compressed Word Problems in HNN-Extensions and Amalgamated Products.
Proceedings of the Computer Science, 2009

Automatic Structures of Bounded Degree Revisited.
Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

2008
First-order and counting theories of omega-automatic structures.
J. Symb. Log., 2008

Efficient memory representation of XML document trees.
Inf. Syst., 2008

Rational Subsets in HNN-Extensions and Amalgamated Products.
IJAC, 2008

Algorithmic Problems on Inverse Monoids over Virtually Free Groups.
IJAC, 2008

Word Equations over Graph Products.
IJAC, 2008

Automatic structures of bounded degree revisited
CoRR, 2008

Hamiltonicity of automatic graphs.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Leaf languages and string compression.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

08261 Executive Summary - Structure-Based Compression of Complex Massive Data.
Proceedings of the Structure-Based Compression of Complex Massive Data, 22.06., 2008

08261 Abstracts Collection - Structure-Based Compression of Complex Massive Data.
Proceedings of the Structure-Based Compression of Complex Massive Data, 22.06., 2008

Compressed membership problems revisited.
Proceedings of the Automata and Formal Languages, 12th International Conference, 2008

Euler paths and ends in automatic and recursive graphs.
Proceedings of the Automata and Formal Languages, 12th International Conference, 2008

2007
Inverse monoids: Decidability and complexity of algebraic questions.
Inf. Comput., 2007

The submonoid and rational subset membership problems for graph groups.
Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007

PDL with Intersection and Converse Is 2 EXP-Complete.
Proceedings of the Foundations of Software Science and Computational Structures, 2007

Application of verification techniques to inverse monoids.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

PDL with Intersection and Converse is 2EXP-complete.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

07441 Abstracts Collection -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

07441 Summary -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

Efficient Computation in Groups Via Compression.
Proceedings of the Computer Science, 2007

2006
The complexity of tree automata and XPath on grammar-compressed trees.
Theor. Comput. Sci., 2006

Word Problems and Membership Problems on Compressed Words.
SIAM J. Comput., 2006

Logical Aspects of Cayley-graphs: the Monoid Case.
IJAC, 2006

Querying and Embedding Compressed Texts.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Partially Commutative Inverse Monoids.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Monadic Chain Logic Over Iterations and Applications to Pushdown Systems.
Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Theories of HNN-Extensions and Amalgamated Products.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

First-Order and Counting Theories of omega-Automatic Structures.
Proceedings of the Foundations of Software Science and Computation Structures, 2006

Infinite State Model-Checking of Propositional Dynamic Logics.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005
Decidable First-Order Theories of One-Step Rewriting in Trace Monoids.
Theory Comput. Syst., 2005

Complexity results for prefix grammars.
ITA, 2005

Decidability and complexity in automatic monoids.
Int. J. Found. Comput. Sci., 2005

Axiomatising divergence.
Inf. Comput., 2005

Logical aspects of Cayley-graphs: the group case.
Ann. Pure Appl. Logic, 2005

Tree Automata and XPath on Compressed Trees.
Proceedings of the Implementation and Application of Automata, 2005

Inverse Monoids: Decidability and Complexity of Algebraic Questions.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Model-Checking Hierarchical Structures.
Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

Fixpoint Logics on Hierarchical Structures.
Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

Efficient Memory Representation of XML Documents.
Proceedings of the Database Programming Languages, 10th International Symposium, 2005

2004
Existential and Positive Theories of Equations in Graph Products.
Theory Comput. Syst., 2004

Bounded MSC communication.
Inf. Comput., 2004

Word Problems on Compressed Words.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Decidability and Complexity in Automatic Monoids.
Proceedings of the Developments in Language Theory, 2004

2003
Computational and logical aspects of infinite monoids.
PhD thesis, 2003

Realizability of high-level message sequence charts: closing the gaps.
Theor. Comput. Sci., 2003

Decidable Theories of Cayley-Graphs.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Automatic Structures of Bounded Degree.
Proceedings of the Logic for Programming, 2003

Word Equations over Graph Products.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002
A Note on The Existential Theory of Equations in Plain Groups.
IJAC, 2002

Existential and Positive Theories of Equations in Graph Products.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Axiomatising Divergence.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

On the Theory of One-Step Rewriting in Trace Monoids.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Bounded MSC Communication.
Proceedings of the Foundations of Software Science and Computation Structures, 2002

Safe Realizability of High-Level Message Sequence Charts.
Proceedings of the CONCUR 2002, 2002

2001
Confluence Problems for Trace Rewriting Systems.
Inf. Comput., 2001

On the Parallel Complexity of Tree Automata.
Proceedings of the Rewriting Techniques and Applications, 12th International Conference, 2001

Word Problems for 2-Homogeneous Monoids and Symmetric Logspace.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000
Word Problems and Confluence Problems for Restricted Semi-Thue Systems.
Proceedings of the Rewriting Techniques and Applications, 11th International Conference, 2000

1999
Complexity Results for Confluence Problems.
Proceedings of the Mathematical Foundations of Computer Science 1999, 1999

Das Konfluenzproblem für Spurersetzungssysteme.
PhD thesis, 1999

1998
NP-Completeness Results Concerning the Transformation of Logic Programs into Attribute Grammars.
Acta Cybern., 1998

On the Confluence of Trace Rewriting Systems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998

Priority and Maximal Progress Are Completely Axioatisable (Extended Abstract).
Proceedings of the CONCUR '98: Concurrency Theory, 1998


  Loading...