Luc Segoufin

Cristina Sirangelo

Proc. ACM Manag. Data, 2024

2023

Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis.

[BibT_eX]

[DOI]

Nofar Carmeli

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

A Simple Algorithm for Consistent Query Answering Under Primary Keys.

[BibT_eX]

[DOI]

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

2022

Tameness and the power of programs over monoids in DA.

[BibT_eX]

[DOI]

Nathan Grosshans

Pierre McKenzie

Log. Methods Comput. Sci., 2022

Enumerating Answers to First-Order Queries over Databases of Low Degree.

[BibT_eX]

[DOI]

Arnaud Durand

Nicole Schweikardt

Log. Methods Comput. Sci., 2022

Enumeration for FO Queries over Nowhere Dense Graphs.

[BibT_eX]

[DOI]

Nicole Schweikardt

Alexandre Vigny

J. ACM, 2022

Conjunctive queries with self-joins, towards a fine-grained complexity analysis.

[BibT_eX]

[DOI]

Nofar Carmeli

CoRR, 2022

2020

First-order queries on classes of structures with bounded expansion.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2020

Projection Views of Register Automata.

[BibT_eX]

[DOI]

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Order-Invariant First-Order Logic over Hollow Trees.

[BibT_eX]

[DOI]

Julien Grange

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

2018

Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates.

[BibT_eX]

[DOI]

Matthias Niewerth

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

2017

A survey on guarded negation.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2017

Bottom-up automata on data trees and vertical XPath.

[BibT_eX]

[DOI]

Diego Figueira

Log. Methods Comput. Sci., 2017

M. Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Cambridge University Press, Cambridge, 2017, x + 544 pp.

[BibT_eX]

[DOI]

Bull. Symb. Log., 2017

The Power of Programs over Monoids in DA.

[BibT_eX]

[DOI]

Nathan Grosshans

Pierre McKenzie

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion.

[BibT_eX]

[DOI]

Alexandre Vigny

Proceedings of the 20th International Conference on Database Theory, 2017

2016

Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2016

Decidable Characterization of FO2(<, +1) and locality of DA.

[BibT_eX]

[DOI]

CoRR, 2016

FO2(<, +1, ~) on data trees, data tree automata and branching vector addition systems.

[BibT_eX]

[DOI]

Florent Jacquemard

Jerémie Dimino

Log. Methods Comput. Sci., 2016

2015

Constant Delay Enumeration for Conjunctive Queries.

[BibT_eX]

[DOI]

SIGMOD Rec., 2015

Guarded Negation.

[BibT_eX]

[DOI]

Vince Bárány

J. ACM, 2015

Deciding definability in FO2(<h, <v) on trees.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2015

Datalog Rewritings of Regular Path Queries using Views.

[BibT_eX]

[DOI]

Nadime Francis

Cristina Sirangelo

Log. Methods Comput. Sci., 2015

Capturing MSO with One Quantifier.

[BibT_eX]

[DOI]

Anuj Dawar

Proceedings of the Fields of Logic and Computation II, 2015

2014

