3 citations · 8 across the 6 of their papers we have counts for
4 papers · 1 filter
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…
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…
A Logic for Non-Deterministic Parallel Abstract State Machines
Flavio Ferrarotti, Klaus-Dieter Schewe, Loredana Tec +1
We develop a logic which enables reasoning about single steps of non-deterministic parallel Abstract State Machines (ASMs). Our logic builds upon the unifying logic introduced by N…