10 results
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, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its […]
Published on September 29, 2012
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
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
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 many interesting known formalisms, including modal logic and the $\mu$-calculus, as well as conjunctive queries and […]
Published on September 24, 2013
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 trees with a decidable emptiness problem. It is essentially a bottom-up alternating automaton with one register that can […]
Published on November 6, 2017
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, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded […]
Published on February 25, 2020
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
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