4 papers
Bisimulations in second-order arithmetic
Yuto Takeda, Keita Yokoyama
This paper investigates the logical strength of two theorems in modal propositional logic - the Hennessy-Milner theorem and the van Benthem characterization theorem - within the fr…
Quasi-Polish spaces and spaces of filters in second-order arithmetic
Yuzuki Kaneko, Keita Yokoyama
The class of quasi-Polish spaces admits several equivalent representations, including UF spaces, NP spaces, subspaces of , and sober spaces…
Completeness theorems for modal logic in second-order arithmetic
Sho Shimomichi, Yuto Takeda, Keita Yokoyama
This paper investigates the logical strength of completeness theorems for modal propositional logic within second-order arithmetic. We demonstrate that the weak completeness theore…
A parameterized halting problem, truth and the MRDP theorem
Yijia Chen, Moritz Müller, Keita Yokoyama
We study the parameterized complexity of the problem to decide whether a given natural number satisfies a given -formula ; the parameter is the size of . This par…