{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T22:46:04Z","timestamp":1752360364259},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3206,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We say that a first order formula \u03a6 <jats:italic>distinguishes<\/jats:italic> a structure <jats:italic>M<\/jats:italic> over a vocabulary <jats:italic>L<\/jats:italic> from another structure <jats:italic>M<\/jats:italic>\u2032 over the same vocabulary if \u03a6 is true on <jats:italic>M<\/jats:italic> but false on <jats:italic>M<\/jats:italic>\u2032. A formula \u03a6 <jats:italic>defines<\/jats:italic> an <jats:italic>L<\/jats:italic>-structure <jats:italic>M<\/jats:italic> if \u03a6 distinguishes <jats:italic>M<\/jats:italic> from any other non-isomorphic <jats:italic>L<\/jats:italic>-structure <jats:italic>M<\/jats:italic>\u2032. A formula \u03a6 <jats:italic>identifies<\/jats:italic> an <jats:italic>n<\/jats:italic>-element <jats:italic>L<\/jats:italic>-structure <jats:italic>M<\/jats:italic> if \u03a6 distinguishes <jats:italic>M<\/jats:italic> from any other non-isomorphic <jats:italic>n<\/jats:italic>-element <jats:italic>L<\/jats:italic>-structure <jats:italic>M<\/jats:italic>\u2032.<\/jats:p><jats:p>We prove that every <jats:italic>n<\/jats:italic>-element structure <jats:italic>M<\/jats:italic> is identifiable by a formula with quantifier rank less than <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007003_inline1\" \/> and at most one quantifier alternation, where <jats:italic>k<\/jats:italic> is the maximum relation arity of M. Moreover, if the automorphism group of <jats:italic>M<\/jats:italic> contains no transposition of two elements, the same result holds for definability rather than identification.<\/jats:p><jats:p>The Bernays-Sch\u00f6nfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every <jats:italic>n<\/jats:italic>-element structure <jats:italic>M<\/jats:italic> is identifiable by a formula in the Bernays-Sch\u00f6nfinkel class with less than <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007003_inline2\" \/> quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to <jats:italic>k<\/jats:italic>, then less than <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007003_inline3\" \/> quantifiers suffice to identify <jats:italic>M<\/jats:italic> and. as long as we keep the number of universal quantifiers bounded by a constant, at total <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007003_inline4\" \/>quantifiers are necessary.<\/jats:p>","DOI":"10.2178\/jsl\/1120224721","type":"journal-article","created":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T15:02:26Z","timestamp":1120230146000},"page":"419-450","source":"Crossref","is-referenced-by-count":6,"title":["Descriptive complexity of finite structures: Saving the quantifier rank"],"prefix":"10.1017","volume":"70","author":[{"given":"Oleg","family":"Pikhurko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007003_ref015","unstructured":"Pikhurko O. , Veith H. , and Verbitsky O. , First order definability of graphs: tight bounds on quantifier rank, submitted, E-print http:\/\/arxiv.org\/abs\/math.C0\/0311041, 2003."},{"key":"S0022481200007003_ref006","first-page":"35","article-title":"Sur quelques classifications des systems de relations","volume":"1","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Universit\u00e9 d'Alger, Publications Scientifiques, Serie A"},{"key":"S0022481200007003_ref008","first-page":"63","volume-title":"Proceedings of the 32nd ACM Annual Symposium on Theory of Computing (STOC)","author":"Grohe","year":"2000"},{"key":"S0022481200007003_ref003","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1999"},{"key":"S0022481200007003_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"S0022481200007003_ref014","unstructured":"Pikhurko O. , Spencer J. , and Verbitsky O. , Succinct definitions in first order graph theory, submitted, E-print http:\/\/arxiv.org\/abs\/math.C0\/0401307, 2004."},{"key":"S0022481200007003_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0022481200007003_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04538-1"},{"key":"S0022481200007003_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90218-I"},{"key":"S0022481200007003_ref012","volume-title":"Random Structures and Algorithms","author":"Kim","year":"2004"},{"key":"S0022481200007003_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90055-2"},{"key":"S0022481200007003_ref013","first-page":"159","volume-title":"Proceedings of the CSL '98 conference","volume":"1584","author":"Pezzoli","year":"1999"},{"key":"S0022481200007003_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"S0022481200007003_ref004","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","article-title":"An application of games to the completeness problem for formalized theories","volume":"49","author":"Ehrenfeucht","year":"1961","journal-title":"Fundamenta Mathematicae"},{"key":"S0022481200007003_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"S0022481200007003_ref016","unstructured":"Pikhurko O. and Verbitsky O. , Descriptive complexity of finite structures: saving the quantifier rank, E-print http.-\/\/arxiv.org\/abs\/math.L0\/0305244, 2003."},{"key":"S0022481200007003_ref007","first-page":"6","volume-title":"Proceedings of the Annual Conference on Logic in Computer Science","author":"Grohe","year":"1998"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T20:50:08Z","timestamp":1556916608000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007003\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["S0022481200007003"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1120224721","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}