Zobrazeno 1 - 10
of 96
pro vyhledávání: '"Luc Segoufin"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 18, Issue 3 (2022)
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 condit
Externí odkaz:
https://doaj.org/article/56a8fd27c6c147998442e9087256d71d
Publikováno v:
Logical Methods in Computer Science, Vol Volume 18, Issue 2 (2022)
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
Externí odkaz:
https://doaj.org/article/e5abcd286a53411388c7a2d49850123a
Autor:
Wojtek Kazana, Luc Segoufin
Publikováno v:
Logical Methods in Computer Science, Vol Volume 16, Issue 1 (2020)
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 th
Externí odkaz:
https://doaj.org/article/25f0ac0e7e3d461a848944fa10728b7a
Autor:
Diego Figueira, Luc Segoufin
Publikováno v:
Logical Methods in Computer Science, Vol Volume 13, Issue 4 (2017)
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-u
Externí odkaz:
https://doaj.org/article/779cac6db40447508327fe9e90d8cf10
Publikováno v:
Logical Methods in Computer Science, Vol Volume 12, Issue 2 (2016)
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(
Externí odkaz:
https://doaj.org/article/59c5c32ad73e47e88250988adc5d5331
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 4 (2015)
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
Externí odkaz:
https://doaj.org/article/c2252384dbf74ee6afbf88af8dadaadb
Autor:
Thomas Place, Luc Segoufin
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 3 (2015)
We provide a decidable characterization of regular forest languages definable in FO2(
Externí odkaz:
https://doaj.org/article/f62ca2677d1442de9f83df6aede7fd47
Autor:
Luc Segoufin, Balder ten Cate
Publikováno v:
Logical Methods in Computer Science, Vol Volume 9, Issue 3 (2013)
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$
Externí odkaz:
https://doaj.org/article/006e45219f3c4d108d29264b660d94cb
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 3 (2012)
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 combina
Externí odkaz:
https://doaj.org/article/ae4895d2a3dc472ab3b07208f4d002a9
Autor:
Thomas Place, Luc Segoufin
Publikováno v:
Logical Methods in Computer Science, Vol Volume 7, Issue 4 (2011)
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 tes
Externí odkaz:
https://doaj.org/article/7155c7e12dd04516a39caf9f4166dd63