TASK Quarterly   Scientific Bulletin of the Centre of Informatics - Tricity Academic Supercomputer & networK   ISSN 1428-6394

3/2005 Logic and Computer Science

Issue editor:
Prof. Carlo Toffalori,
Dipartimento di Matematica e Informatica,
Universita di Camerino, Italy



  • 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, Phelp(•) and P1-help(•), acting on classes of sets C and returning classes of sets Phelp(C) and P1-help(C). A number of results have been obtained on this subject, principally devoted to understanding how wide the Phelp(C) and P1-help(C) classes are. For example, it seems that the Phelp(•) operator contracts NPcoNP}, while the P1-help(•) operator enlarges UP. To better understand the relative power of P1-help(•) versus Phelp(•) we propose to search, for every relativizable class D containing P, the largest relativizable class C containing P such that for every oracle B PBhelp(CB)⊆ PB1-help(DB). In the following paper: Cintioli P. and Silvestri R. 1997 Inf. Proc. Let. 61 189, it has been observed that Phelp(UPcoUP)= P1-help(UPcoUP), and this is true in any relativized world. In this paper we consider the case of D=UPcoUP and demonstrate the existence of an oracle A for which PAhelp(UPA2coUPA2) is not contained in PA1-help(UPAcoUPA). We also prove that for every integer k ≥ 2 there exists an oracle A such that PAhelp(UPAkcoUPAk) ⊄ UPAk.