Thomas Schwentick

According to our database1, Thomas Schwentick authored at least 174 papers between 1992 and 2018.

Collaborative distances :

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151).
Dagstuhl Manifestos, 2018

Streaming Rewriting Games: Winning Strategies and Complexity.
CoRR, 2018

Conjunctive query containment over trees using schema information.
Acta Inf., 2018

2017
BonXai: Combining the Simplicity of DTD with the Expressiveness of XML Schema.
ACM Trans. Database Syst., 2017

Games for Active XML Revisited.
Theory Comput. Syst., 2017

Dynamic conjunctive queries.
J. Comput. Syst. Sci., 2017

Parallel-Correctness and Transferability for Conjunctive Queries.
J. ACM, 2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).
Dagstuhl Reports, 2017

Dynamic Conjunctive Queries.
CoRR, 2017

Dynamic Complexity under Definable Changes.
CoRR, 2017

A Strategy for Dynamic Programs: Start over and Muddle through.
CoRR, 2017

Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151).
CoRR, 2017

Reasoning on data partitioning for single-round multi-join evaluation in massively parallel systems.
Commun. ACM, 2017

Dynamic Complexity under Definable Changes.
Proceedings of the 20th International Conference on Database Theory, 2017

A Strategy for Dynamic Programs: Start over and Muddle Through.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Data partitioning for single-round multi-join evaluation in massively parallel systems.
SIGMOD Record, 2016

Research Directions for Principles of Data Management (Abridged).
SIGMOD Record, 2016

Dynamic complexity: recent updates.
SIGLOG News, 2016

Foundations of Data Management (Dagstuhl Perspectives Workshop 16151).
Dagstuhl Reports, 2016

Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation.
Proceedings of the 19th International Conference on Database Theory, 2016

2015
On the quantifier-free dynamic complexity of Reachability.
Inf. Comput., 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).
Dagstuhl Reports, 2015

Static Analysis for Logic-Based Dynamic Programs.
CoRR, 2015

Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation.
CoRR, 2015

Reachability is in DynFO.
CoRR, 2015

BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Parallel-Correctness and Transferability for Conjunctive Queries.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Games for Active XML Revisited.
Proceedings of the 18th International Conference on Database Theory, 2015

Reachability is in DynFO.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Static Analysis for Logic-based Dynamic Programs.
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

2014
Games for Active XML Revisited.
CoRR, 2014

Parallel-Correctness and Transferability for Conjunctive Queries.
CoRR, 2014

The price of query rewriting in ontology-based data access.
Artif. Intell., 2014

Dynamic Conjunctive Queries.
Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

Reasoning about XML Constraints based on XML-to-relational mappings.
Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

2013
Preface of Special Issue on Theoretical Aspects of Computer Science.
Theory Comput. Syst., 2013

On the quantifier-free dynamic complexity of Reachability.
CoRR, 2013

A Short Note on Two-Variable Logic with a Linear Order Successor and a Preorder Successor.
CoRR, 2013

Perspectives of Dynamic Complexity.
Proceedings of the Logic, Language, Information, and Computation, 2013

The Dynamic Complexity of the Reachability Problem on Graphs.
Proceedings of the Reachability Problems - 7th International Workshop, 2013

On the Quantifier-Free Dynamic Complexity of Reachability.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Validity of Tree Pattern Queries with Respect to Schema Information.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

XML Schema Management: A Challenge for Automata Theory.
Proceedings of the Language and Automata Theory and Applications, 2013

Dynamic Communicating Automata and Branching High-Level MSCs.
Proceedings of the Language and Automata Theory and Applications, 2013

On optimum left-to-right strategies for active context-free games.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012
The dynamic complexity of formal languages.
ACM Trans. Comput. Log., 2012

Developing and Analyzing XSDs through BonXai.
PVLDB, 2012

Theoretical Aspects of Computer Science.
Theory Comput. Syst., 2012

On optimum left-to-right strategies for active context-free games
CoRR, 2012

Two-Variable Logic with Two Order Relations
Logical Methods in Computer Science, 2012

Feasible Automata for Two-Variable Logic with Successor on Data Words.
Proceedings of the Language and Automata Theory and Applications, 2012

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, 2012

Foundations of XML Based on Logic and Automata: A Snapshot.
Proceedings of the Foundations of Information and Knowledge Systems, 2012

2011
Two-variable logic on data words.
ACM Trans. Comput. Log., 2011

Conjunctive query containment over trees.
J. Comput. Syst. Sci., 2011

Expressiveness of Hybrid Temporal Logic on Data Words.
Electr. Notes Theor. Comput. Sci., 2011

Foundations of distributed data management (Dagstuhl Seminar 11421).
Dagstuhl Reports, 2011

A note on the expressive power of linear orders
Logical Methods in Computer Science, 2011

Feasible Automata for Two-Variable Logic with Successor on Data Words
CoRR, 2011

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs
CoRR, 2011

Frontmatter, Table of Contents, Preface, Conference Organization.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Two-variable logic and key constraints on data words.
Proceedings of the Database Theory, 2011

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs.
Proceedings of the 24th International Workshop on Description Logics (DL 2011), 2011

2010
Inference of concise regular expressions and DTDs.
ACM Trans. Database Syst., 2010

On notions of regularity for data languages.
Theor. Comput. Sci., 2010

Complexity of hybrid logics over transitive frames.
J. Applied Logic, 2010

Logik und Automaten: ein echtes Dreamteam.
Informatik Spektrum, 2010

Temporal Logics on Words with Multiple Data Values
CoRR, 2010

Table of Contents - 27th International Symposium on Theoretical Aspects of Computer Science.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Schema design for XML repositories: complexity and tractability.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Temporal Logics on Words with Multiple Data Values.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

10061 Executive Summary - Circuits, Logic, and Games.
Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

10061 Abstracts Collection - Circuits, Logic, and Games.
Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

Two-Variable Logic with Two Order Relations - (Extended Abstract).
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey.
Proceedings of the Fields of Logic and Computation, 2010

2009
Complexity of Decision Problems for XML Schemas and Chain Regular Expressions.
SIAM J. Comput., 2009

Foreword.
Theory Comput. Syst., 2009

Volker Weber.
Journal of Logic, Language and Information, 2009

Generalized hypertree decompositions: NP-hardness and tractable variants.
J. ACM, 2009

Two-variable logic on data trees and XML reasoning.
J. ACM, 2009

On the Hybrid Extension of CTL and CTL+
CoRR, 2009

The Dynamic Complexity of Formal Languages.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

On the Hybrid Extension of CTL and CTL+.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Tree Projections: Game Characterization and Computational Aspects.
Proceedings of the Graph Theory, 2009

2008
Introduction to ICDT 2007 special section.
ACM Trans. Database Syst., 2008

Dynamic Complexity of Formal Languages
CoRR, 2008

Complexity of Hybrid Logics over Transitive Frames
CoRR, 2008

A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract).
Proceedings of the STACS 2008, 2008

Optimizing Conjunctive Queries over Trees Using Schema Information.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

08171 Summary - Beyond the Finite: New Challenges in Verification and Semistructured Data.
Proceedings of the Beyond the Finite: New Challenges in Verification and Semistructured Data, 20.04., 2008

08171 Abstracts Collection - Beyond the Finite: New Challenges in Verification and Semistructured Data.
Proceedings of the Beyond the Finite: New Challenges in Verification and Semistructured Data, 20.04., 2008

Counting in trees.
Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

Deterministic top-down tree automata: past, present, and future.
Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007
Simple off the shelf abstractions for XML schema.
SIGMOD Record, 2007

Dynamic Complexity Theory Revisited.
Theory Comput. Syst., 2007

Automata for XML - A survey.
J. Comput. Syst. Sci., 2007

Bounded-Variable Fragments of Hybrid Logics.
Proceedings of the STACS 2007, 2007

The complexity of reasoning about pattern-based XML schemas.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

Generalized hypertree decompositions: np-hardness and tractable variants.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

On Notions of Regularity for Data Languages.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Conjunctive Query Containment over Trees.
Proceedings of the Database Programming Languages, 11th International Symposium, 2007

2006
Expressiveness and complexity of XML Schema.
ACM Trans. Database Syst., 2006

Active Context-Free Games.
Theory Comput. Syst., 2006

On the complexity of XPath containment in the presence of disjunction, DTDs, and variables.
Logical Methods in Computer Science, 2006

The many faces of a translation.
J. Comput. Syst. Sci., 2006

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

Inference of Concise DTDs from XML Data.
Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Two-variable logic on data trees and XML reasoning.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Two-Variable Logic on Words with Data.
Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Expressive Power of Pebble Automata.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

06451 Abstracts Collection -- Circuits, Logic, and Games .
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

06451 Executive Summary -- Circuits, Logic, and Games .
Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

2005
Expressiveness of XSDs: from practice to theory, there and back again.
Proceedings of the 14th international conference on World Wide Web, 2005

Dynamic Complexity Theory Revisited.
Proceedings of the STACS 2005, 2005

Which XML Schemas Admit 1-Pass Preorder Typing?
Proceedings of the Database Theory, 2005

05061 Summary - Foundations of Semi-structured Data.
Proceedings of the Foundations of Semistructured Data, 6.-11. February 2005, 2005

05061 Abstracts Collection - Foundations of Semistructured Data.
Proceedings of the Foundations of Semistructured Data, 6.-11. February 2005, 2005

On the Complexity of Equational Horn Clauses.
Proceedings of the Automated Deduction, 2005

2004
Finite state machines for strings over infinite alphabets.
ACM Trans. Comput. Log., 2004

XPath query containment.
SIGMOD Record, 2004

Solving Equations in the Relational Algebra.
SIAM J. Comput., 2004

Existential second-order logic over graphs: Charting the tractability frontier.
J. ACM, 2004

Active Context-Free Games.
Proceedings of the STACS 2004, 2004

Trees, Automata and XML.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Complexity of Decision Problems for Simple Regular Expressions.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Counting in Trees for Free.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Definable relations and first-order query languages over strings.
J. ACM, 2003

On the power of tree-walking automata.
Inf. Comput., 2003

Numerical document queries.
Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

XPath Containment in the Presence of Disjunction, DTDs, and Variables.
Proceedings of the Database Theory, 2003

XML: Model, Schemas, Types, Logics, and Queries.
Proceedings of the Logics for Emerging Applications of Databases [outcome of a Dagstuhl seminar], 2003

2002
Query automata over finite trees.
Theor. Comput. Sci., 2002

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time.
SIAM J. Comput., 2002

2001
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci., 2001

Solving equations in the relational algebra
CoRR, 2001

When is the evaluation of conjunctive queries tractable?
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Automata-and Logic-Based Pattern Languages for Tree-Structured Data.
Proceedings of the Semantics in Databases, 2001

String Operations in Query Languages.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Towards Regular Languages over Infinite Alphabets.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

A Model-Theoretic Approach to Regular String Relations.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Partially-Ordered Two-Way Automata: A New Characterization of DA.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Second-Order Logic over Strings: Regular and Non-regular Fragments.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000
Locality of order-invariant first-order formulas.
ACM Trans. Comput. Log., 2000

Expressive and Efficient Pattern Languages for Tree-Structured Data.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

On Diving in Trees.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

On the Power of Tree-Walking Automata.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

The Many Faces of a Translation.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Logically defined queries on trees.
Grundlagen von Datenbanken, 2000

Existential Second-Order Logic over Graphs: Charting the Tractability Frontier.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Local Normal Forms for First-Order Logic with Applications to Games and Automata.
Discrete Mathematics & Theoretical Computer Science, 1999

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines.
Proceedings of the STACS 99, 1999

The Descriptive Complexity Approach to LOGCFL.
Proceedings of the STACS 99, 1999

Query Automata.
Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31, 1999

Automata for Unary Queries on Trees.
Grundlagen von Datenbanken, 1999

1998
Subclasses of Binary NP.
J. Log. Comput., 1998

Positive Versions of Polynomial Time.
Inf. Comput., 1998

The Descriptive Complexity Approach to LOGCFL
Electronic Colloquium on Computational Complexity (ECCC), 1998

The descriptive complexity approach to LOGCFL
CoRR, 1998

Local Normal Forms for First-Order Logic with Applications to Games and Automata.
Proceedings of the STACS 98, 1998

Locality of Order-Invariant First-Order Formulas.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

Descriptive Complexity, Lower Bounds and Linear Time.
Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997
Algebraic and Logical Characterizations of Deterministic Linear Time Classes.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Padding and the Expressive Power of Existential Second-Order Logics.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
On Winning Ehrenfeucht Games and Monadic NP.
Ann. Pure Appl. Logic, 1996

On Bijections vs. Unary Functions.
Proceedings of the STACS 96, 1996

On Positive P.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
On winning Ehrenfeucht games and monadic NP.
PhD thesis, 1995

The Power of the Middle Bit of a #P Function.
J. Comput. Syst. Sci., 1995

Graph Connectivity, Monadic NP and Built-in Relations of Moderate Degree.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994
Graph Connectivity and Monadic NP
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Logics For Context-Free Languages.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993
On the Power of Polynomial Time Bit-Reductions (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
On the Power of Polynomial Bit-Reductions
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992


  Loading...