{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T06:51:01Z","timestamp":1760079061370},"reference-count":63,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3479,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>We show that the spectrum of a sentence <jats:italic>\u03d5<\/jats:italic> in Counting Monadic Second Order Logic (<jats:italic>CMSOL<\/jats:italic>) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of <jats:italic>\u03d5<\/jats:italic> are of clique width at most <jats:italic>k<\/jats:italic>, for some fixed <jats:italic>k<\/jats:italic>. We prove a similar statement for arbitrary finite relational vocabularies <jats:italic>\u03c4<\/jats:italic> and a variant of clique width for <jats:italic>\u03c4<\/jats:italic>-structures. This includes the cases where the models of <jats:italic>\u03d5<\/jats:italic> are of tree width at most <jats:italic>k<\/jats:italic>. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic <jats:italic>GSOL<\/jats:italic>. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle.<\/jats:p><jats:p>Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.<\/jats:p>","DOI":"10.2178\/jsl\/1096901758","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:40:02Z","timestamp":1109781602000},"page":"617-640","source":"Crossref","is-referenced-by-count":7,"title":["On spectra of sentences of monadic second order logic with counting"],"prefix":"10.1017","volume":"69","author":[{"given":"E.","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007544_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"S0022481200007544_ref033","first-page":"1","volume-title":"Handbook of formal languages","volume":"3","author":"G\u00e9cseg","year":"1997"},{"key":"S0022481200007544_ref020","volume-title":"Graph theory","author":"Diestel","year":"1996"},{"key":"S0022481200007544_ref063","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"S0022481200007544_ref060","volume-title":"Classification theory and the number of non-isomorphic models","volume":"92","author":"Shelah","year":"1990"},{"key":"S0022481200007544_ref032","unstructured":"Fischer E. and Makowsky J. A. , Patch-width, a generalization of clique-width for relational structures, in preparation, 2004."},{"key":"S0022481200007544_ref059","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"S0022481200007544_ref058","first-page":"160","volume":"17","author":"Scholz","year":"1952","journal-title":"Problem #1: Ein ungel\u00f6stes Problem in der symbolischen Logik"},{"key":"S0022481200007544_ref052","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000241"},{"key":"S0022481200007544_ref053","first-page":"89","article-title":"Solutions to the Scholz problem","volume":"12","author":"Mo","year":"1991","journal-title":"Chinese Annals of Mathematics, Series A"},{"key":"S0022481200007544_ref002","first-page":"29","volume-title":"Applications scientifiques de la logique math\u00e9matique","volume":"5","author":"Beth","year":"1954"},{"key":"S0022481200007544_ref051","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00013-5"},{"key":"S0022481200007544_ref050","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00449-8"},{"key":"S0022481200007544_ref055","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"S0022481200007544_ref017","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003565"},{"key":"S0022481200007544_ref062","first-page":"141","volume-title":"Trends in theoretical computer science","author":"Specker","year":"1988"},{"key":"S0022481200007544_ref054","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00018-M"},{"key":"S0022481200007544_ref048","unstructured":"Makowsky J. A. , Logical methods in graph algorithms, lecture notes of a course given at ESSLLI '99 in Utrecht , 08, 1999."},{"key":"S0022481200007544_ref040","first-page":"291","volume-title":"LiCS '03, IEEE","author":"Gurevich","year":"2003"},{"key":"S0022481200007544_ref013","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1020"},{"key":"S0022481200007544_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90019-1"},{"key":"S0022481200007544_ref022","first-page":"189","volume-title":"CSL \u201997","volume":"1414","author":"Durand","year":"1997"},{"key":"S0022481200007544_ref004","first-page":"1","article-title":"A tourist guide through tree width","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybernetica"},{"key":"S0022481200007544_ref003","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/3-540-18170-9_164","volume-title":"Computation theory and logic","volume":"270","author":"Blatter","year":"1987"},{"key":"S0022481200007544_ref038","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90009-A"},{"key":"S0022481200007544_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_21"},{"key":"S0022481200007544_ref025","volume-title":"Mathematical logic","author":"Ebbinghaus","year":"1980"},{"key":"S0022481200007544_ref061","article-title":"Spectra of monadic second order sentences","author":"Shelah","year":"2004","journal-title":"Japanese Journal of Mathematics"},{"key":"S0022481200007544_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S0022481200007544_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204169"},{"key":"S0022481200007544_ref029","doi-asserted-by":"publisher","DOI":"10.4064\/fm-47-1-57-103"},{"key":"S0022481200007544_ref057","unstructured":"Rotics U. , Efficient algorithms for generally intractable graph problems restricted to specific classes of graphs, Ph. D. thesis , Technion-Israel Institute of Technology, 1998."},{"key":"S0022481200007544_ref009","first-page":"126","volume-title":"Proceedings of LATIN 2000","volume":"1776","author":"Corneil","year":"2000"},{"key":"S0022481200007544_ref042","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0022481200007544_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"S0022481200007544_ref039","first-page":"481","volume":"44","author":"Gurevich","year":"1979","journal-title":"Modest theory of short chains, I"},{"key":"S0022481200007544_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00112-3"},{"key":"S0022481200007544_ref007","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"S0022481200007544_ref045","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)86542-5"},{"key":"S0022481200007544_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07805-3_8"},{"key":"S0022481200007544_ref043","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2031"},{"key":"S0022481200007544_ref041","volume-title":"Hyperedge replacement: Grammars and languages","volume":"643","author":"Habel","year":"1992"},{"key":"S0022481200007544_ref024","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S0022481200007544_ref026","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1510"},{"key":"S0022481200007544_ref049","volume-title":"Annals of Pure and Applied Logic","author":"Makowsky","year":"2004"},{"key":"S0022481200007544_ref027","first-page":"27","volume-title":"Complexity of computation","volume":"7","author":"Fagin","year":"1974"},{"key":"S0022481200007544_ref028","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"S0022481200007544_ref030","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00075-X"},{"key":"S0022481200007544_ref034","first-page":"333","article-title":"Bounded Algol-like languages","volume":"113","author":"Ginsburg","year":"1966","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200007544_ref036","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000260"},{"key":"S0022481200007544_ref001","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010403"},{"key":"S0022481200007544_ref037","first-page":"217","volume-title":"LiCS 2000","author":"Gr\u00e4del","year":"2000"},{"key":"S0022481200007544_ref047","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786976"},{"key":"S0022481200007544_ref056","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90120-O"},{"key":"S0022481200007544_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"S0022481200007544_ref044","first-page":"139","volume":"39","author":"Jones","year":"1972","journal-title":"Turing machines and spectra of first order formulas"},{"key":"S0022481200007544_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"S0022481200007544_ref046","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19770233608"},{"key":"S0022481200007544_ref005","first-page":"29","volume-title":"Proceedings of the 22th International Symposium on the Mathematical Foundation of Computer Science, MFCS \u201997","volume":"1295","author":"Bodlaender","year":"1997"},{"key":"S0022481200007544_ref014","doi-asserted-by":"publisher","DOI":"10.1142\/9789812384720_0005"},{"key":"S0022481200007544_ref031","first-page":"90","volume-title":"Cocoon '03","volume":"2697","author":"Fischer","year":"2003"},{"key":"S0022481200007544_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00221-3"},{"key":"S0022481200007544_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90148-9"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T16:27:19Z","timestamp":1557160039000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007544\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["S0022481200007544"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1096901758","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}