Zobrazeno 1 - 10
of 173
pro vyhledávání: '"Durand, Arnaud"'
Autor:
Bournez, Olivier, Durand, Arnaud
This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs), a.k.a. (Ordinary) Difference Equations. It presents a new framework using these equations as a central tool for computation and algorithm de
Externí odkaz:
http://arxiv.org/abs/2209.12168
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional
Externí odkaz:
http://arxiv.org/abs/2205.00539
We study the complexity of reasoning tasks for logics in team semantics. Our main focus is on the data complexity of model checking but we also derive new results for logically defined counting and enumeration problems. Our approach is based on modul
Externí odkaz:
http://arxiv.org/abs/2204.00576
Publikováno v:
In Journal of Computer and System Sciences December 2024 146
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 2 (May 10, 2022) lmcs:6858
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:
http://arxiv.org/abs/2010.08382
This papers studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and provides several implicit characterizations of comple
Externí odkaz:
http://arxiv.org/abs/1810.02241
Team semantics is a semantical framework for the study of dependence and independence concepts ubiquitous in many areas such as databases and statistics. In recent works team semantics has been generalised to accommodate also multisets and probabilis
Externí odkaz:
http://arxiv.org/abs/1803.02180
In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes $\textrm{NC}^1$, $\textrm{SAC}^1$ and $\textrm{AC}^1$ as well as thei
Externí odkaz:
http://arxiv.org/abs/1710.01934
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the
Externí odkaz:
http://arxiv.org/abs/1604.06617
We define a variant of team semantics called multiteam semantics based on multisets and study the properties of various logics in this framework. In particular, we define natural probabilistic versions of inclusion and independence atoms and certain
Externí odkaz:
http://arxiv.org/abs/1510.09040