3 citations · 4 across the 6 of their papers we have counts for
8 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…
On Higher Order Query Languages which on Relational Databases Collapse to Second Order Logic
Flavio Ferrarotti, Loredana Tec, José María Turull-Torres
In the framework of computable queries in Database Theory, there are many examples of queries to (properties of) relational database instances that can be expressed by simple and e…
Expressing Properties in Second and Third Order Logic: Hypercube Graphs and SATQBF
F. Ferrarotti, W. Ren, J. M. Turull Torres
It follows from the famous Fagin's theorem that all problems in NP are expressible in existential second-order logic (ESO), and vice versa. Indeed, there are well-known ESO charact…