Thomas Schwentick

Counting in Trees for Free Helmut Seidl (2008)

1 Introduction Semistructured data is a data model of great importance in several areas including databases, document retrieval and the web. In particular, the language XML seems to become a...

Thomas Schwentick, Anca Muscholl, Peter Habermehl

Abstract. It is known that MSO logic for ordered unranked trees is undecidable ifPresburger constraints are allowed at children of nodes. We show here that a decidable logic is obtained if we use a...

Complexity of Hybrid Logics over Transitive Frames (2008)

Mundhenk, Martin, Schneider, Thomas, Schwentick, Thomas, Weber, Volker

This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid language extended...

Universität Dortmund (2008)

Anca Muscholl, Thomas Schwentick, Luc Segoufin

Motivated by reasoning tasks for XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data value from a...

General Terms (2008)

Mikołaj Bojańczyk, Thomas Schwentick, Lehrstuhl Informatik I

Motivated by reasoning tasks in the context of XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data...

On notions of regularity for data languages (2008)

Henrik Björklund, Thomas Schwentick

Abstract. Motivated by considerations in XML theory and model checking, data strings have been introduced as an extension of finite alphabet strings which carry, at each position, a symbol and a data...

Algorithms, Theory (2008)

Georg Gottlob, Zoltán Miklós, Thomas Schwentick, Lehrstuhl Informatik I

comlab.ox.ac.uk The generalized hypertree width GHW (H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated...

and (2008)

1 Introduction Automata for XML — A Survey (2008)

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

Since the arrival of XML as a data representation language, concepts from formal language theory like regular expressions, grammars and automata have been used for various purposes, e.g., as

and (2008)

ABSTRACT Expressiveness of XSDs: from Practice to Theory, There and Back Again (2008)

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

Geert Jan Bex, Frank Neven, Wim Martens, Thomas Schwentick

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML...

General Terms Theory (2008)

Mikołaj Bojańczyk, Thomas Schwentick, Lehrstuhl Informatik I, Claire David, Luc Segoufin, Anca Muscholl

Motivated by reasoning tasks in the context of XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data...

and (2008)

A little bit infinite? On adding data to finitely labelled structures (Abstract) (2008)

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

A little bit infinite? On adding data to finitely labelled structures (Abstract) (2008)

Finite or infinite strings or trees with labels from a finite alphabet play an important role in computer science. They can be used to model many interesting objects including system runs in...

03. A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract) (2008)

Finite or infinite strings or trees with labels from a finite alphabet play an important role in computer science. They can be used to model many interesting objects including system runs in...

08171 Summary -- Beyond the Finite: New Challenges in Verification and Semistructured Data (2008)

Finite or innite strings or trees with labels from a nite alphabet play an important role in computer science. They can be used to model many interesting objects including system runs in Automated...

Muscholl, Anca, Ramanujam, Ramaswamy, Rusinowitch, Michaël, Schwentick, Thomas, Vianu, Victor

Exploring the interaction of model checking and database static analysis techniques in the development of novel approaches to the verification of software systems handling data.

08171 Abstracts Collection -- Beyond the Finite: New Challenges in Verification and Semistructured Data (2008)

Muscholl, Anca, Ramanujam, Ramaswamy, Rusinowitch, Michaël, Schwentick, Thomas, Vianu, Victor

From 20.04. to 25.04.2008, the Dagstuhl Seminar 08171 ``Beyond the Finite: New Challenges in Verification and Semistructured Data'' was held in the International Conference and Research Center...

d (2007)

Frederic Green, Johannes Kobler, Kenneth W. Regan, Thomas Schwentick

fg This paper studies the class MP of languages which can be solved in polynomial time with the additional information of one bit from a #P function f. The middle bit of f(x) is shown to be as...

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines (2007)

Clemens Lautemann Nicole, Nicole Schweikardt, Thomas Schwentick

. The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this...

Solving Equations in the Relational Algebra (2007)

Joachim Biskup, Jan Paredaens, U. Antwerp, Thomas Schwentick, U. Mainz, ...

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

