The early connections between Mathematical Logic and Computer Science date back to the thirties and to the birth itself of modern Theoretical Computer Science, and concern computability. This survey wishes to emphasize how alive and fruitful this relationship has been since then, and still is.
The modal μ-calculus is an extension of modal logic with two operators μ and ν, which give the least and greatest fixpoints of monotone operators on powersets. This powerful logic is widely used in computer science, in the area of verification of correctness of concurrent systems. In this survey we review both the theoretical aspects of the modal μ-calculus and its applications to computer science.
In this paper we discuss some generalizations of Renyi-Ulam game with lies: some of them are simply probabilistic variants of it, some others differ from it by the presence of more than one number to guess. In the last part of the paper, we also discuss the relationship between such variants and many-valued logic. This paper is just a survey of known results, but in its last part it also contains some plans for future research.
The concept of a reduction between subsets of a given space is described, giving rise to various complexity hierarchies, studied both in descriptive set theory and in automata theory. We discuss in particular the Wadge and Lipschitz hierarchies for subsets of the Baire and Cantor spaces and the hierarchy of Borel reducibility for finitary relations on standard Borel spaces. The notions of Wadge and Lipschitz reductions are related to corresponding perfect information games.
Schöning and Ko respectively introduced the concepts of helping and one-side-helping, and then defined new operators, P_{help}(•) and P_{1-help}(•), acting on classes of sets C and returning classes of sets P_{help}(C) and P_{1-help}(C). A number of results have been obtained on this subject, principally devoted to understanding how wide the P_{help}(C) and P_{1-help}(C) classes are. For example, it seems that the P_{help}(•) operator contracts NP ∩ coNP}, while the P_{1-help}(•) operator enlarges UP. To better understand the relative power of P_{1-help}(•) versus P_{help}(•) we propose to search, for every relativizable class D containing P, the largest relativizable class C containing P such that for every oracle B P^{B}_{help}(C^{B})⊆ P^{B}_{1-help}(D^{B}). In the following paper: Cintioli P. and Silvestri R. 1997 Inf. Proc. Let. 61 189, it has been observed that P_{help}(UP ∩ coUP)= P_{1-help}(UP ∩ coUP), and this is true in any relativized world. In this paper we consider the case of D=UP ∩ coUP and demonstrate the existence of an oracle A for which P^{A}_{help}(UP^{A}_{2} ∩ coUP^{A}_{2}) is not contained in P^{A}_{1-help}(UP^{A} ∩ coUP^{A}). We also prove that for every integer k ≥ 2 there exists an oracle A such that P^{A}_{help}(UP^{A}_{k} ∩ coUP^{A}_{k}) ⊄ UP^{A}_{k}.
1997-2020 (C) CI TASK quarterly@task.gda.pl