Zobrazeno 1 - 10
of 121
pro vyhledávání: '"Ferrarotti, Flavio"'
Autor:
Ferrarotti, Flavio, Rivière, Peter, Schewe, Klaus-Dieter, Singh, Neeraj Kumar, Ameur, Yamine Aït
The verification of liveness conditions is an important aspect of state-based rigorous methods. This article investigates this problem in a fragment $\square$LTL of the logic LTL(EB), the integration of the UNTIL-fragment of Pnueli's linear time temp
Externí odkaz:
http://arxiv.org/abs/2401.16838
Abstract State Machines (ASMs) provide a model of computations on structures rather than strings. Blass, Gurevich and Shelah showed that deterministic PTIME-bounded ASMs define the choiceless fragment of PTIME, but cannot capture PTIME. In this artic
Externí odkaz:
http://arxiv.org/abs/2401.16366
Publikováno v:
In Journal of Computer Languages March 2024 78
Complexity theory can be viewed as the study of the relationship between computation and applications, understood the former as complexity classes and the latter as problems. Completeness results are clearly central to that view. Many natural algorit
Externí odkaz:
http://arxiv.org/abs/2009.04259
Publikováno v:
Science of Computer Programming, 223:102864, 2022
We develop a behavioural theory of reflective sequential algorithms (RSAs), i.e. sequential algorithms that can modify their own behaviour. The theory comprises a set of language-independent postulates defining the class of RSAs, an abstract machine
Externí odkaz:
http://arxiv.org/abs/2001.01873
We introduce a restricted second-order logic $\mathrm{SO}^{\mathit{plog}}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of th
Externí odkaz:
http://arxiv.org/abs/1912.00010
The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes $\tilde{\Sigma}_{m}^{\mathit{plog}}$ or $\tilde{\Pi}_{m}^{\mathit{plog}}$ ($m \in \mathbb{N}$) in this hierarchy can be captured by
Externí odkaz:
http://arxiv.org/abs/1911.13104
Autor:
Ferrarotti, Flavio, González, Senén, Torres, José María Turull, Bussche, Jan Van den, Virtema, Jonni
We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit
Externí odkaz:
http://arxiv.org/abs/1903.03413
Let $\mathrm{SO}^{\mathit{plog}}$ denote the restriction of second-order logic, where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. In this article we investigate the problem, which T
Externí odkaz:
http://arxiv.org/abs/1806.07127