3 citations · 3 across the 5 of their papers we have counts for
7 papers
Completeness in Polylogarithmic Time and Space
Flavio Ferrarotti, Senen Gonzalez, Klaus-Dieter Schewe +1
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. Compl…
A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time
Flavio Ferrarotti, Senen Gonzáles, Klaus-Dieter Schewe +1
We introduce a restricted second-order logic for finite structures where second-order quantification ranges over relations of size at most poly-logari…
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems
Flavio Ferrarotti, Senén González, Klaus-Dieter Schewe +1
The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes or $\tildeΠ_{m}^{\mathit{plog}}…
Descriptive Complexity of Deterministic Polylogarithmic Time and Space
Flavio Ferrarotti, Senén González, José María Turull Torres +2
We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sor…
The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic
Flavio Ferrarotti, Senén González, Klaus-Dieter Schewe +1
Let denote the restriction of second-order logic, where second-order quantification ranges over relations of size at most poly-logarithmic in the size…
Towards an ASM thesis for reflective sequential algorithms
Flavio Ferrarotti, Loredana Tec, Jose Maria Turull Torres
Starting from Gurevich's thesis for sequential algorithms (the so-called "sequential ASM thesis"), we propose a characterization of the behaviour of sequential algorithms enriched…