Author name cluster

Markus Lohrey

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

34 papers

2 author rows

MFCS Conference 2025 Conference Paper

FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree

Markus Lohrey
Sebastian Maneth
Markus L. Schmid

Enumerating the result set of a first-order query over a relational structure of bounded degree can be done with linear preprocessing and constant delay. In this work, we extend this result towards the compressed perspective where the structure is given in a potentially highly compressed form by a straight-line program (SLP). Our main result is an algorithm that enumerates the result set of a first-order query over a structure of bounded degree that is represented by an SLP satisfying the so-called apex condition. For a fixed formula, the enumeration algorithm has constant delay and needs a preprocessing time that is linear in the size of the SLP.

MFCS Conference 2024 Conference Paper

Streaming in Graph Products

Markus Lohrey
Julio Xochitemol

We investigate the streaming space complexity of word problems for groups. Using so-called distinguishers, we prove a transfer theorem for graph products of groups. Moreover, we use distinguishers to obtain a logspace streaming algorithm for the membership problem in a finitely generated subgroup of a free group.

MFCS Conference 2022 Conference Paper

Membership Problems in Finite Groups

Markus Lohrey
Andreas Rosowski
Georg Zetzsche

We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n ≥ 3, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks [Eugene M. Luks, 1991], which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.

Highlights Conference 2022 Conference Abstract

Straight-Line Programs: From Compression to Algorithmics

Markus Lohrey

A straight-line program is a context-free grammar that produces exactly one word. The length of this word can be exponentially smaller (in the best case) than the size of the straight-line program. This is the underlying idea of grammar-based compression, where straight-line programs are used for the compression of strings. Compressors that exploit this idea are for instance LZ77, RePair, BiSection, and Sequitur. After introducing straight-line programs and grammar-based compression I will explore recent algorithmic applications of straight-line programs in stringology, group theory, and algebraic complexity theory. If time permits I will also talk about an extension to trees. Straight-line programs for trees have found applications in information theory and parallel algorithms.

MFCS Conference 2022 Conference Paper

Streaming Word Problems

Markus Lohrey
Lukas Lück

We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, direct products, free products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson’s group F.

MFCS Conference 2020 Conference Paper

Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups

Markus Lohrey
Georg Zetzsche

We prove that the power word problem for the solvable Baumslag-Solitar groups BS(1, q) = ⟨ a, t ∣ t a t^{-1} = a^q ⟩ can be solved in TC⁰. In the power word problem, the input consists of group elements g₁, …, g_d and binary encoded integers n₁, …, n_d and it is asked whether g₁^{n₁} ⋯ g_d^{n_d} = 1 holds. Moreover, we prove that the knapsack problem for BS(1, q) is NP-complete. In the knapsack problem, the input consists of group elements g₁, …, g_d, h and it is asked whether the equation g₁^{x₁} ⋯ g_d^{x_d} = h has a solution in ℕ^d.

FOCS Conference 2019 Conference Paper

Balancing Straight-Line Programs

Moses Ganardi
Artur Jez
Markus Lohrey

We show that a context-free grammar of size m that produces a single string w of length n (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for w of size O(m), whose unique derivation tree has depth O(log n). This solves an open problem in the area of grammar-based compression, improves many results in this area and greatly simplifies many existing constructions. Similar results are stated for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be all deduced from a single meta theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to O(log n) with the cost of a constant multiplicative size increase. Here, n refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (non-commutative) semirings. A long version of the paper can be found in [1].

MFCS Conference 2019 Conference Paper

The Power Word Problem

Markus Lohrey
Armin Weiß

In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may contain powers p^x, where p is a finite word over generators of G and x is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i. e. , an algebraic circuit over G). The main result of the paper states that the power word problem for a finitely generated free group F is AC^0-Turing-reducible to the word problem for F. Moreover, the following hardness result is shown: For a wreath product G Wr Z, where G is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where G is abelian: then the power word problem is shown to be in TC^0.

MFCS Conference 2018 Conference Paper

Average Case Analysis of Leaf-Centric Binary Tree Sources

Louisa Seelbach Benkner
Markus Lohrey

We study the average size of the minimal directed acyclic graph (DAG) with respect to so-called leaf-centric binary tree sources as studied by Zhang, Yang, and Kieffer. A leaf-centric binary tree source induces for every n >= 2 a probability distribution on all binary trees with n leaves. We generalize a result shown by Flajolet, Gourdon, Martinez and Devroye according to which the average size of the minimal DAG of a binary tree that is produced by the binary search tree model is Theta(n / log n).

MFCS Conference 2018 Conference Paper

Sliding Windows over Context-Free Languages

Moses Ganardi
Artur Jez
Markus Lohrey

We study the space complexity of sliding window streaming algorithms that check membership of the window content in a fixed context-free language. For regular languages, this complexity is either constant, logarithmic or linear [Moses Ganardi et al. , 2016]. We prove that every context-free language whose sliding window space complexity is log_2(n) - omega(1) must be regular and has constant space complexity. Moreover, for every c in N, c >= 1 we construct a (nondeterministic) context-free language whose sliding window space complexity is O(n^(1/c)) \ o(n^(1/c)). Finally, we give an example of a deterministic one-counter language whose sliding window space complexity is Theta((log n)^2).

MFCS Conference 2017 Conference Paper

Counting Problems for Parikh Images

Christoph Haase
Stefan Kiefer
Markus Lohrey

Given finite-state automata (or context-free grammars) A, B over the same alphabet and a Parikh vector p, we study the complexity of deciding whether the number of words in the language of A with Parikh image p is greater than the number of such words in the language of B. Recently, this problem turned out to be tightly related to the cost problem for weighted Markov chains. We classify the complexity according to whether A and B are deterministic, the size of the alphabet, and the encoding of p (binary or unary).

I&C Journal 2016 Journal Article

Approximation of smallest linear tree grammar

Artur Jeż
Markus Lohrey

A simple linear-time algorithm for constructing a linear context-free tree grammar of size O ( r g + r g log ⁡ ( n / r g ) ) for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T, and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i. e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees.

CSL Conference 2016 Conference Paper

On the Parallel Complexity of Bisimulation on Finite Systems

Moses Ganardi
Stefan Göller
Markus Lohrey

In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC^1, respectively. This solves an open problem from Balcázar, Gabarró, and Sántha. We also show that the simulation problem is P-complete even for graphs of bounded path-width.

I&C Journal 2015 Journal Article

Rational subsets and submonoids of wreath products

Markus Lohrey
Benjamin Steinberg
Georg Zetzsche

It is shown that membership in rational subsets of wreath products H ≀ V with H a finite group and V a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product Z ≀ Z with an undecidable membership problem.

CSL Conference 2015 Conference Paper

Temporal Logics with Local Constraints (Invited Talk)

Claudia Carapelle
Markus Lohrey

Recent decidability results on the satisfiability problem for temporal logics, in particular LTL, CTL* and ECTL*, with constraints over external structures like the integers with the order or infinite trees are surveyed in this paper.

I&C Journal 2013 Journal Article

Isomorphism of regular trees and words

Markus Lohrey
Christian Mathissen

