6 results
Mikolaj Bojanczyk ; Luc Segoufin.
We study tree languages that can be defined in \Delta_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the […]
Published on October 20, 2010
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 descendant relation and the following sibling relation. In terms of expressive power it corresponds to a fragment of […]
Published on September 1, 2015
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 (RPQ). These are queries selecting pairs of nodes in a graph database that are connected via a path whose sequence of […]
Published on December 22, 2015
Florent Jacquemard ; Luc Segoufin ; Jerémie Dimino.
A data tree is an unranked ordered tree where each node carries a label from a finite alphabet and a datum from some infinite domain. We consider the two variable first order logic FO2(<,+1,~) over data trees. Here +1 refers to the child and the next sibling relations while < refers to the […]
Published on April 26, 2016
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 $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural […]
Published on August 2, 2022
Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin.
A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree bounded by $\log n$. It is known that over a […]
Published on May 10, 2022