Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
5 results

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 many interesting known formalisms, including modal logic and the $\mu$-calculus, as well as conjunctive queries and&nbsp;[&hellip;]
Published on September 24, 2013
Volume 9, Issue 3

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, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its&nbsp;[&hellip;]
Published on September 29, 2012
Volume 8, Issue 3

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

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&nbsp;[&hellip;]
Published on October 20, 2010
Volume 6, Issue 4

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 trees with a decidable emptiness problem. It is essentially a bottom-up alternating automaton with one register that can&nbsp;[&hellip;]
Published on November 6, 2017
Volume 13, Issue 4

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, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded&nbsp;[&hellip;]
Published on February 25, 2020
Volume 16, Issue 1
  • < Previous
  • 1
  • Next >