Switch to: References

Add citations

You must login to add citations.
  1. Cardinal Arithmetic in the Style of Baron Von Münchhausen.Albert Visser - 2009 - Review of Symbolic Logic 2 (3):570-589.
    In this paper we show how to interpret Robinson’s arithmetic Q and the theory R of Tarski, Mostowski, and Robinson as theories of cardinals in very weak theories of relations over a domain.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05.Stan S. Wainer - 2006 - Bulletin of Symbolic Logic 12 (2):310-361.
  • On Countable Chains Having Decidable Monadic Theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
    Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theory.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  • Computational Complexity of Logical Theories of One Successor and Another Unary Function.Pascal Michel - 2007 - Archive for Mathematical Logic 46 (2):123-148.
    The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Automata Techniques for Query Inference Machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.
    In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework for studying this question. Essentially, once we have a result for queries to [S,<]2, we can obtain the same result for many different languages. We obtain easier proofs of old results and several new results. An earlier result we (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Logical Aspects of Cayley-Graphs: The Group Case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1):263-286.
    We prove that a finitely generated group is context-free whenever its Cayley-graph has a decidable monadic second-order theory. Hence, by the seminal work of Muller and Schupp, our result gives a logical characterization of context-free groups and also proves a conjecture of Schupp. To derive this result, we investigate general graphs and show that a graph of bounded degree with a high degree of symmetry is context-free whenever its monadic second-order theory is decidable. Further, it is shown that the word (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Iterated Pushdown Automata and Sequences of Rational Numbers.Séverine Fratani & Géraud Sénizergues - 2006 - Annals of Pure and Applied Logic 141 (3):363-411.