{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:32:42Z","timestamp":1774593162360,"version":"3.50.1"},"reference-count":112,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"unspecified","delay-in-days":643,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u00fcnter 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 the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached by means of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally by means of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open.<\/jats:p>","DOI":"10.2178\/bsl.1804020","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T14:06:21Z","timestamp":1352815581000},"page":"505-553","source":"Crossref","is-referenced-by-count":13,"title":["Fifty years of the spectrum problem: survey and new results"],"prefix":"10.1017","volume":"18","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil D.","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malika","family":"More","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"S1079898600008957_ref108","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"42","author":"Turing","year":"1936","journal-title":"Proceedings of the London Mathematical Society"},{"key":"S1079898600008957_ref090","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7"},{"key":"S1079898600008957_ref110","volume-title":"Generatingfunctionology","author":"Wilf","year":"1990"},{"key":"S1079898600008957_ref093","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-0507-1"},{"key":"S1079898600008957_ref112","doi-asserted-by":"publisher","DOI":"10.1137\/0207018"},{"key":"S1079898600008957_ref087","first-page":"282","article-title":"Rudimentary predicates and Turing computations","volume":"195","author":"Nepomnja\u0161\u010di\u01d0","year":"1970","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S1079898600008957_ref082","first-page":"89","article-title":"The solution of Scholz problems","volume":"12","author":"Mo","year":"1991","journal-title":"Chinese Annals of Mathematics, Series A"},{"key":"S1079898600008957_ref091","first-page":"395","article-title":"The observational predicate calculus and complexity of computations","volume":"16","author":"Pudl\u00e1k","year":"1975","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"S1079898600008957_ref079","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786976"},{"key":"S1079898600008957_ref081","unstructured":"Miller J. , Statement of result on primitive recursive reals, E-mail communication."},{"key":"S1079898600008957_ref102","first-page":"861","article-title":"On the subrecursive computability of several famous constants","volume":"14","author":"Skordev","year":"2008","journal-title":"Journal of Universal Computer Science"},{"key":"S1079898600008957_ref109","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"S1079898600008957_ref107","first-page":"569","article-title":"Impossibility of an algorithm for the decision problem in finite classes","volume":"70","author":"Trakhtenbrot","year":"1950","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S1079898600008957_ref098","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19720180102"},{"key":"S1079898600008957_ref111","unstructured":"Woods A. R. , Some problems in logic and number theory and their connections, Ph.D. thesis, University of Manchester, 1981."},{"key":"S1079898600008957_ref099","volume-title":"Subrecursion. Functions and hierarchies","volume":"9","author":"Rose","year":"1984"},{"key":"S1079898600008957_ref083","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19970430315"},{"key":"S1079898600008957_ref076","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00198-6"},{"key":"S1079898600008957_ref065","doi-asserted-by":"crossref","first-page":"70","DOI":"10.26686\/ajl.v2i0.1768","article-title":"Limiting cases for spectrum closure results","volume":"2","author":"Hunter","year":"2004","journal-title":"Australasian Journal of Logic"},{"key":"S1079898600008957_ref103","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of formal systems","volume":"47","author":"Smullyan","year":"1961"},{"key":"S1079898600008957_ref077","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19770233608"},{"key":"S1079898600008957_ref105","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(54)50074-0"},{"key":"S1079898600008957_ref092","first-page":"58","volume-title":"Logic, methodology and philosophy of science II","author":"Rabin","year":"1965"},{"key":"S1079898600008957_ref080","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"S1079898600008957_ref101","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200210)48:1+<91::AID-MALQ91>3.0.CO;2-L"},{"key":"S1079898600008957_ref106","volume-title":"Undecidable theories","author":"Tarski","year":"1953"},{"key":"S1079898600008957_ref096","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"S1079898600008957_ref100","first-page":"160","article-title":"Ein ungel\u00f6stes Problem in der symbolischen Logik","volume":"17","author":"Scholz","year":"1952","journal-title":"The Journal of Symbolic Logic"},{"key":"S1079898600008957_ref097","volume-title":"Review of [6]","author":"Robinson"},{"key":"S1079898600008957_ref072","first-page":"1","article-title":"Egyszer\u00fc p\u00e9lda eld\u00f6nthetetlen aritmetikai probl\u00e9m\u00e0ra. (Ein einfaches Beispiel f\u00fcr ein unentscheidbares arithmetisches Problem)","volume":"50","author":"Kalm\u00e1r","year":"1943","journal-title":"Mate \u00e9s Fizikai Lapok"},{"key":"S1079898600008957_ref071","doi-asserted-by":"publisher","DOI":"10.2307\/2272354"},{"key":"S1079898600008957_ref089","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028025"},{"key":"S1079898600008957_ref075","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"S1079898600008957_ref066","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S1079898600008957_ref088","first-page":"44","article-title":"Examples of predicates inexpressible by s-rudimentary formulas","volume":"2","author":"Nepomnja\u0161\u010di\u01d0","year":"1978","journal-title":"Kibernetika (Kiev)"},{"key":"S1079898600008957_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"S1079898600008957_ref045","first-page":"17","article-title":"Volume and fraction of satisfiability of formulas of the lower predicate calculus","volume":"2","author":"Glebski\u01d0","year":"1969","journal-title":"Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainsko\u01d0 SSR. Kibernetika"},{"key":"S1079898600008957_ref044","first-page":"1","volume-title":"Handbook of formal languages, vol. 3: Beyond words","author":"G\u00e9cseg","year":"1997"},{"key":"S1079898600008957_ref028","unstructured":"Durand A. , Hi\u00e9rarchies de d\u00e9finissabilit\u00e9 logique au second ordre, Ph.D. thesis, Universit\u00e9 de Caen, Caen, France, 1996."},{"key":"S1079898600008957_ref008","first-page":"1","article-title":"A tourist guide through tree width","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybernetica"},{"key":"S1079898600008957_ref063","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S1079898600008957_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"S1079898600008957_ref034","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00002-9"},{"key":"S1079898600008957_ref013","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200510010"},{"key":"S1079898600008957_ref036","first-page":"43","volume-title":"Complexity of computation (Proceedings of the SIAM\u2013AMS Symposium on Applied Mathematics, New York, 1973)","volume":"7","author":"Fagin","year":"1974"},{"key":"S1079898600008957_ref085","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19560021007"},{"key":"S1079898600008957_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"S1079898600008957_ref064","first-page":"281","volume-title":"18th International Symposium on Logic in Computer Science (LICS'03)","author":"Hunter","year":"2003"},{"key":"S1079898600008957_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90205-5"},{"key":"S1079898600008957_ref042","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","volume":"1","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Publications Scientifiques de l'Universit\u00e9 d'Alger, S\u00e9rie A"},{"key":"S1079898600008957_ref094","unstructured":"Ritchie R. W. , Classes of recursive functions of predictable complexity, Ph.D. thesis, Princeton University, 1960."},{"key":"S1079898600008957_ref041","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1096901758"},{"key":"S1079898600008957_ref030","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00112-3"},{"key":"S1079898600008957_ref060","unstructured":"Harrow K. , Sub-elementary classes of functions and relations, Ph.D. thesis, New York University, 1973."},{"key":"S1079898600008957_ref050","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_52"},{"key":"S1079898600008957_ref021","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1020"},{"key":"S1079898600008957_ref006","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010403"},{"key":"S1079898600008957_ref059","volume-title":"Introduction to formal language theory","author":"Harrison","year":"1978"},{"key":"S1079898600008957_ref095","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0158822-2"},{"key":"S1079898600008957_ref084","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210118"},{"key":"S1079898600008957_ref052","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18170-9_164"},{"key":"S1079898600008957_ref062","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"S1079898600008957_ref051","doi-asserted-by":"publisher","DOI":"10.1007\/BF01699468"},{"key":"S1079898600008957_ref070","first-page":"157","volume-title":"Conference Record, Fourth Annual ACM Symposium on Theory of Computing","author":"Jones","year":"1972"},{"key":"S1079898600008957_ref001","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.165.547"},{"key":"S1079898600008957_ref005","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19940400308"},{"key":"S1079898600008957_ref024","first-page":"169","article-title":"Eine Bemerkung zur Aufl\u00f6sung der eingeschachtelten Rekursion","volume":"11","author":"Csillag","year":"1947","journal-title":"Acta Universitatis Szegediensis, Acta Scientiarum Mathematicarum"},{"key":"S1079898600008957_ref073","doi-asserted-by":"publisher","DOI":"10.2307\/2267457"},{"key":"S1079898600008957_ref086","volume-title":"Linear bounded automata","author":"Myhill","year":"1960"},{"key":"S1079898600008957_ref004","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"S1079898600008957_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90015-A"},{"key":"S1079898600008957_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"S1079898600008957_ref033","doi-asserted-by":"publisher","DOI":"10.1070\/RM1965v020n04ABEH001188"},{"key":"S1079898600008957_ref012","unstructured":"Chateau A. , Utilisation des destin\u00e9es pour la d\u00e9cision et sa complexit\u00e9 dans le cas de formules \u00e0 profondeur de quantification born\u00e9e sur des structures logiques finies et infinies, Ph.D. thesis, Universit\u00e9 d'Auvergne, 2003."},{"key":"S1079898600008957_ref043","unstructured":"Friedman H. , Primitive recursive reals, http:\/\/www.es.nyu.edu\/pipermail\/fom\/2006\u2013April\/010452.html, April 2006."},{"key":"S1079898600008957_ref007","unstructured":"Bennett J. H. , On spectra, Ph.D. thesis, Princeton University, Princeton, New Jersey, USA, 1962."},{"key":"S1079898600008957_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90218-I"},{"key":"S1079898600008957_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07805-3_8"},{"key":"S1079898600008957_ref026","unstructured":"Dahlhaus E. , Combinatorial and logical properties of reductions to some complete problems in NP and NL, Ph.D. thesis, Technische Universit\u00e4t Berlin, Germany, 1982."},{"key":"S1079898600008957_ref002","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"S1079898600008957_ref069","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"S1079898600008957_ref054","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90009-A"},{"key":"S1079898600008957_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.08.018"},{"key":"S1079898600008957_ref053","doi-asserted-by":"publisher","DOI":"10.1137\/0217050"},{"key":"S1079898600008957_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_50"},{"key":"S1079898600008957_ref016","unstructured":"Christen C. A. , Spektralproblem und Komplexit\u00e4tstheorie, Ph.D. thesis, Eidgen\u00f6ssische Technische Hochschule (ETH), Z\u00fcrich, Switzerland, 1974."},{"key":"S1079898600008957_ref068","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2031"},{"key":"S1079898600008957_ref058","volume-title":"Graphical enumeration","author":"Harary","year":"1973"},{"key":"S1079898600008957_ref046","first-page":"53","volume":"3","author":"Gr\u00e4del","year":"1997","journal-title":"On the decision problem for two-variable first-order logic"},{"key":"S1079898600008957_ref048","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80043-6"},{"key":"S1079898600008957_ref027","volume-title":"Graph theory","author":"Diestel","year":"1996"},{"key":"S1079898600008957_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S1079898600008957_ref067","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S1079898600008957_ref035","unstructured":"Fagin R. , Contributions to the model theory of finite structures, Ph.D. thesis. University of California, Berkeley, California, 1973."},{"key":"S1079898600008957_ref031","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S1079898600008957_ref074","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"S1079898600008957_ref055","first-page":"1","article-title":"Some classes of recursive functions","volume":"4","author":"Grzegorczyk","year":"1953","journal-title":"Rosprawy Matematyczne"},{"key":"S1079898600008957_ref056","first-page":"291","volume-title":"18th IEEE Symposium on Logic in Computer Science (LICS 2003)","author":"Gurevich","year":"2003"},{"key":"S1079898600008957_ref078","doi-asserted-by":"publisher","DOI":"10.1007\/BF01458217"},{"key":"S1079898600008957_ref038","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210117"},{"key":"S1079898600008957_ref057","first-page":"30","volume-title":"Mathematical Foundations of Computer Science 1975","volume":"32","author":"H\u00e1jek","year":"1975"},{"key":"S1079898600008957_ref047","doi-asserted-by":"crossref","DOI":"10.1063\/1.4822863","volume-title":"Concrete mathematics. A foundation for computer science","author":"Graham","year":"1989"},{"key":"S1079898600008957_ref049","doi-asserted-by":"publisher","DOI":"10.1137\/0213025"},{"key":"S1079898600008957_ref104","doi-asserted-by":"publisher","DOI":"10.2307\/2267043"},{"key":"S1079898600008957_ref037","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"S1079898600008957_ref014","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710005"},{"key":"S1079898600008957_ref025","volume-title":"Review of[85]","author":"Curry"},{"key":"S1079898600008957_ref040","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"S1079898600008957_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028015"},{"key":"S1079898600008957_ref032","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"S1079898600008957_ref018","first-page":"51","volume-title":"IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, Schenectady, New York","author":"Cobham","year":"1968"},{"key":"S1079898600008957_ref061","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"}],"container-title":["The Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600008957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T02:10:49Z","timestamp":1594865449000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600008957\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":112,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["S1079898600008957"],"URL":"https:\/\/doi.org\/10.2178\/bsl.1804020","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]}}}