A glimpse on constant delay enumeration (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013

Enumeration of monadic second-order queries on trees.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2013

Unary negation.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2013

Enumeration of first-order queries on classes of structures with bounded expansion.

[BibT_eX]

[DOI]

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Verification of database-driven systems via amalgamation.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Szymon Torunczyk

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Enumerating with constant delay the answers to a query.

[BibT_eX]

[DOI]

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012

Locality from Circuit Lower Bounds.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Piecewise testable tree languages

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Howard Straubing

Log. Methods Comput. Sci., 2012

2011

Two-variable logic on data words.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2011

Foundations of distributed data management (Dagstuhl Seminar 11421).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

A decidable characterization of locally testable tree languages

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2011

First-order query evaluation on structures of bounded degree

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2011

Automata based verification over linearly ordered data domains.

[BibT_eX]

[DOI]

Szymon Torunczyk

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

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Views and queries: Determinacy and rewriting.

[BibT_eX]

[DOI]

Alan Nash

ACM Trans. Database Syst., 2010

Transitive closure logic, nested tree walking automata, and XPath.

[BibT_eX]

[DOI]

J. ACM, 2010

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Log. Methods Comput. Sci., 2010

Addition-Invariant FO and Regularity.

[BibT_eX]

[DOI]

Nicole Schweikardt

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Deciding Definability in FO2(<) (or XPath) on Trees.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

2009

Static analysis of active XML systems.

[BibT_eX]

[DOI]

Serge Abiteboul

ACM Trans. Database Syst., 2009

Regular tree languages definable in FO and in FOmod.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2009

Towards a characterization of order-invariant queries over tame graphs.

[BibT_eX]

[DOI]

J. Symb. Log., 2009

Two-variable logic on data trees and XML reasoning.

[BibT_eX]

[DOI]

J. ACM, 2009

Modeling and Verifying Active XML Artifacts.

[BibT_eX]

[DOI]

Serge Abiteboul

IEEE Data Eng. Bull., 2009

Future-Looking Logics on Data Words and Trees.

[BibT_eX]

[DOI]

Diego Figueira

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

2008

XPath, transitive closure logic, and nested tree walking automata.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

2007

Static analysis of XML processing with data values.

[BibT_eX]

[DOI]

SIGMOD Rec., 2007

Constant-Memory Validation of Streaming XML Documents Against DTDs.

[BibT_eX]

[DOI]

Cristina Sirangelo

Proceedings of the Database Theory, 2007

Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report.

[BibT_eX]

[DOI]

Alan Nash

Proceedings of the Database Theory, 2007

Complexity of Pebble Tree-Walking Automata.

[BibT_eX]

[DOI]

Mathias Samuelides

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006

Representing and querying XML with incomplete information.

[BibT_eX]

[DOI]

Serge Abiteboul

ACM Trans. Database Syst., 2006

Active Context-Free Games.

[BibT_eX]

[DOI]

Anca Muscholl

Thomas Schwentick

Theory Comput. Syst., 2006

Complementing deterministic tree-walking automata.

[BibT_eX]

[DOI]

Anca Muscholl

Mathias Samuelides

Inf. Process. Lett., 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

Automata and Logics for Words and Trees over an Infinite Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005

The complexity of XPath query evaluation and XML typing.

[BibT_eX]

[DOI]

J. ACM, 2005

Regular Tree Languages Definable in FO.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Views and queries: determinacy and rewriting.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Towards a Characterization of Order-Invariant Queries over Tame Structures.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004

Order Independent Temporal Properties.

[BibT_eX]

[DOI]

Nicole Bidoit

Sandra de Amo

J. Log. Comput., 2004

2003

Reachability and connectivity queries in constraint databases.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Definable relations and first-order query languages over strings.

[BibT_eX]

[DOI]

J. ACM, 2003

Building a constraint-based spatial database system: model, languages, and implementation.

[BibT_eX]

[DOI]

Inf. Syst., 2003

Handling Interpolated Data.

[BibT_eX]

[DOI]

Comput. J., 2003

Typing and querying XML documents: some complexity bounds.

[BibT_eX]

[DOI]

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

2002

On first-order topological queries.

[BibT_eX]

[DOI]

Martin Grohe

ACM Trans. Comput. Log., 2002

Validating Streaming XML Documents.

[BibT_eX]

[DOI]

Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

2001

Spatio-Temporal Data Handling with Constraints.

[BibT_eX]

[DOI]

GeoInformatica, 2001

When is the evaluation of conjunctive queries tractable?

[BibT_eX]

[DOI]

Martin Grohe

Thomas Schwentick

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

String Operations in Query Languages.

[BibT_eX]

[DOI]

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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

Propriétés temporelles indépendantes de l'ordre.

[BibT_eX]

Nicole Bidoit

Sandra de Amo

Proceedings of the 17èmes Journées Bases de Données Avancées, 2001

2000

Querying Spatial Databases via Topological Invariants.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

Manipulating Interpolated Data is Easier than You Thought.

[BibT_eX]

[DOI]

Proceedings of the VLDB 2000, 2000

The DEDALE Prototype.

[BibT_eX]

Proceedings of the Constraint Databases, 2000

Optimization Techniques.

[BibT_eX]

Proceedings of the Constraint Databases, 2000

1999

On the Orthographic Dimension of Constraint Databases.

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 1999

Modeling and Querying Interpolated Spatial Data.

[BibT_eX]

Proceedings of the 15èmes Journées Bases de Données Avancées, 1999

1998

The DEDALE System for Complex Spatial Queries.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD 1998, 1998

Efficient multi-dimensional data handling in constraint databases.

[BibT_eX]