Wim Martens

KR Conference 2020 Conference Paper

Containment of Simple Conjunctive Regular Path Queries

• Diego Figueira
• Adwait Godbole
• S. Krishna
• Wim Martens
• Matthias Niewerth
• Tina Trautner

Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is EXPSPACE-complete in general, we focus here on severely restricted fragments, which are known to be highly relevant in practice according to several recent studies. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for NP, Pi2p, PSPACE or EXPSPACE.

STOC Conference 2017 Invited Paper

Optimizing tree pattern queries: why cutting is not enough (invited talk)

• Wim Martens

TCS Journal 2016 Journal Article

Closure properties and descriptional complexity of deterministic regular expressions

• Katja Losemann
• Wim Martens
• Matthias Niewerth

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i. e. , we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of languages, we consider regular expressions, deterministic regular expressions, and deterministic finite automata. Our results show that exponential blow-ups between these representations cannot be avoided. Furthermore, we study the descriptional complexity of these representations when applying boolean operations. Here, we start by investigating the closure properties of such languages under various language-theoretic operations such as union, intersection, concatenation, Kleene star, and reversal. Our results show that languages that are definable by deterministic regular expressions are not closed under any of these operations. Finally, we show that for all these operations except the Kleene star an exponential blow-up in the size of deterministic regular expressions cannot be avoided.

Highlights Conference 2013 Conference Abstract

Efficient separability of regular languages by subsequences and suffixes

• Wojciech Czerwiński
• Wim Martens
• Tomas Masopust

When can two regular word languages K and L be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if K and L are given by nondeterministic automata.

MFCS Conference 2013 Conference Paper

Validity of Tree Pattern Queries with Respect to Schema Information

• Henrik Björklund
• Wim Martens
• Thomas Schwentick

Abstract We prove that various containment and validity problems for tree pattern queries with respect to a schema are EXPTIME-complete. When one does not require the root of a tree pattern query to match the root of a tree, validity of a non-branching tree pattern query with respect to a Relax NG schema or W3C XML Schema is already EXPTIME-hard when the query does not branch and uses only child axes. These hardness results already hold when the alphabet size is fixed. Validity with respect to a DTD is proved to be EXPTIME-hard already when the query only uses child axes and is allowed to branch only once.

MFCS Conference 2012 Conference Paper

Descriptional Complexity of Deterministic Regular Expressions

• Katja Losemann
• Wim Martens
• Matthias Niewerth

Abstract We study the descriptional complexity of regular languages that are definable by deterministic regular expressions. First, we examine possible blow-ups when translating between regular expressions, deterministic regular expressions, and deterministic automata. Then we give an overview of the closure properties of these languages under various language-theoretic operations and we study the descriptional complexity of applying these operations. Our main technical result is a general property that implies that the blow-up when translating a DFA to an equivalent deterministic expression can be exponential.

MFCS Conference 2009 Conference Paper

Regular Expressions with Counting: Weak versus Strong Determinism

• Wouter Gelade
• Marc Gyssens
• Wim Martens

Abstract We study deterministic regular expressions extended with the counting operator. There exist two notions of determinism, strong and weak determinism, which almost coincide for standard regular expressions. This, however, changes dramatically in the presence of counting. In particular, we show that weakly deterministic expressions with counting are exponentially more succinct and strictly more expressive than strongly deterministic ones, even though they still do not capture all regular languages. In addition, we present a finite automaton model with counters, study its properties and investigate the natural extension of the Glushkov construction translating expressions with counting into such counting automata. This translation yields a deterministic automaton if and only if the expression is strongly deterministic. These results then also allow to derive upper bounds for decision problems for strongly deterministic expressions with counting.

MFCS Conference 2008 Conference Paper

Optimizing Conjunctive Queries over Trees Using Schema Information

• Henrik Björklund
• Wim Martens
• Thomas Schwentick

Abstract We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME-complete w. r. t. a schema (DTD or Relax NG). Furthermore, we show that satisfiability for conjunctive queries w. r. t. a schema can be decided in NP. The problem is NP-hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment w. r. t. a schema becomes decidable again if the “larger” query is not allowed to use both equalities and inequalities.

I&C Journal 2008 Journal Article

Typechecking top-down XML transformations: Fixed input or output schemas

• Wim Martens
• Frank Neven
• Marc Gyssens

Typechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting.

TCS Journal 2005 Journal Article

On the complexity of typechecking top-down XML transformations

• Wim Martens
• Frank Neven

We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as input and output schemas. The complexity of the typechecking problems in this scenario ranges from PTIME to EXPTIME.

MFCS Conference 2004 Conference Paper

Complexity of Decision Problems for Simple Regular Expressions

• Wim Martens
• Frank Neven
• Thomas Schwentick

Abstract We study the complexity of the inclusion, equivalence, and intersection problem for simple regular expressions arising in practical XML schemas. These basically consist of the concatenation of factors where each factor is a disjunction of strings possibly extended with ‘*’ or ‘? ’. We obtain lower and upper bounds for various fragments of simple regular expressions. Although we show that inclusion and intersection are already intractable for very weak expressions, we also identify some tractable cases. For equivalence, we only prove an initial tractability result leaving the complexity of more general cases open. The main motivation for this research comes from database theory, or more specifically XML and semi-structured data. We namely show that all lower and upper bounds for inclusion and equivalence, carry over to the corresponding decision problems for extended context-free grammars and single-type tree grammars, which are abstractions of DTDs and XML Schemas, respectively. For intersection, we show that the complexity only carries over for DTDs.