{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T17:15:01Z","timestamp":1784308501790,"version":"3.55.0"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3663,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,3]]},"abstract":"Abstract<\/jats:title>The paper discusses the notion of finite model truth definitions<\/jats:italic> (or FM-truth definitions<\/jats:italic>), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition.<\/jats:p>We compare FM-truth definitions with Vardi's concept of the combined complexity<\/jats:italic> of logics, noting an important difference: the difficulty of defining FM-truth for a logic does not depend on the syntax of , as long as it is decidable. It follows that for a natural there exist FM-truth definitions whose evaluation is much easier than the combined complexly of would suggest.<\/jats:p>We apply the general theory to give a complexity-theoretical characterization of the logics for which the classes (prenex classes of higher order logics) define FM-truth. For any d<\/jats:italic> \u2265 2, m<\/jats:italic> \u2265 1 we construct a family of syntactically defined fragments of which satisfy this characterization. We also use the classes to give a refinement of known results on the complexity classes captured by .<\/jats:p>We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary \u03c3, of a fixed number k<\/jats:italic> such that model checking for all first order sentences over \u03c3 can be done in deterministic time nk<\/jats:sup><\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1080938836","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:29:06Z","timestamp":1109780946000},"page":"183-200","source":"Crossref","is-referenced-by-count":9,"title":["Truth definitions in finite models"],"prefix":"10.1017","volume":"69","author":[{"given":"Leszek Aleksander","family":"Ko\u0142odziejczyk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200008112_ref019","unstructured":"Zdanowski K. , Arithmetics in finite hut potentially infinite worlds, Ph. D. Thesis , Warsaw University, in preparation."},{"key":"S0022481200008112_ref012","first-page":"228","volume-title":"Handbook of logic in artificial intelligence and logic programming","volume":"2","author":"Leivant","year":"1994"},{"key":"S0022481200008112_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"S0022481200008112_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71820-2"},{"key":"S0022481200008112_ref006","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin","year":"1974","journal-title":"Complexity of Computation, S1AM-AMS Proceedings"},{"key":"S0022481200008112_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9"},{"key":"S0022481200008112_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90019-6"},{"key":"S0022481200008112_ref015","volume-title":"Proceedings of Contributed Papers, LMPhSc 99","author":"Mostowski"},{"key":"S0022481200008112_ref004","unstructured":"Christen C. A. , Spektren und Klassen Elementarer Funktionen, Ph. D. Thesis , ETH Z\u00fcrich, 1974."},{"key":"S0022481200008112_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00013-5"},{"key":"S0022481200008112_ref007","first-page":"545","volume":"62","author":"Gottlob","year":"1997","journal-title":"Relativized Logspace and generalized quantifiers over finite ordered structures"},{"key":"S0022481200008112_ref014","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200111)47:4<513::AID-MALQ513>3.0.CO;2-J"},{"key":"S0022481200008112_ref018","first-page":"137","volume-title":"Proceedings of the 14th ACM Symposium on Theory of Computing","author":"Vardi","year":"1982"},{"key":"S0022481200008112_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0022481200008112_ref002","unstructured":"Bennett J. , On spectra, Ph. D. Thesis , Princeton University, 1962."},{"key":"S0022481200008112_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00033-X"},{"key":"S0022481200008112_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00057-8"},{"key":"S0022481200008112_ref009","volume-title":"Technical Report 5\/2003","author":"Hella","year":"2003"},{"key":"S0022481200008112_ref017","first-page":"152","volume-title":"Poj\u0229cie prawdy w j\u0119zykach nauk dedukcyjnych","author":"Tarski","year":"1933"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200008112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T17:28:22Z","timestamp":1557163702000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200008112\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["S0022481200008112"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1080938836","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}