3 papers
math.LO2025
Strong Kurtz Randomness and Binary Expansions of Reordered Computable Numbers
Peter Hertling, Philip Janicki
A real number is called left-computable if there exists a computable increasing sequence of rational numbers converging to it. In this article we investigate the Kolmogorov complex…
cs.LO2019
EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 2: EXPSPACE-Hardness
Peter Hertling, Gisela Krommes
It is known that the satisfiability problems of the product logics K4xS5 and S4xS5 are NEXPTIME-hard and that the satisfiability problem of the logic SSL of subset spaces is PSPACE…
cs.LO2019
EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 1: ESPACE-Algorithms
Peter Hertling, Gisela Krommes
It is known that the satisfiability problems of the product logics K4xS5 and S4xS5 and of the logic SSL of subset spaces are in N2EXPTIME. We improve this upper bound for the compl…