Switch to: References

Add citations

You must login to add citations.
  1. The structure of the models of decidable monadic theories of graphs.D. Seese - 1991 - Annals of Pure and Applied Logic 53 (2):169-195.
    In this article the structure of the models of decidable monadic theories of planar graphs is investigated. It is shown that if the monadic theory of a class K of planar graphs is decidable, then the tree-width in the sense of Robertson and Seymour of the elements of K is universally bounded and there is a class T of trees such that the monadic theory of K is interpretable in the monadic theory of T.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
    The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...)
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
    We study tree-like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
    Download  
     
    Export citation  
     
    Bookmark