9 citations · 16 across the 11 of their papers we have counts for
11 papers
Infinitary provability logic
Mojtaba Mojtahedi, Fedor Pakhomov, Giovanni Soldà
Gödel-Löb provability logic $\GL$ is a propositional modal system that on one hand enjoys completeness with respect to conversely well-founded Kripke frames and on the other hand c…
Generalized Higman's Theorem and iterated ideals
Fedor Pakhomov, Giovanni Soldà
Generalized Higman's Theorem is the direct counterpart of Higman's Theorem that asserts the closure of the class of \emph{better} quasi-orders, instead of the class of \emph{well}…
On statistical learning of graphs
Vittorio Cipriani, Valentino Delle Rose, Luca San Mauro +1
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds…
On Nash-Williams' Theorem regarding sequences with finite range
Fedor Pakhomov, Giovanni Soldà
The famous theorem of Higman states that for any well-quasi-order (wqo) the embeddability order on finite sequences over is also wqo. In his celebrated 1965 paper, Nash-Wil…
Sequential discontinuity and first-order problems
Arno Pauly, Giovanni Soldà
We explore the low levels of the structure of the continuous Weihrauch degrees of first-order problems. In particular, we show that there exists a minimal discontinuous first-order…
Provable better quasi orders
Anton Freund, Alberto Marcone, Fedor Pakhomov +1
It has recently been shown that fairly strong axiom systems such as cannot prove that the antichain with three elements is a better quasi order (). I…
The logical strength of minimal bad arrays
Anton Freund, Fedor Pakhomov, Giovanni Soldà
This paper studies logical aspects of the notion of better quasi order, which has been introduced by C. Nash-Williams (Mathematical Proceedings of the Cambridge Philosophical Socie…
On the Weihrauch degree of the additive Ramsey theorem
Arno Pauly, Cécilia Pradic, Giovanni Solda
We characterize the strength, in terms of Weihrauch degrees, of certain problems related to Ramsey-like theorems concerning colourings of the rationals and of the natural numbers.…
Algebraic properties of the first-order part of a problem
Giovanni Solda, Manlio Valenti
In this paper we study the notion of first-order part of a computational problem, first introduced by Dzhafarov, Solomon, and Yokoyama, which captures the "strongest computational…
(Extra)ordinary equivalences with the ascending/descending sequence principle
Marta Fiori-Carones, Alberto Marcone, Paul Shafer +1
We analyze the axiomatic strength of the following theorem due to Rival and Sands in the style of reverse mathematics. "Every infinite partial order of finite width contains an…
An inside/outside Ramsey theorem and recursion theory
Marta Fiori-Carones, Paul Shafer, Giovanni Soldà
Inspired by Ramsey's theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph contains an infinite subset such t…