Author name cluster

Markus L. Schmid

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.

13 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.

Details

MFCS Conference 2025 Conference Paper

Linear Time Subsequence and Supersequence Regex Matching

Antoine Amarilli
Florin Manea
Tina Ringleb
Markus L. Schmid

It is well-known that checking whether a given string w matches a given regular expression r can be done in quadratic time O(|w|⋅ |r|) and that this cannot be improved to a truly subquadratic running time of O((|w|⋅ |r|)^{1-ε}) assuming the strong exponential time hypothesis (SETH). We study a different matching paradigm where we ask instead whether w has a subsequence that matches r, and show that regex matching in this sense can be solved in linear time O(|w| + |r|). Further, the same holds if we ask for a supersequence. We show that the quantitative variants where we want to compute a longest or shortest subsequence or supersequence of w that matches r can be solved in O(|w|⋅ |r|), i. e. , asymptotically no worse than classical regex matching; and we show that O(|w| + |r|) is conditionally not possible for these problems. We also investigate these questions with respect to other natural string relations like the infix, prefix, left-extension or extension relation instead of the subsequence and supersequence relation. We further study the complexity of the universal problem where we ask if all subsequences (or supersequences, infixes, prefixes, left-extensions or extensions) of an input string satisfy a given regular expression.

Details

Highlights Conference 2021 Conference Abstract

Spanner Evaluation over SLP-Compressed Documents

Markus L. Schmid

We consider the problem of evaluating regular spanners over compressed documents, i. e. , we wish to solve evaluation tasks directly on the compressed data, without decompression. As compressed forms of the documents we use straight-line programs (SLPs) – a lossless compression scheme for textual data widely used in different areas of theoretical computer science and particularly well-suited for algorithmics on compressed data. In data complexity, our results are as follows. For a regular spanner M and an SLP S that represents a document D, we can solve the tasks of model checking and of checking non-emptiness in time O(size(S)). Computing the set [[M]](D) of all span-tuples extracted from D can be done in time O(size(S) |[[M]](D)|), and enumeration of [[M]](D) can be done with linear preprocessing O(size(S)) and a delay of O(depth(S)), where depth(S) is the depth of S’s derivation tree. Note that size(S) can be exponentially smaller than the document’s size |D|; and, due to known balancing results for SLPs, we can always assume that depth(S) = O(log(|D|)) independent of D’s compressibility. Hence, our enumeration algorithm has a delay logarithmic in the size of the non-compressed data and a preprocessing time that is at best (i. e. , in the case of highly compressible documents) also logarithmic, but at worst still linear. Therefore, in a big-data perspective, our enumeration algorithm for SLP-compressed documents may nevertheless beat the known linear preprocessing and constant delay algorithms for non-compressed documents.

Details

MFCS Conference 2018 Conference Paper

Consensus Strings with Small Maximum Distance and Small Distance Sum

Laurent Bulteau
Markus L. Schmid

The parameterised complexity of consensus string problems (Closest String, Closest Substring, Closest String with Outliers) is investigated in a more general setting, i. e. , with a bound on the maximum Hamming distance and a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of Closest String and Closest Substring, and partly for Closest String with Outliers; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.

Details

TCS Journal 2018 Journal Article

Revisiting Shinohara's algorithm for computing descriptive patterns

Henning Fernau
Florin Manea
Robert Mercaş
Markus L. Schmid

A pattern α is a word consisting of constants and variables and it describes the pattern language L ( α ) of all words that can be obtained by uniformly replacing the variables with constant words. In 1982, Shinohara presents an algorithm that computes a pattern that is descriptive for a finite set S of words, i. e. , its pattern language contains S in the closest possible way among all pattern languages. We generalise Shinohara's algorithm to subclasses of patterns and characterise those subclasses for which it is applicable. Furthermore, within this set of pattern classes, we characterise those for which Shinohara's algorithm has a polynomial running time (under the assumption P ≠ NP ). Moreover, we also investigate the complexity of the consistency problem of patterns, i. e. , finding a pattern that separates two given finite sets of words.