The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be EXPTIME -complete (resp. P -complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be PSPACE -complete (resp. P -complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Ésik and Bloom. Similar techniques can be used to show that one can check in polynomial time whether a given regular linear order has a non-trivial automorphism. This improves a recent decidability result of Kuske.

Highlights Conference 2013 Conference Abstract

Satisfiability of CTL* with constraints

Claudia Carapelle
Alexander Kartzow
Markus Lohrey

CTL* formulas can be enriched to express relations between variables whose value can range in a chosen concrete domain. Chosen the appropriate domain one can express quantitative properties that ordinary CTL^* formulas can only approximate through abstraction. We can refer directly to concrete values and describe how they change in time. In this talk we show that satisfiability for CTL* with equality-, order-, and modulo- constraints over the Z is decidable

MFCS Conference 2011 Conference Paper

Compressed Word Problems for Inverse Monoids

Markus Lohrey

Abstract The compressed word problem for a finitely generated monoid M asks whether two given compressed words over the generators of M represent the same element of M. For string compression, straight-line programs, i. e. , context-free grammars that generate a single string, are used in this paper. It is shown that the compressed word problem for a free inverse monoid of finite rank at least two is complete for \(\Pi^p_2\) (second universal level of the polynomial time hierarchy). Moreover, it is shown that there exists a fixed finite idempotent presentation (i. e. , a finite set of relations involving idempotents of a free inverse monoid), for which the corresponding quotient monoid has a PSPACE -complete compressed word problem. The ordinary uncompressed word problem for such a quotient can be solved in logspace [10]. Finally, a PSPACE -algorithm that checks whether a given element of a free inverse monoid belongs to a given rational subset is presented. This problem is also shown to be PSPACE -complete (even for a fixed finitely generated submonoid instead of a variable rational subset).

I&C Journal 2011 Journal Article

Leaf languages and string compression

Markus Lohrey

Tight connections between leaf languages and strings compressed by straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a language L is complete for the leaf language class defined by L via logspace machines. A more difficult variant of the compressed membership problem for L is shown to be complete for the leaf language class defined by L via polynomial time machines. As a corollary, it is shown that there exists a fixed linear visibly pushdown language for which the compressed membership problem is PSPACE-complete. For XML languages, it is shown that the compressed membership problem is coNP-complete. Furthermore it is shown that the embedding problem for SLP-compressed strings is hard for PP (probabilistic polynomial time).

CSL Conference 2010 Conference Paper

The Isomorphism Problem for omega -Automatic Trees

Dietrich Kuske
Jiamou Liu
Markus Lohrey

Abstract The main result of this paper is that the isomorphism problem for ω -automatic trees of finite height is at least as hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies [9] showing that the isomorphism problem for ω -automatic structures is not \(\Sigma^1_2\). Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω -automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to our main results, we show lower and upper bounds for the isomorphism problem for ω -automatic trees of every finite height: (i) It is decidable ( \(\Pi^0_1\) -complete, resp.) for height 1 (2, resp.), (ii) \(\Pi^1_1\) -hard and in \(\Pi^1_2\) for height 3, and (iii) \(\Pi^1_{n-3}\) - and \(\Sigma^1_{n-3}\) -hard and in \(\Pi^1_{2n-4}\) (assuming CH ) for all n ≥ 4. All proofs are elementary and do not rely on theorems from set theory. Complete proofs can be found in [18].

CSL Conference 2009 Conference Paper

Automatic Structures of Bounded Degree Revisited

Dietrich Kuske
Markus Lohrey

Abstract It it shown that the first-order theory of an automatic structure, whose Gaifman graph has bounded degree, is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). Presenting an automatic structure of bounded degree whose theory is hard for 2 EXPSPACE, we also prove this result to be optimal. These findings close the gap left open in [14].

I&C Journal 2007 Journal Article

Inverse monoids: Decidability and complexity of algebraic questions

Markus Lohrey
Nicole Ondrusch

This paper investigates the word problem for inverse monoids generated by a set Γ subject to relations of the form e = f, where e and f are both idempotents in the free inverse monoid generated by Γ. It is shown that for every fixed monoid of this form the word problem can be solved both in linear time on a RAM as well as in deterministic logarithmic space, which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced.

CSL Conference 2006 Conference Paper

Infinite State Model-Checking of Propositional Dynamic Logics

Stefan Göller
Markus Lohrey

Abstract Model-checking problems for PDL (propositional dynamic logic) and its extension PDL ∩ (which includes the intersection operator on programs) over various classes of infinite state systems (BPP, BPA, pushdown systems, prefix-recognizable systems) are studied. Precise upper and lower bounds are shown for the data/expression/combined complexity of these model-checking problems.

MFCS Conference 2006 Conference Paper

Partially Commutative Inverse Monoids

Volker Diekert
Markus Lohrey
Alexander Miller

Abstract Free partially commutative inverse monoids are investigated. Analogously to free partially commutative monoids (trace monoids), free partially commutative inverse monoid are the quotients of free inverse monoids modulo a partially defined commutation relation on the generators. An O ( n log( n )) algorithm on a RAM for the word problem is presented, and NP -completeness of the generalized word problem and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. For these monoids, the word problem is decidable if and only if the complement of the commutation relation is transitive.

MFCS Conference 2006 Conference Paper

Querying and Embedding Compressed Texts

Yury Lifshits
Markus Lohrey

Abstract The computational complexity of two simple string problems on compressed input strings is considered: the querying problem (What is the symbol at a given position in a given input string?) and the embedding problem (Can the first input string be embedded into the second input string?). Straight-line programs are used for text compression. It is shown that the querying problem becomes P-complete for compressed strings, while the embedding problem becomes hard for the complexity class \(\Theta^{p}_{2}\).

TCS Journal 2006 Journal Article

The complexity of tree automata and XPath on grammar-compressed trees

Markus Lohrey
Sebastian Maneth

The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the evaluation problem for (structural) XPath queries on trees that are compressed via straight-line context-free tree grammars is investigated.

I&C Journal 2005 Journal Article

Axiomatising divergence

Markus Lohrey
Pedro R. D’Argenio
Holger Hermanns

When a process is capable of executing an unbounded number of non-observable actions it is said to be divergent. Different capabilities of an observer to identify this phenomena along the execution leads to different divergent sensitive semantics. This paper develops sound and complete axiomatisations for the divergence sensitive spectrum of weak bisimulation equivalence. The axiomatisations separates the axioms concerning recursion and those that capture the essence of diverging behaviour.

MFCS Conference 2005 Conference Paper

Inverse Monoids: Decidability and Complexity of Algebraic Questions

Markus Lohrey
Nicole Ondrusch

Abstract The word problem for inverse monoids generated by a set Γ subject to relations of the form e = f, where e and f are both idempotents in the free inverse monoid generated by Γ, is investigated. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, it is shown that the Cayley-graph of the free inverse monoid has an undecidable monadic second-order theory.

I&C Journal 2004 Journal Article

Bounded MSC communication

Markus Lohrey
Anca Muscholl

Message sequence charts (MSCs) and high-level message sequence charts (HMSCs) are popular formalisms for the specification of communication protocols between asynchronous processes. An important concept in this context is the size of the communication buffers used between processes. Since real systems impose limitations on the capacity (or speed) of communication links, we ask whether a given HMSC can be implemented with respect to a given buffer size imposed by the environment. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (or HMSC, or nested MSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP.

LPAR Conference 2003 Conference Paper

Automatic Structures of Bounded Degree

Markus Lohrey

The first-order theory of an automatic structure is known to be decidable but there are examples of automatic structures with nonelementary first-order theories. We prove that the first-order theory of an automatic structure of bounded degree (meaning that the corresponding Gaifman-graph has bounded degree) is elementary decidable. More precisely, we prove an upper bound of triply exponential alternating time with a linear number of alternations. We also present an automatic structure of bounded degree such that the corresponding first-order theory has a lower bound of doubly exponential time with a linear number of alternations. We prove similar results also for tree automatic structures.

TCS Journal 2003 Journal Article

Realizability of high-level message sequence charts: closing the gaps

Markus Lohrey

We study the notion of safe realizability for high-level message sequence charts (HMSCs) (Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Crete (Greece), Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 797–808). We show that safe realizability is EXPSPACE-complete for bounded HMSCs but undecidable for the class of all HMSCs. This solves two open problems from Alur et al. Moreover we prove that safe realizability is also EXPSPACE-complete for the larger class of globally-cooperative HMSCs.

I&C Journal 2001 Journal Article

Confluence Problems for Trace Rewriting Systems

Markus Lohrey

Rewriting systems over trace monoids, briefly trace rewriting systems, generalize both semi-Thue systems and vector replacement systems. In [21], a particular trace monoid M is presented such that confluence is undecidable for the class of length–reducing trace rewriting systems over M. In this paper, we show that this result holds for every trace monoid, which is neither free nor free commutative. Furthermore we show that confluence for special trace rewriting systems over a fixed trace monoid is decidable in polynomial time.

MFCS Conference 2001 Conference Paper

Word Problems for 2-Homogeneous Monoids and Symmetric Logspace

Markus Lohrey

Abstract We prove that the word problem for every monoid presented by a fixed 2-homogeneous semi-Thue system can be solved in log-space, which generalizes a result of Lipton and Zalcstein for free groups. The uniform word problem for the class of all 2-homogeneous semi-Thue systems is shown to be complete for symmetric log-space.

MFCS Conference 1999 Conference Paper

Complexity Results for Confluence Problems

Markus Lohrey

Abstract We study the complexity of the confluence problem for restricted kinds of semi-Thue systems, vector replacement systems and general trace rewriting systems. We prove that confluence for length-reducing semi-Thue systems is P-complete and that this complexity reduces to NC 2 in the monadic case. For length-reducing vector replacement systems we prove that the confluence problem is PSPACE-complete and that the complexity reduces to NP and P for monadic systems and special systems, respectively. Finally we prove that for special trace rewriting systems, confluence can be decided in polynomial time and that the extended word problem for special trace rewriting systems is undecidable.