8 results
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
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 problem belongs to Constant-Delaylin if for an input of size n it can be solved by: - an O(n) precomputation phase building […]
Published on June 29, 2011
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 show that it is decidable whether a regular tree language is locally testable. The decidability is shown for ranked trees […]
Published on November 22, 2011
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
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
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
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