Luc Segoufin

Orcid: 0000-0002-9564-7581

Affiliations:
  • INRIA, France


According to our database1, Luc Segoufin authored at least 87 papers between 1997 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join.
Proc. ACM Manag. Data, 2024

2023
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis.
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.
Proceedings of the 26th International Conference on Database Theory, 2023

2022
Tameness and the power of programs over monoids in DA.
Log. Methods Comput. Sci., 2022

Enumerating Answers to First-Order Queries over Databases of Low Degree.
Log. Methods Comput. Sci., 2022

Enumeration for FO Queries over Nowhere Dense Graphs.
J. ACM, 2022

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

2020
First-order queries on classes of structures with bounded expansion.
Log. Methods Comput. Sci., 2020

Projection Views of Register Automata.
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Order-Invariant First-Order Logic over Hollow Trees.
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.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

2017
A survey on guarded negation.
ACM SIGLOG News, 2017

Bottom-up automata on data trees and vertical XPath.
Log. Methods Comput. Sci., 2017

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

The Power of Programs over Monoids in DA.
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.
Proceedings of the 20th International Conference on Database Theory, 2017

2016
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.
ACM Trans. Comput. Theory, 2016

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

FO2(<, +1, ~) on data trees, data tree automata and branching vector addition systems.
Log. Methods Comput. Sci., 2016

2015
Constant Delay Enumeration for Conjunctive Queries.
SIGMOD Rec., 2015

Guarded Negation.
J. ACM, 2015

Deciding definability in FO2(<h, <v) on trees.
Log. Methods Comput. Sci., 2015

Datalog Rewritings of Regular Path Queries using Views.
Log. Methods Comput. Sci., 2015

Capturing MSO with One Quantifier.
Proceedings of the Fields of Logic and Computation II, 2015

2014
A glimpse on constant delay enumeration (Invited Talk).
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013
Enumeration of monadic second-order queries on trees.
ACM Trans. Comput. Log., 2013

Unary negation.
Log. Methods Comput. Sci., 2013

Enumeration of first-order queries on classes of structures with bounded expansion.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Verification of database-driven systems via amalgamation.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Enumerating with constant delay the answers to a query.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012
Locality from Circuit Lower Bounds.
SIAM J. Comput., 2012

Piecewise testable tree languages
Log. Methods Comput. Sci., 2012

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

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

A decidable characterization of locally testable tree languages
Log. Methods Comput. Sci., 2011

First-order query evaluation on structures of bounded degree
Log. Methods Comput. Sci., 2011

Automata based verification over linearly ordered data domains.
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.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Views and queries: Determinacy and rewriting.
ACM Trans. Database Syst., 2010

Transitive closure logic, nested tree walking automata, and XPath.
J. ACM, 2010

Tree Languages Defined in First-Order Logic with One Quantifier Alternation
Log. Methods Comput. Sci., 2010

Addition-Invariant FO and Regularity.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Deciding Definability in FO<sub>2</sub>(<) (or XPath) on Trees.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

2009
Static analysis of active XML systems.
ACM Trans. Database Syst., 2009

Regular tree languages definable in FO and in FO<sub><i>mod</i></sub>.
ACM Trans. Comput. Log., 2009

Towards a characterization of order-invariant queries over tame graphs.
J. Symb. Log., 2009

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

Modeling and Verifying Active XML Artifacts.
IEEE Data Eng. Bull., 2009

Future-Looking Logics on Data Words and Trees.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

2008
XPath, transitive closure logic, and nested tree walking automata.
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.
SIGMOD Rec., 2007

Constant-Memory Validation of Streaming XML Documents Against DTDs.
Proceedings of the Database Theory, 2007

Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report.
Proceedings of the Database Theory, 2007

Complexity of Pebble Tree-Walking Automata.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006
Representing and querying XML with incomplete information.
ACM Trans. Database Syst., 2006

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

Complementing deterministic tree-walking automata.
Inf. Process. Lett., 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

Automata and Logics for Words and Trees over an Infinite Alphabet.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005
The complexity of XPath query evaluation and XML typing.
J. ACM, 2005

Regular Tree Languages Definable in FO.
Proceedings of the STACS 2005, 2005

Views and queries: determinacy and rewriting.
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.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004
Order Independent Temporal Properties.
J. Log. Comput., 2004

2003
Reachability and connectivity queries in constraint databases.
J. Comput. Syst. Sci., 2003

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

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

Handling Interpolated Data.
Comput. J., 2003

Typing and querying XML documents: some complexity bounds.
Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

2002
On first-order topological queries.
ACM Trans. Comput. Log., 2002

Validating Streaming XML Documents.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

2001
Spatio-Temporal Data Handling with Constraints.
GeoInformatica, 2001

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

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

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

Propriétés temporelles indépendantes de l'ordre.
Proceedings of the 17èmes Journées Bases de Données Avancées, 2001

2000
Querying Spatial Databases via Topological Invariants.
J. Comput. Syst. Sci., 2000

Manipulating Interpolated Data is Easier than You Thought.
Proceedings of the VLDB 2000, 2000

The DEDALE Prototype.
Proceedings of the Constraint Databases, 2000

Optimization Techniques.
Proceedings of the Constraint Databases, 2000

1999
On the Orthographic Dimension of Constraint Databases.
Proceedings of the Database Theory, 1999

Modeling and Querying Interpolated Spatial Data.
Proceedings of the 15èmes Journées Bases de Données Avancées, 1999

1998
The DEDALE System for Complex Spatial Queries.
Proceedings of the SIGMOD 1998, 1998

Efficient multi-dimensional data handling in constraint databases.
Proceedings of the 14ème Journées Bases de Données Avancées, 1998

1997
DEDALE, A Spatial Constraint Database.
Proceedings of the Database Programming Languages, 6th International Workshop, 1997


  Loading...