7 found
Sort by:
  1. Luke Ong, Carlos Areces, Santiago Figueira & Ruy de Queiroz (forthcoming). 19th Workshop on Logic, Language, Information and Computation (Wollic 2012). Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Luke Ong, Carlos Areces, Santiago Figueira and Ruy de Queiroz The Bulletin of Symbolic Logic, Volume 19, Issue 3, Page 425-426, September 2013.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Carlos Areces, Santiago Figueira & Sergio Mera (2012). Completeness Results for Memory Logics. Annals of Pure and Applied Logic 163 (7):961-972.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Carlos Areces, Diego Figueira, Santiago Figueira & Sergio Mera (2011). The Expressive Power of Memory Logics. Review of Symbolic Logic 4 (2):290-318.
    We investigate the expressive power of memory logics. These are modal logics extended with the possibility to store (or remove) the current node of evaluation in (or from) a memory, and to perform membership tests on the current memory. From this perspective, the hybrid logic (↓), for example, can be thought of as a particular case of a memory logic where the memory is an indexed list of elements of the domain.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  4. Santiago Figueira, André Nies & Frank Stephan (2008). Lowness Properties and Approximations of the Jump. Annals of Pure and Applied Logic 152 (1):51-66.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller (2006). Randomness and Halting Probabilities. Journal of Symbolic Logic 71 (4):1411 - 1430.
    We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is $\Sigma _{n}^{0}$-complete or $\Pi _{n}^{0}$-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is $\Sigma _{n}^{0}$ or $\Pi _{n}^{0}$ Nevertheless, there exists $\Delta _{n+1}^{0}$ sets such that ΩU[X] is n-random. There are $\Delta _{2}^{0}$ sets (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. Journal of Logic, Language and Information 14 (2):133-148.
    In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  7. Ver�Nica Becher, Santiago Figueira, Andr� Nies & Silvana Picchi (2005). Program Size Complexity for Possibly Infinite Computations. Notre Dame Journal of Formal Logic 46 (1):51-64.
    We define a program size complexity function as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in relative to the complexity. We prove that the classes of Martin-Löf random sequences and -random sequences coincide and that the -trivial sequences are exactly the recursive ones. We also study some properties of and compare it with other complexity functions. In particular, is different from , the (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation