Switch to: References

Citations of:

Book Reviews [Book Review]

Studia Logica 71 (1):133-148 (2002)

Add citations

You must login to add citations.
  1. An incomplete set of shortest descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
    The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Reduction Techniques for Proving Decidability in Logics and Their Meet–Combination.João Rasga, Cristina Sernadas & Walter Carnielli - 2021 - Bulletin of Symbolic Logic 27 (1):39-66.
    Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation