Thomas Schwentick

Jennifer Todtenhoefer

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Dynamic Constant Time Parallel Graph Algorithms with Sub-Linear Work.

[BibT_eX]

[DOI]

Jonas Schmidt

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Work-Efficient Query Evaluation with PRAMs.

[BibT_eX]

[DOI]

Jens Keppeler

Christopher Spinrath

Proceedings of the 26th International Conference on Database Theory, 2023

2022

Low-Latency Sliding Window Algorithms for Formal Languages.

[BibT_eX]

[DOI]

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Ackermann Award 2021.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

2021 ACM PODS Alberto O. Mendelzon Test-of-Time Award.

[BibT_eX]

[DOI]

Angela Bonifati

Rasmus Pagh

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Work-sensitive Dynamic Complexity of Formal Languages.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computation Structures, 2021

Automata and finite model theory.

[BibT_eX]

[DOI]

Wouter Gelade

Proceedings of the Handbook of Automata Theory., 2021

2020

Sketches of Dynamic Complexity.

[BibT_eX]

[DOI]

Nils Vortmeier

SIGMOD Rec., 2020

Distribution Constraints: The Chase for Distributed Data.

[BibT_eX]

[DOI]

Gaetano Geck

Proceedings of the 23rd International Conference on Database Theory, 2020

Dynamic Complexity Meets Parameterised Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2019

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

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

Parallel-Correctness and Parallel-Boundedness for Datalog Programs.

[BibT_eX]

[DOI]

Proceedings of the 22nd International Conference on Database Theory, 2019

Winning Strategies for Streaming Rewriting Games.

[BibT_eX]

[DOI]

Christian Coester

Martin Schuster

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

2018

Dynamic Complexity under Definable Changes.

[BibT_eX]

[DOI]

Nils Vortmeier

ACM Trans. Database Syst., 2018

Reasoning About XML Constraints Based on XML-to-Relational Mappings.

[BibT_eX]

[DOI]

Matthias Niewerth

Theory Comput. Syst., 2018

Reachability Is in DynFO.

[BibT_eX]

[DOI]

J. ACM, 2018

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

[BibT_eX]

[DOI]

Dagstuhl Manifestos, 2018

Streaming Rewriting Games: Winning Strategies and Complexity.

[BibT_eX]

[DOI]

Christian Coester

Martin Schuster

CoRR, 2018

Conjunctive query containment over trees using schema information.

[BibT_eX]

[DOI]

Acta Informatica, 2018

The Ackermann Award 2018.

[BibT_eX]

[DOI]

Dexter Kozen

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

BonXai: Combining the Simplicity of DTD with the Expressiveness of XML Schema.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2017

Games for Active XML Revisited.

[BibT_eX]

[DOI]

Martin Schuster

Theory Comput. Syst., 2017

Dynamic conjunctive queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Parallel-Correctness and Transferability for Conjunctive Queries.

[BibT_eX]

[DOI]

J. ACM, 2017

Finite and Algorithmic Model Theory (Dagstuhl Seminar 17361).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

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

[BibT_eX]

[DOI]

Commun. ACM, 2017

2016

Data partitioning for single-round multi-join evaluation in massively parallel systems.

[BibT_eX]

[DOI]

SIGMOD Rec., 2016

Research Directions for Principles of Data Management (Abridged).

[BibT_eX]

[DOI]

SIGMOD Rec., 2016

Dynamic complexity: recent updates.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2016

Foundations of Data Management (Dagstuhl Perspectives Workshop 16151).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

2015

On the quantifier-free dynamic complexity of Reachability.

[BibT_eX]

[DOI]

Inf. Comput., 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Static Analysis for Logic-based Dynamic Programs.

[BibT_eX]

[DOI]

Nils Vortmeier

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

2014

The price of query rewriting in ontology-based data access.

[BibT_eX]

[DOI]

Stanislav Kikot

Roman Kontchakov

Vladimir V. Podolskii

Michael Zakharyaschev

Artif. Intell., 2014

2013

Preface of Special Issue on Theoretical Aspects of Computer Science.

[BibT_eX]

[DOI]

Christoph Dürr

Theory Comput. Syst., 2013

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

[BibT_eX]

[DOI]

Amaldev Manuel

CoRR, 2013

Perspectives of Dynamic Complexity.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information, and Computation, 2013

The Dynamic Complexity of the Reachability Problem on Graphs.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 7th International Workshop, 2013

Validity of Tree Pattern Queries with Respect to Schema Information.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

XML Schema Management: A Challenge for Automata Theory.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2013

Dynamic Communicating Automata and Branching High-Level MSCs.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2013

On optimum left-to-right strategies for active context-free games.

[BibT_eX]

[DOI]

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012

The dynamic complexity of formal languages.

[BibT_eX]

[DOI]

Wouter Gelade

Marcel Marquardt

ACM Trans. Comput. Log., 2012

Developing and Analyzing XSDs through BonXai.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2012

Theoretical Aspects of Computer Science.

[BibT_eX]

[DOI]

Jean-Yves Marion

Theory Comput. Syst., 2012

Two-Variable Logic with Two Order Relations

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2012

Feasible Automata for Two-Variable Logic with Successor on Data Words.

[BibT_eX]

[DOI]

Ahmet Kara

Tony Tan

Proceedings of the Language and Automata Theory and Applications, 2012

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Information and Knowledge Systems, 2012

2011

Two-variable logic on data words.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2011

Conjunctive query containment over trees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Expressiveness of Hybrid Temporal Logic on Data Words.

[BibT_eX]

[DOI]

Ahmet Kara

Proceedings of the 7th Workshop on Methods for Modalities, 2011

Foundations of distributed data management (Dagstuhl Seminar 11421).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

A note on the expressive power of linear orders

[BibT_eX]

[DOI]

Nicole Schweikardt

Log. Methods Comput. Sci., 2011

Frontmatter, Table of Contents, Preface, Conference Organization.

[BibT_eX]

[DOI]

Christoph Dürr

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Two-variable logic and key constraints on data words.

[BibT_eX]

[DOI]

Matthias Niewerth

Proceedings of the Database Theory, 2011

2010

Inference of concise regular expressions and DTDs.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2010

On notions of regularity for data languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Complexity of hybrid logics over transitive frames.

[BibT_eX]

[DOI]

J. Appl. Log., 2010

Logik und Automaten: ein echtes Dreamteam.

[BibT_eX]

[DOI]

Inform. Spektrum, 2010

Table of Contents - 27th International Symposium on Theoretical Aspects of Computer Science.

[BibT_eX]

[DOI]

Jean-Yves Marion

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

Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science.

[BibT_eX]

[DOI]

Jean-Yves Marion

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

Schema design for XML repositories: complexity and tractability.

[BibT_eX]

[DOI]

Matthias Niewerth

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Temporal Logics on Words with Multiple Data Values.

[BibT_eX]

[DOI]

Ahmet Kara

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

10061 Executive Summary - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

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

10061 Abstracts Collection - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

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

Two-Variable Logic with Two Order Relations - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey.

[BibT_eX]

[DOI]

Thomas Eiter

Proceedings of the Fields of Logic and Computation, 2010

2009

Complexity of Decision Problems for XML Schemas and Chain Regular Expressions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Foreword.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

Volker Weber.

[BibT_eX]

[DOI]

J. Log. Lang. Inf., 2009

Generalized hypertree decompositions: NP-hardness and tractable variants.

[BibT_eX]

[DOI]

Zoltán Miklós

J. ACM, 2009

Two-variable logic on data trees and XML reasoning.

[BibT_eX]

[DOI]

J. ACM, 2009

On the Hybrid Extension of CTL and CTL+

[BibT_eX]

[DOI]

CoRR, 2009

On the Hybrid Extension of CTL and CTL<sup>+</sup>.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Tree Projections: Game Characterization and Computational Aspects.

[BibT_eX]

[DOI]

Proceedings of the Graph Theory, 2009

2008

Introduction to ICDT 2007 special section.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2008

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

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

Optimizing Conjunctive Queries over Trees Using Schema Information.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

08171 Summary - Beyond the Finite: New Challenges in Verification and Semistructured Data.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Counting in trees.

[BibT_eX]

Helmut Seidl

Anca Muscholl

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

Deterministic top-down tree automata: past, present, and future.

[BibT_eX]

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

2007

Simple off the shelf abstractions for XML schema.

[BibT_eX]

[DOI]

SIGMOD Rec., 2007

Dynamic Complexity Theory Revisited.

[BibT_eX]

[DOI]

Volker Weber

Theory Comput. Syst., 2007

Automata for XML - A survey.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

Bounded-Variable Fragments of Hybrid Logics.

[BibT_eX]

[DOI]

Volker Weber

Proceedings of the STACS 2007, 2007

The complexity of reasoning about pattern-based XML schemas.

[BibT_eX]

[DOI]

Gjergji Kasneci

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

2006

Expressiveness and complexity of XML Schema.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2006

Active Context-Free Games.

[BibT_eX]

[DOI]

Anca Muscholl

Luc Segoufin

Theory Comput. Syst., 2006

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

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2006

The many faces of a translation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Inference of Concise DTDs from XML Data.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Conference on Very Large Data Bases, 2006

Two-variable logic on data trees and XML reasoning.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Two-Variable Logic on Words with Data.

[BibT_eX]

[DOI]

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Expressive Power of Pebble Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

06451 Abstracts Collection -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Heribert Vollmer

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

06451 Executive Summary -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Heribert Vollmer

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.

[BibT_eX]

[DOI]

Proceedings of the 14th international conference on World Wide Web, 2005

Which XML Schemas Admit 1-Pass Preorder Typing?

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 2005

05061 Summary - Foundations of Semi-structured Data.

[BibT_eX]

[DOI]

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

05061 Abstracts Collection - Foundations of Semistructured Data.

[BibT_eX]

[DOI]

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

On the Complexity of Equational Horn Clauses.

[BibT_eX]

[DOI]

Kumar Neeraj Verma

Helmut Seidl

Proceedings of the Automated Deduction, 2005

2004

Finite state machines for strings over infinite alphabets.

[BibT_eX]

[DOI]

Victor Vianu

ACM Trans. Comput. Log., 2004

XPath query containment.

[BibT_eX]

[DOI]

SIGMOD Rec., 2004

Solving Equations in the Relational Algebra.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Existential second-order logic over graphs: Charting the tractability frontier.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

J. ACM, 2004

Trees, Automata and XML.

[BibT_eX]

[DOI]

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Complexity of Decision Problems for Simple Regular Expressions.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Counting in Trees for Free.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Definable relations and first-order query languages over strings.

[BibT_eX]

[DOI]

J. ACM, 2003

On the power of tree-walking automata.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Numerical document queries.

[BibT_eX]

[DOI]

Helmut Seidl

Anca Muscholl

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.

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 2003

XML: Model, Schemas, Types, Logics, and Queries.

[BibT_eX]

Nils Klarlund

Proceedings of the Logics for Emerging Applications of Databases [outcome of a Dagstuhl seminar], 2003

2002

Query automata over finite trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time.

[BibT_eX]

[DOI]

Etienne Grandjean

SIAM J. Comput., 2002

2001

The Descriptive Complexity Approach to LOGCFL.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

When is the evaluation of conjunctive queries tractable?

[BibT_eX]

[DOI]

Martin Grohe

Luc Segoufin

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Automata-and Logic-Based Pattern Languages for Tree-Structured Data.

[BibT_eX]

[DOI]

Proceedings of the Semantics in Databases, 2001

String Operations in Query Languages.

[BibT_eX]

[DOI]

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Towards Regular Languages over Infinite Alphabets.

[BibT_eX]

[DOI]

Victor Vianu

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

A Model-Theoretic Approach to Regular String Relations.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Partially-Ordered Two-Way Automata: A New Characterization of DA.

[BibT_eX]

[DOI]

Heribert Vollmer

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Second-Order Logic over Strings: Regular and Non-regular Fragments.

[BibT_eX]

[DOI]

Thomas Eiter

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000

Locality of order-invariant first-order formulas.

[BibT_eX]

[DOI]

Martin Grohe

ACM Trans. Comput. Log., 2000

Expressive and Efficient Pattern Languages for Tree-Structured Data.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

On Diving in Trees.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Logically defined queries on trees.

[BibT_eX]

[DOI]

Proceedings of the 12. GI-Workshop Grundlagen von Datenbanken, 2000

1999

Local Normal Forms for First-Order Logic with Applications to Games and Automata.

[BibT_eX]

[DOI]

Klaus Barthelmann

Discret. Math. Theor. Comput. Sci., 1999

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines.

[BibT_eX]

[DOI]

Nicole Schweikardt

Proceedings of the STACS 99, 1999

Query Automata.

[BibT_eX]

[DOI]

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

Automata for Unary Queries on Trees.

[BibT_eX]

Proceedings of the 11. Workshop Grundlagen von Datenbanken, 1999

1998

Subclasses of Binary NP.

[BibT_eX]

[DOI]

Arnaud Durand

J. Log. Comput., 1998

Positive Versions of Polynomial Time.

[BibT_eX]

[DOI]

Iain A. Stewart

Inf. Comput., 1998

Descriptive Complexity, Lower Bounds and Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997

Algebraic and Logical Characterizations of Deterministic Linear Time Classes.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996

On Winning Ehrenfeucht Games and Monadic NP.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 1996

On Bijections vs. Unary Functions.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

On Positive P.

[BibT_eX]

[DOI]

Iain A. Stewart

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

On winning Ehrenfeucht games and monadic NP.

[BibT_eX]

[DOI]

PhD thesis, 1995

The Power of the Middle Bit of a #P Function.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

Graph Connectivity, Monadic NP and Built-in Relations of Moderate Degree.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

Graph Connectivity and Monadic NP

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Logics For Context-Free Languages.

[BibT_eX]

[DOI]