On Positive P (2007)

Clemens Lautemann, Thomas Schwentick, Iain A. Stewart

Continuing a line of research opened up by Grigni and Sipser in [4] and further pursued in [10], we show that a wide variety of equivalent characterizations of P still remain equivalent when...

Query Automata (Extended Abstract) (2007)

On the Power of Polynomial Time Bit-Reductions (Extended Abstract) (2007)

It is common to model structured document databases by context-free and extended context-free grammars. A crucial difference is that the derivation trees of the former are ranked, while those of the...

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner, Theoretische Informatik

For a nondeterministic polynomial time Turing machine M and an input string x, the leaf string of M on x is the 0-1-sequence of leaf-values (0 ¸ reject, 1 ¸ accept) of the computation tree of M...

de (2007)

Fb Iv Informatik, Thomas Schwentick, Anca Muscholl

A query against a database behind a site like Napster may search, e.g., for all users who have downloaded more jazz titles than pop music titles. In order to express such queries, we extend classical...

U. Toronto (2007)

Michael Benedikt, Leonid Libkin, Thomas Schwentick, U. Marburg, Luc Segou N

We study analogs of classical relational calculus in the context of strings. We start by studying string logics. Taking a classical model-theoretic approach, we x a set of string operations and look...

2 (2007)

Pierre Mckenzie, Thomas Schwentick, Heribert Vollmer

Abstract. First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic nite transducers (NFTs). It is shown here that this...

1 (2007)

Pierre Mckenzie, Thomas Schwentick, Heribert Vollmer

Abstract. Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over innite alphabets. These are conservative extensions of classical automata...

2 (2007)

Abstract. First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this...

U. Toronto and Bell Labs (2007)

Michael Benedikt, Leonid Libkin, Thomas Schwentick, U. Mainz, Luc Segou N

We study relational calculi with support for string operations. Most prior proposals were based on adding the operation of concatenation to rst-order logic. Such an extension is problematic as the...

Solving equations in the relational algebra Joachim Biskup, U. (2007)

Jan Paredaens, U. Antwerp, Thomas Schwentick, U. Mainz, U. Limburg

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic (2007)

Martin Grohe, Thomas Schwentick

A query is local if the decision of whether a tuple in a structure satises this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant...

1 (2007)

Martin Grohe, Thomas Schwentick

Abstract. A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by...

U. Toronto (2007)

Michael Benedikt, Leonid Libkin, Thomas Schwentick, U. Mainz, Luc Segou N

