3/2005 Logic and Computer Science

Contents:

• S.Leonesi and C.Toffalori, Logic, Primes and Computation: a Tale of Unrest - abstract | full text
• G.Lenzi, The Modal μ-Calculus: a Survey - abstract | full text
• C.Marini and F.Montagna, Probabilistic Variants of Renyi-Ulam Game and Many-Valued Logic - abstract | full text
• A.Andretta and R.Camerlo, The Use of Complexity Hierarchies in Descriptive Set Theory and Automata Theory - abstract | full text
• P.Cintioli, Relativized Helping Operators - abstract | full text

Abstracts:

• S.Leonesi and C.Toffalori, Logic, Primes and Computation: a Tale of Unrest

  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.

• G.Lenzi, The Modal μ-Calculus: a Survey

  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.

• C.Marini and F.Montagna, Probabilistic Variants of Renyi-Ulam Game and Many-Valued Logic

  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.

• A.Andretta and R.Camerlo, The Use of Complexity Hierarchies in Descriptive Set Theory and Automata Theory

  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.

• P.Cintioli, Relativized Helping Operators

  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₂ ∩ coUP^A₂) 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.