1.  42
    Fifty Years of the Spectrum Problem: Survey and New Results.Arnaud Durand, Neil D. Jones, Johann A. Makowsky & Malika More - 2012 - Bulletin of Symbolic Logic 18 (4):505-553.
    In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to (...)
    Direct download (9 more)  
    Export citation  
    Bookmark   3 citations  
  2.  19
    Rudimentary Languages and Second‐Order Logic.Malika More & Frédéric Olive - 1997 - Mathematical Logic Quarterly 43 (3):419-426.
    The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second-order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions by providing (...)
    Direct download (5 more)  
    Export citation  
    Bookmark   2 citations  
  3.  33
    The Ultra‐Weak Ash Conjecture and Some Particular Cases.Annie Chateau & Malika More - 2006 - Mathematical Logic Quarterly 52 (1):4-13.
    Ash's functions Nσ ,k count the number of k -equivalence classes of σ -structures of size n . Some conditions on their asymptotic behavior imply the long standing spectrum conjecture. We present a new condition which is equivalent to this conjecture and we discriminate some easy and difficult particular cases.
    Direct download (4 more)  
    Export citation  
    Bookmark   1 citation