Contents:

  • Carlo Toffalori From the Editor   abstract | full text
  • Stefano Leonesi and Carlo Toffalori Logic, Primes and Computation: a Tale of Unrest   abstract | full text
  • Giacomo Lenzi The Modal \mu -Calculus: a Survey   abstract | full text
  • Claudio Marini and Franco Montagna Probabilistic Variants of R\ényi-Ulam Game and Many-Valued Logic   abstract | full text
  • Alessandro Andretta and Riccardo Camerlo The Use of Complexity Hierarchies in Descriptive Set Theory and Automata Theory   abstract | full text
  • Patrizio Cintioli Relativized Helping Operators   abstract | full text

Abstracts:

hCarlo Toffalori From the Editor

 

hStefano Leonesi and Carlo 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.

 

hGiacomo Lenzi The Modal \mu -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.

 

hClaudio Marini and Franco Montagna Probabilistic Variants of R\ényi-Ulam Game and Many-Valued Logic

In this paper we discuss some generalizations of Rényi-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.

 

hAlessandro Andretta and Riccardo 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.

 

hPatrizio 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 NP ∩ coNP, 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 B B B for every oracle B PB help (C ) ⊆ P1−help (D ). In [1] it has been observed that Phelp (UP ∩ coUP) = P1−help (UP ∩ coUP), and this is true in any relativized world. In this paper we consider the case A A of D = UP ∩ coUP and demonstrate the existence of an oracle A for which PA help (UP2 ∩ coUP2 ) is A A A not contained in P1−help (UP ∩ coUP ). We also prove that for every integer k ≥ 2 there exists an A A A oracle A such that PA help (UPk ∩ coUPk ) 6⊆ UPk .

 

The Current Issue


VIEW VOLUME
VIEW ALL VOLUMES