36 citations · 146 across the 15 of their papers we have counts for
15 papers
A Simple Algorithm for Consistent Query Answering under Primary Keys
Diego Figueira, Anantha Padmanabha, Luc Segoufin +1
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is…
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis
Nofar Carmeli, Luc Segoufin
Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-jo…
Tameness and the power of programs over monoids in DA
Nathan Grosshans, Pierre Mckenzie, Luc Segoufin
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class . Here we make progress in understanding…
Enumerating Answers to First-Order Queries over Databases of Low Degree
Arnaud Durand, Nicole Schweikardt, Luc Segoufin
A class of relational databases has low degree if for all , all but finitely many databases in the class have degree at most , where is the size of the database. Typi…
First-order queries on classes of structures with bounded expansion
Wojtek Kazana, Luc Segoufin
We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree,…
Bottom-up automata on data trees and vertical XPath
Diego Figueira, Luc Segoufin
A data tree is a finite tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data…
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
Paul Beame, Nathan Grosshans, Pierre McKenzie +1
A formulation of "Nečiporuk's lower bound method" slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limit…
Decidable Characterization of FO2(<,+1) and locality of DA
Thomas Place, Luc Segoufin
Several years ago Thérien and Wilke exhibited a decidable characterization of the languages of words that are definable in FO2(<,+1). Their proof relies on three separate ingredien…
Datalog Rewritings of Regular Path Queries using Views
Nadime Francis, Luc Segoufin, Cristina Sirangelo
We consider query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We mainly consider views and queries specified by Regular Path Queries…
Deciding definability in FO2(<h,<v) on trees
Thomas Place, Luc Segoufin
We provide a decidable characterization of regular forest languages definable in FO2(<h,<v). By FO2(<h,<v) we refer to the two variable fragment of first order logic built from the…
Unary negation
Luc Segoufin, Balder ten Cate
We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize…
Piecewise testable tree languages
Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing
This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem,…
A decidable characterization of locally testable tree languages
Thomas Place, Luc Segoufin
A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree. In this paper we sh…
First-order query evaluation on structures of bounded degree
Wojciech Kazana, Luc Segoufin
We consider the enumeration problem of first-order queries over structures of bounded degree. It was shown that this problem is in the Constant-Delaylin class. An enumeration probl…
Tree Languages Defined in First-Order Logic with One Quantifier Alternation
Mikolaj Bojanczyk, Luc Segoufin
We study tree languages that can be defined in Δ_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a f…