Markus L. Schmid

Markus L. Schmid

Auto-generated profile, based on publicly available information

Markus L. Schmid

Humboldt-Universität zu Berlin

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 May 2017 in Theoretical Computer Science
Verified
Journal Article
Closed access
Henning FernauHenning Fernau
Henning Fernau
MPMeenakshi Paramasivan
Meenakshi Paramasivan
MSMarkus L. Schmid
Markus L. Schmid
VVVojtěch Vorel
Vojtěch Vorel

13 November 2020 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
KCKatrin Casel
Katrin Casel
Henning FernauHenning Fernau
Henning Fernau
SGSerge Gaspers
Serge Gaspers
BGBenjamin Gras
Benjamin Gras
MSMarkus L. Schmid
Markus L. Schmid
In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an $\mathcal {O}(3^{\mid {w}\mid })$ O ( 3 ∣ w ∣ ) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the “hierarchical depth” of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.

27 November 2023 in Logical Methods in Computer Science
Verified
Journal Article
Open access
PDF file
KCKatrin Casel
Katrin Casel
MSMarkus L. Schmid
Markus L. Schmid
A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for q and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.

9 August 2019
Verified
Book Chapter
Closed access
PDF file
FMFlorin Manea
Florin Manea
MSMarkus L. Schmid
Markus L. Schmid

16 September 2023 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
KCKatrin Casel
Katrin Casel
TFTobias Friedrich
Tobias Friedrich
SNStefan Neubert
Stefan Neubert
MSMarkus L. Schmid
Markus L. Schmid

10 February 2025 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
RSRebecca Sattler
Rebecca Sattler
SKSarah Kleest-Meißner
Sarah Kleest-Meißner
SLSteven Lange
Steven Lange
MSMarkus L. Schmid
Markus L. Schmid
NSNicole Schweikardt
Nicole Schweikardt
MWMatthias Weidlich
Matthias Weidlich
The continuous evaluation of queries over an event stream provides the foundation for reactive applications in various domains. Yet, knowledge of queries that detect distinguished event patterns that are potential causes of the situation of interest is often not directly available. However, given a database of finite, historic (sub-)streams that have been gathered whenever a situation of interest was observed, one may aim at automatic discovery of the respective queries. Existing algorithms for event query discovery incorporate ad-hoc design choices, though, and it is unclear how their suitability for a database shall be assessed. In this paper, we address this gap with DISCES, an algorithmic framework for event query discovery. DISCES outlines a design space for discovery algorithms, thereby making the design choices explicit. We instantiate the framework to derive four specific algorithms, which all yield correct and complete results, but differ in their runtime sensitivity. We therefore also provide guidance on how to select one of the algorithms for a given database based on a few of its essential properties. Our experiments using simulated and real-world data illustrate that our algorithms are indeed tailored to databases showing certain properties and solve the query discovery problem several orders of magnitude faster than existing approaches.