Details DOI

TCS Journal 2017 Journal Article

Characterization and complexity results on jumping finite automata

Henning Fernau
Meenakshi Paramasivan
Markus L. Schmid
Vojtěch Vorel

In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.

Details DOI

MFCS Conference 2017 Conference Paper

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

Katrin Casel
Henning Fernau
Alexander Grigoriev
Markus L. Schmid
Sue Whitesides

Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i. e. , the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.

Details

I&C Journal 2016 Journal Article

Characterising REGEX languages by regular languages equipped with factor-referencing

Markus L. Schmid

A (factor-)reference in a word is a special symbol that refers to another factor in the same word; a reference is dereferenced by substituting it with the referenced factor. We introduce and investigate the class ref-REG of all languages that can be obtained by taking a regular language R and then dereferencing all possible references in the words of R. We show that ref-REG coincides with the class of languages defined by regular expressions as they exist in modern programming languages like Perl, Python, Java, etc. (often called REGEX languages).

Details DOI

TCS Journal 2016 Journal Article

Computing equality-free and repetitive string factorisations

Markus L. Schmid

For a string w, a factorisation is any tuple ( u 1, u 2, …, u k ) of strings that satisfies w = u 1 ⋅ u 2 ⋯ u k. A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of repeating factors) and its width is the maximum length of any factor. To decide, for a string w and a number m, whether w has an equality-free factorisation with a size of at least (or a width of at most) m are NP -complete problems. We further investigate the complexity of these problems and we also study the converse problems of computing a factorisation that is to a large extent not equality-free, i. e. , a factorisation of size at least (or width at most) m such that the total number of different factors does not exceed a given bound k.

Details DOI

Highlights Conference 2016 Conference Abstract

On the Complexity of Grammar-Based Compression over Fixed Alphabets

Katrin Casel
Henning Fernau
Serge Gaspers
Benjamin Gras
Markus L. Schmid

This talk is based on the following paper: Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid. On the Complexity of Grammar-Based Compression over Fixed Alphabets. 43rd International Colloquium on Automata, Languages, and Programming 2016, ICALP 2016. We investigate the complexity of grammar-based compression, i. e. , to compress a word by a context-free grammar. It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3^n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given 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” on the complexity of the shortest-grammar problem).

Details

I&C Journal 2015 Journal Article

Pattern matching with variables: A multivariate complexity analysis

Henning Fernau
Markus L. Schmid

A pattern α, i. e. , a string that contains variables and terminals, matches a terminal word w if w can be obtained by uniformly substituting the variables of α by terminal words. Deciding whether a given terminal word matches a given pattern is NP-complete and this holds for several natural variants of the problem that result from whether or not variables can be erased, whether or not the patterns are required to be terminal-free or whether or not the mapping of variables to terminal words must be injective. We consider numerous parameters of this problem (i. e. , number of variables, length of w, length of the words substituted for variables, number of occurrences per variable, cardinality of the terminal alphabet) and for all possible combinations of the parameters (and variants described above), we answer the question whether or not the problem is still NP-complete if these parameters are bounded by constants.

Details DOI

I&C Journal 2014 Journal Article

Patterns with bounded treewidth

Daniel Reidenbach
Markus L. Schmid

A pattern is a string consisting of variables and terminal symbols, and its language is the set of all words that can be obtained by substituting arbitrary words for the variables. The membership problem for pattern languages, i. e. , deciding on whether or not a given word is in the pattern language of a given pattern is NP-complete. We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify new such parameters.

Details DOI

TCS Journal 2014 Journal Article

Regular and context-free pattern languages over small alphabets

Daniel Reidenbach
Markus L. Schmid

Pattern languages are generalisations of the copy language, which is a standard textbook example of a context-sensitive and non-context-free language. In this work, we investigate a counter-intuitive phenomenon: with respect to alphabets of size 2 and 3, pattern languages can be regular or context-free in an unexpected way. For this regularity and context-freeness of pattern languages, we give several sufficient and necessary conditions and improve known results.

Details DOI