We study algebras of denable string relations { classes of regular n-ary relations that arise as the denable sets within a model whose carrier is the set of all strings. We show that the largest such...

3 (2007)

Thomas Schwentick, Anca Muscholl, Peter Habermehl, Tu Munchen I

Abstract. In [22], it was shown that MSO logic for ordered unranked trees becomes undecidable if Presburger constraints are allowed at children of nodes. We now show that a decidable logic is...

Simple off the shelf abstractions for XML schem (2007)

Martens, Wim, NEVEN, Frank, Schwentick, Thomas

Although the advent of XML Schema [25] has rendered DTDs obsolete, research on practical XML optimization is mostly biased towards DTDs and tends to largely ignore XSDs (some notable exceptions...

Deterministic top-down tree automata: past, present, future (2007)

MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

Abstract (2007)

Claire David, Thomas Schwentick, Anca Muscholl, Luc Segoufin

In a data word each position carries a label from a finite alphabet and a data value from some infinite domain. These models have been already considered in the realm of semistructured data, timed...

Bounded-variable fragments of hybrid logics (2007)

Thomas Schwentick, Volker Weber

Abstract. Hybrid logics extend modal logics by first-order concepts, in particular they allow a limited use of variables. Unfortunately, in general, satisfiability for hybrid formulas is undecidable...

06451 Executive Summary -- Circuits, Logic, and Games (2007)

Schwentick, Thomas, Thérien, Denis, Vollmer, Heribert

In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.

06451 Abstracts Collection -- Circuits, Logic, and Games (2007)

Schwentick, Thomas, Thérien, Denis, Vollmer, Heribert

From 08.11.06 to 10.11.06, the Dagstuhl Seminar 06451 ``Circuits, Logic, and Games'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...

The Complexity of Reasoning about Pattern-based XML Schemas (2007)

Kasneci, Gjergji, Schwentick, Thomas

In a recent paper, Martens et al. introduced a specification mechanism for {XML} tree languages, based on rules of the form r ! s, where r, s are regular expressions. Sets of such rules can be...

On the complexity of XPath containment in the presence of disjunction, DTDs, and variables (2006)

Neven, Frank, Schwentick, Thomas

XPath is a simple language for navigating an XML-tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. We...

Expressiveness and complexity of XML Schema (2006)

Martens, Wim, NEVEN, Frank, Schwentick, Thomas, BEX, Geert Jan

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

Two-Variable Logic on Words with Data (2006)

Bojanczyk, Mikolaj, Muscholl, Anca, Schwentick, Thomas, Segoufin, Luc, David, Claire

In a data word each position carries a label from a finite alphabet and a data value from some infinite domain. These models have been already considered in the realm of semistructured data, timed...

Two-Variable Logic on Data Trees and XML Reasoning (2006)

Bojanczyk, Mikolaj, David, Claire, Muscholl, Anca, Schwentick, Thomas, Segoufin, Luc

Motivated by reasoning tasks in the context of XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data...

Expressive power of pebbles Automata (2006)

Bojanczyk, Mikolaj, Samuelides, Mathias, Schwentick, Thomas, Segoufin, Luc

Two variants of pebble tree-walking automata on trees are considered that were introduced in the literature. It is shown that for each number of pebbles, the two models have the same expressive power...

Expressiveness and complexity of XML Schema (2006)

Expressiveness and complexity of XML Schema (2006)

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas, BEX, Geert Jan

The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical...

Expressive power of pebbles Automata (2006)

Bojanczyk, Mikolaj, Samuelides, Mathias, Schwentick, Thomas, Segoufin, Luc

Two variants of pebble tree-walking automata on trees are considered that were introduced in the literature. It is shown that for each number of pebbles, the two models have the same expressive power...

Two-Variable Logic on Words with Data (2006)

Bojanczyk, Mikolaj, Muscholl, Anca, Schwentick, Thomas, Segoufin, Luc, David, Claire

In a data word each position carries a label from a finite alphabet and a data value from some infinite domain. These models have been already considered in the realm of semistructured data, timed...

Two-Variable Logic on Data Trees and XML Reasoning (2006)

Bojanczyk, Mikolaj, David, Claire, Muscholl, Anca, Schwentick, Thomas, Segoufin, Luc

Motivated by reasoning tasks in the context of XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data...

Expressive power of pebble automata (2006)

Mathias Samuelides, Thomas Schwentick, Luc Segoufin

Abstract. Two variants of pebble tree-walking automata on trees are considered that were introduced in the literature. It is shown that for each number of pebbles, the two models have the same...

On the complexity of XPath containment in the presence of disjunction, DTDs, and variables (2006)

Expressive power of pebble automata (2006)

XPath is a simple language for navigating an XML-tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. We...

Mathias Samuelides, Thomas Schwentick

Abstract. Two variants of pebble tree-walking automata on binary trees are considered that were introduced in the literature. It is shown that for each number of pebbles, the two models have the same...

Which XML Schemas Admit 1-Pass Preorder Typing? (2005)

Expressiveness of XSDs: from practice to theory, there and back again (2005)

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a...

05061 Abstracts Collection - Foundations of Semistructured Data (2005)

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML...

Schwentick, Thomas, Suciu, D.

From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

Which XML Schemas Admit 1-Pass Preorder Typing? (2005)

Expressiveness of XSDs: from practice to theory, there and back again (2005)

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a...

05061 Abstracts Collection - Foundations of Semistructured Data (2005)

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML...

NEVEN, Frank, Schwentick, Thomas, Suciu, D.

From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

Expressiveness of XSDs: from practice theory, there and back again (2005)

BEX, Geert, MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

Which XML Schemas Admit 1-Pass Preorder Typing? (2005)

MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a...

Expressiveness of XSDs: from practice to theory, there and back again (2005)

BEX, Geert Jan, MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML...

05061 Abstracts Collection - Foundations of Semistructured Data (2005)

NEVEN, Frank, Schwentick, Thomas, Suciu, D.

From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

Expressiveness of XSDs: from practice theory, there and back again (2005)

BEX, Geert, MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

Dynamic Complexity Theory Revisited (2005)

Volker Weber, Thomas Schwentick

Abstract. Dynamic complexity asks for the effort needed to maintain the information about properties of a structure under operations changing the structure. This paper introduces a refined notion of...

Complexity of hybrid logics over transitive frames (2005)

Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber

Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with ↓...

Which XML schemas admit 1-pass preorder typing (2005)

Dynamic Complexity Theory Revisited (2005)

Unfortunately, DTDs are limited in various ways. A particular limitation is that the type of an element can only depend on its tag but not on its context. As an example, in Figure 1 it is not...

Volker Weber, Thomas Schwentick

Dynamic complexity investigates the required effort to maintain knowledge about a property of a structure under changing operations. This article introduces a refined notion of dynamic problems which...

Complexity of Hybrid Logics over Transitive Frames (2005)

Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber

This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with is...

Complexity of hybrid logics over transitive frames (2005)

Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber

Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with #...

Complexity of hybrid logics over transitive frames (2005)

Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber

Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with ↓...

05061 Abstracts Collection -- Foundations of Semistructured Data (2005)

Neven, Frank, Schwentick, Thomas, Suciu, Dan

From 06.02.05 to 11.02.05, the Dagstuhl Seminar 05061 ``Foundations of Semistructured Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

05061 Summary -- Foundations of Semi-structured Data (2005)

Neven, Frank, Schwentick, Thomas, Suciu, Dan

As in the first seminar on this topic, the aim o the workshop was to bring together people from the areas related to semi-structured data. However, besides the presentation of recent work, this time...

Complexity of Decision Problems for Simple Regular Expressions. (2004)

Finite state machines for strings over infinite alphabets (2004)

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

Solving equations in the relational algebra (2004)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Biskup, Joachim, Paredaens, Jan, Schwentick, Thomas

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

Counting in trees for free (2004)

Seidl, Helmut, Schwentick, Thomas, Muscholl, Anca, Habermehl, Peter

In [22], it was shown that MSO logic for ordered unranked trees becomes undecidable if Presburger constraints are allowed at children of nodes. We now show that a decidable logic is obtained if we...

Complexity of Decision Problems for Simple Regular Expressions. (2004)

Finite state machines for strings over infinite alphabets (2004)

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

Solving equations in the relational algebra (2004)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Biskup, Joachim, Paredaens, Jan, Schwentick, Thomas

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

Complexity of Decision Problems for Simple Regular Expressions. (2004)

MARTENS, Wim, NEVEN, Frank, Schwentick, Thomas

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

Finite state machines for strings over infinite alphabets (2004)

NEVEN, Frank, Schwentick, Thomas, Vianu, Victor

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Solving equations in the relational algebra (2004)

VAN DEN BUSSCHE, Jan, Biskup, Joachim, Paredaens, Jan, Schwentick, Thomas

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

Counting in trees for free (2004)

Seidl, Helmut, Schwentick, Thomas, Muscholl, Anca, Habermehl, Peter

In [22], it was shown that MSO logic for ordered unranked trees becomes undecidable if Presburger constraints are allowed at children of nodes. We now show that a decidable logic is obtained if we...

Finite state machines for strings over infinite alphabets (2004)

Finite state machines for strings over infinite alphabets (2004)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Complexity of decision problems for simple regular expressions (2004)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

On the power of tree-walking automata. (2003)

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

XPath containment in the presence of disjunction, DTDs, and variables. (2003)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms...

On the power of tree-walking automata. (2003)

XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In...

XPath containment in the presence of disjunction, DTDs, and variables. (2003)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms...

On the power of tree-walking automata. (2003)

XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In...

XPath containment in the presence of disjunction, DTDs, and variables. (2003)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve a better understanding of their expressiveness, we characterize them in terms...

Automata- and Logic-Based Pattern Languages for Tree-Structured Data (2003)

XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. In...

XPath containment in the presence of disjunction, DTDs, and variables (2003)

This paper surveys work of the authors on pattern languages for tree-structured data with XML as the main application in mind. The main focus is on formalisms from formal language theory and logic....

XML: model, schemas, types, logics, and queries (2003)

Abstract. XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of...

Nils Klarlund, Thomas Schwentick, Dan Suciu At

In this chapter, we shall see that the suspicion is easy dispelled. We look at techniques now used in practice for dealing with XML trees, and we note how they depart from old-fashioned uses. Since...

XPath containment in the presence of disjunction, DTDs, and variables (2003)

XML: model, schemas, types, logics, and queries (2003)

Abstract. XPath is a simple language for navigating an XML tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of...

Nils Klarlund, Thomas Schwentick, Dan Suciu

It is intriguing that something as bland as a syntax for trees has become one of the leading buzzwords of the Internet era. XML (eXtended Markup Language) is the name of this notation, which evolved...

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

Finite State Machines for Strings over Infinite Alphabets (2002)

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

Solving equations in the relational algebra (2001)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Biskup, Joachim, Paredaens, Jan, Schwentick, Thomas, Bussche, Jan Van Den

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query...

Towards Regular Languages over Infinite Alphabets (2001)

Automata- and Logic-Based Pattern Languages for Tree-Structured Data (2001)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Towards Regular Languages over Infinite Alphabets (2001)

This paper surveys work of the authors on pattern languages for tree-structured data with XML as the main application in mind. The main focus is on formalisms from formal language theory and logic....

Automata- and Logic-Based Pattern Languages for Tree-Structured Data (2001)

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Towards Regular Languages over Infinite Alphabets (2001)

This paper surveys work of the authors on pattern languages for tree-structured data with XML as the main application in mind. The main focus is on formalisms from formal language theory and logic....

NEVEN, Frank, Schwentick, Thomas, Vianu, Victor

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics...

Automata- and logic-based pattern languages for tree-structured data. Unpublished (2001)

Partially-Ordered Two-Way Automata: A New Characterization of DA (2001)

Thomas Schwentick, Heribert Vollmer

Abstract. In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it. Equivalently we may assume that the states set is partially...

Second-order logic over strings: Regular and nonregular fragments (2001)

Thomas Eiter, Georg Gottlob, Thomas Schwentick

Abstract. By a well-known result due to Buchi and Trakhtenbrot, all monadic second-order sentences over words describe regular languages. In this paper, we investigate prefix classes of general...

Automata- and logic-based pattern languages for tree-structured data. Unpublished (2001)

When is the evaluation of conjunctive queries tractable (2001)

Abstract. This paper surveys work of the authors on pattern languages for tree-structured data with XML as the main application in mind. The main focus is on formalisms from formal language theory...

Martin Grohe, Thomas Schwentick, Inria Rocquencourt

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NPcomplete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined...

When is the evaluation of conjunctive queries tractable (2001)

Martin Grohe, Thomas Schwentick, Luc Segoufin

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NP-complete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined...

String operations in query languages (2001)

Michael Benedikt, Leonid Libkin, U. Toronto, Thomas Schwentick, U. Mainz, Luc Segou N

We study relational calculi with support for string operations. While SQL restricts the ability to mix string pattern-matching and relational operations, prior proposals for embedding SQL in a...

Partially-Ordered Two-Way Automata: A New Characterization of DA (2001)

Thomas Schwentick, Heribert Vollmer

In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it. This is equivalent to the property that the states set is partially...

When is the evaluation of conjunctive queries tractable (2001)

Martin Grohe, Thomas Schwentick, Luc Segoufin, Inria Rocquencourt

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NPcomplete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined...

String operations in query languages (2001)

Michael Benedikt, Leonid Libkin, U. Toronto, Bell Labs, Thomas Schwentick, U. Mainz, ...

We study relational calculi with support for string operations. Most prior proposals were based on adding the operation of concatenation to first-order logic. Such an extension is problematic as the...

Partially-ordered Two-way Automata: (2001)

New Characterization Of, Thomas Schwentick, Heribert Vollmer

In this paper, we consider nite automata with the restriction that whenever the automaton leaves a state it never returns to it.

Towards regular languages over infinite alphabets (2001)

Automata- and logic-based pattern languages for tree-structured data. Unpublished (2001)

Abstract. Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata...

On the Power of Tree-Walking Automata (2000)

Abstract. This paper surveys work of the authors on pattern languages for tree-structured data with XML as the main application in mind. The main focus is on formalisms from formal language theory...

Expressive and Efficient Pattern Languages for Tree-Structured Data. (2000)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of...

On the Power of Tree-Walking Automata (2000)

Expressive and Efficient Pattern Languages for Tree-Structured Data. (2000)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of...

On the Power of Tree-Walking Automata (2000)

Expressive and Efficient Pattern Languages for Tree-Structured Data. (2000)

Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of...

Existential second-order logic over graphs: Charting the tractability frontier (2000)

Georg Gottlob, Tu Wien, Phokion G. Kolaitis, Thomas Schwentick

Fagin's theorem, the rst important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is denable by an existential secondorder formula. In this paper,...

On Diving in Trees (2000)

The Many Faces of a Translation (2000)

The paper is concerned with queries on tree-structured data. It denes fragments of rstorder logic (FO) and FO extended by regular expressions along paths. These fragments have the same expressive...

Pierre Mckenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts...

The Many Faces of a Translation (2000)

Pierre Mckenzie, Thomas Schwentick, Denis Therien, Heribert Vollmer

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic nite transducers (NFTs). It is shown here that this characterization lifts...

On the power of tree-walking automata (2000)

The many faces of a translation (2000)

Abstract. Tree-walking automata (TWAs) recently received new attention in the elds of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in...

Pierre Mckenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts...

On the power of tree-walking automata (2000)

Automata for Unary Queries on Trees (1999)

Abstract. Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in...

Query Automata (1999)

Automata for Unary Queries on Trees (1999)

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

Query Automata (1999)

Automata for Unary Queries on Trees (1999)

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

Query Automata (1999)

Expressive and efficient pattern languages for tree-structured data (1999)

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

it turned out that the proof of Proposition 2 and therefore of Theorem 3 (stating an exponential time upper bound) is wrong. The given algorithm is not correct. So far, we have not been able to find...

Query automata (1999)

The Descriptive Complexity Approach to LOGCFL (1999)

A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an...

Clemens Lautemann Pierre, Thomas Schwentick, Heribert Vollmer

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...

Local Normal Forms for First-Order Logic with Applications to Games and Automata (1999)

Local Normal Forms for First-Order Logic with Applications to Games and Automata (1999)

this paper are automata theory and descriptive complexity. Since Buchi's and Elgot's famous characterization of the regular string languages as the sets of models of (existential) monadic...

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines (1999)

this paper are automata theory and descriptive complexity. Since Buchi's and Elgot's famous characterization of the regular string languages as the sets of models of (existential) monadic...

Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick

. The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this...

The Descriptive Complexity Approach to LOGCFL (1999)

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...

XML schemas without order (1999)

Frank Neven Limburgs, Frank Neven, Thomas Schwentick

XML schemas consist of context-free grammars that allow regular expressions on the right-hand side of productions. In the schema definition language ScmDL, XML schemas are enhanced to, among other...

The Descriptive Complexity Approach to LOGCFL (1999)

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer

Building upon the known generalized-quanti er-based rst-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from...

Local Normal Forms for First-Order Logic with Applications to Games and Automata (1999)

The descriptive complexity approach to LOGCFL (1998)

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x 1,...,x l, ∀ y, φ where φ is r-local around y, i.e....

Lautemann, Clemens, McKenzie, Pierre, Schwentick, Thomas, Vollmer, Heribert

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising...

Local normal forms for first-order logic with applications to games and automata (1998)

Local Normal Forms for First-Order Logic with Applications to Games and Automata (1998)

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form 9x1; : : : ; x l 8y ' where ' is r-local around y, i. e....

Descriptive Complexity, Lower Bounds and Linear Time (1998)

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form 9x 1 ; : : : ; x l 8y' where ' is r-local around y, i. e....

Subclasses of Binary NP (1998)

This paper surveys two related lines of research: ffl Logical characterizations of (non-deterministic) linear time complexity classes, and ffl non-expressibility results concerning sublogics of...

DURAND, ARNAUD, LAUTEMANN, CLEMENS, SCHWENTICK, THOMAS

Binary NP consists of all sets of finite structures which are expressible in existential second-order logic with second-order quantification restricted to relations of arity 2. We look at semantical...

Padding and the Expressive Power of Existential Second-Order Logics (1997)

Local Normal Forms for First-Order Logic with Applications to Games and Automata (1997)

Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded...

The Power of the Middle Bit of a #P Function (1997)

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form 9x1 ; : : : ; x l 8y' where ' is r-local around y, i. e....

Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, Jacobo Torán

This paper studies the class MP of languages which can be solved in polynomial time with the additional information of one bit from a #P function f. The middle bit of f(x) is shown to be as powerful...

Subclasses of Binary NP (1996)

Arnaud Durand, Clemens Lautemann, Thomas Schwentick

Binary NP consists of all sets of finite structures which are expressible in existential second order logic with second order quantification restricted to relations of arity 2. We look at semantical...

On Bijections vs. Unary Functions (1996)

On Winning Ehrenfeucht Games and Monadic NP (1996)

. A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses...

Algebraic and Logical Characterizations of Deterministic Linear Time Classes (1996)

Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures. In this...

The power of the middle bit of a #P function (1995)

In this paper an algebraic characterization of the class DLIN of functions that can be computed in linear time by a deterministic RAM using only numbers of linear size is given. This class was...

Green, Frederic, Köbler, Johannes, Regan, Kenneth W., Schwentick, Thomas, Toran, Jacobo

The power of the middle bit of a #P function (1995)

Green, Frederic, Köbler, Johannes, Regan, Kenneth W., Schwentick, Thomas, Toran, Jacobo

On winning Ehrenfeucht games and monadic NP / (1995)

Schwentick, Thomas.

Auch Sekundärausg.

Graph Connectivity, Monadic NP and Built-in Relations of Moderate Degree (1995)

Fragments of Binary NP (1995)

. It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph...

Arnaud Durand, Clemens Lautemann, Thomas Schwentick

Binary NP is existential second order logic where second order quantification is over relations of arity 2. We look at semantical restrictions of binary NP, where the second order quantifiers range...

Logics For Context-Free Languages (1995)

Clemens Lautemann, Thomas Schwentick, Denis Thérien

. We define matchings, and show that they capture the essence of context--freeness. More precisely, we show that the class of context-- free languages coincides with the class of those sets of...

The power of the middle bit of a #P function (1995)

Frederic Green, Thomas Schwentick, Johannes Köbler, Keneth W. Regan, Jacobo Torán, ...

We introduce the class MP of languages L which can be solved in polynomial time with the additional information of one bit from a #P function f. We prove that the polynomial hierarchy and the classes...

A Note on Set Bit Enumeration (1994)

Thomas Schwentick, J. Ramachandran

An m-set-bit-enumerator for a function f is a source of information that, in response to the query: "How many set bits (`1's) are there in the binary representation of f(x)?", computes...

Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages (1994)

Bernd Borchert, Gutachter Prof, Dr. Klaus Ambos-spies, Thomas Schwentick, ...

this paper were shown in the preceeding Chapters 3 and 4. In this chapter some other models of nondeterministic computation will be considered. For each model the notion of a predicate class is...

Graph Connectivity and Monadic NP (1994)