Descriptive complexity of deterministic polylogarithmic time
F Ferrarotti, S González, JM Turull Torres… - … Workshop on Logic …, 2019 - Springer
We propose a logical characterization of problems solvable in deterministic polylogarithmic
time (PolylogTime). We introduce a novel two-sorted logic that separates the elements of the …
time (PolylogTime). We introduce a novel two-sorted logic that separates the elements of the …
Recursion-Theoretic Alternation
E Skapinakis - Conference on Computability in Europe, 2024 - Springer
We introduce four recursion schemes, which, operating on a tree-like data structure, capture
different models of computation based on alternating bounded quantifiers. By encoding …
different models of computation based on alternating bounded quantifiers. By encoding …
A restricted second-order logic for non-deterministic poly-logarithmic time
F Ferrarotti, SÉ GonzÁles, KD Schewe… - Logic Journal of the …, 2020 - academic.oup.com
We introduce a restricted second-order logic for finite structures where second-order
quantification ranges over relations of size at most poly-logarithmic in the size of the …
quantification ranges over relations of size at most poly-logarithmic in the size of the …
Descriptive complexity of deterministic polylogarithmic time and space
F Ferrarotti, S González, JMT Torres… - Journal of Computer and …, 2021 - Elsevier
We propose logical characterizations of problems solvable in deterministic polylogarithmic
time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two …
time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two …
Proper hierarchies in polylogarithmic time and absence of complete problems
F Ferrarotti, S González, KD Schewe… - … on Foundations of …, 2020 - Springer
The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it
was shown that all classes ̃\varSigma _ m^ plog or ̃\varPi _ m^ plog (m ∈ N) in this hierarchy …
was shown that all classes ̃\varSigma _ m^ plog or ̃\varPi _ m^ plog (m ∈ N) in this hierarchy …
Completeness in Polylogarithmic Time and Space
F Ferrarotti, S Gonzalez, KD Schewe… - arXiv preprint arXiv …, 2020 - arxiv.org
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 …
applications, understood the former as complexity classes and the latter as problems …
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems
JM Turull-Torres - … of Information and Knowledge Systems: 11th …, 2020 - books.google.com
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems Page 108
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems Flavio …
Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems Flavio …
Descriptive Complexity of Polylogarithmic Time/submitted by Senen Gonzalez, MSc.
SA Gonzalez Cornejo - 2019 - epub.jku.at
During the last forty years logics over nite structures have become a central pillar for
studying the denability and complexity of computational problems. The focus is on …
studying the denability and complexity of computational problems. The focus is on …