{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T05:59:57Z","timestamp":1649138397381},"reference-count":14,"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":"<jats:title>Abstract<\/jats:title><jats:p>This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].<\/jats:p><jats:p>We introduce an operation <jats:italic>exists<jats:sub>n<\/jats:sub><\/jats:italic> (<jats:italic>S<\/jats:italic>) on properties <jats:italic>S<\/jats:italic> that says \u201cthere are <jats:italic>n<\/jats:italic> components having <jats:italic>S<\/jats:italic>\u201d. We use this operation to show that under natural strictness conditions, adding a first order quantifier word <jats:italic>u<\/jats:italic> to the beginning of a prefix class <jats:italic>V<\/jats:italic> increases the expressive power monotonically in <jats:italic>u<\/jats:italic>. As a corollary, if the first order quantifiers are not already absorbed in <jats:italic>V<\/jats:italic>, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of <jats:italic>V<\/jats:italic> are strict.<\/jats:p><jats:p>We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties <jats:italic>S, S<\/jats:italic> cannot belong to the positive first order closure of a monadic prefix class <jats:italic>W<\/jats:italic> unless it already belongs to <jats:italic>W<\/jats:italic>.<\/jats:p><jats:p>We introduce another operation <jats:italic>alt<\/jats:italic>(<jats:italic>S<\/jats:italic>) on properties which has the same relationship with the Circuit Value Problem as <jats:italic>reach<\/jats:italic>(<jats:italic>S<\/jats:italic>) (defined in [JM01]) has with the Directed Reachability Problem. We use <jats:italic>alt<\/jats:italic>(<jats:italic>S<\/jats:italic>) to show that \u03a0<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic> \u2288 <jats:italic>FO<\/jats:italic>(\u03a3<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>), \u03a3<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic> \u2288 <jats:italic>FO<\/jats:italic>(\u2206<jats:italic><jats:sub>n<\/jats:sub><\/jats:italic>). and \u2206<jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub> \u2288 <jats:italic>FOB<\/jats:italic>(\u03a3<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>), solving some open problems raised in [Mat98].<\/jats:p>","DOI":"10.2178\/jsl\/1080938831","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:27:19Z","timestamp":1109798839000},"page":"118-136","source":"Crossref","is-referenced-by-count":2,"title":["First order quantifiers in monadic second order logic"],"prefix":"10.1017","volume":"69","author":[{"given":"H. Jerome","family":"Keisler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wafik Boulos","family":"Lotfallah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200008069_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0022481200008069_ref009","volume-title":"Proceedings of STACS","author":"Janin","year":"2001"},{"key":"S0022481200008069_ref013","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614951"},{"key":"S0022481200008069_ref001","first-page":"113","volume":"55","author":"Ajtai","year":"1990","journal-title":"Reachability is harder for directed than for undirected finite graphs"},{"key":"S0022481200008069_ref007","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"S0022481200008069_ref004","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1999"},{"key":"S0022481200008069_ref005","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":"S0022481200008069_ref002","first-page":"309","volume-title":"Journal of Computer and System Sciences","author":"Ajtai","year":"1998"},{"key":"S0022481200008069_ref006","first-page":"43","volume-title":"Complexity of computation","volume":"7","author":"Fagin","year":"1974"},{"key":"S0022481200008069_ref003","first-page":"660","article-title":"The closure of monadic NP","volume":"60","author":"Ajtai","year":"2000","journal-title":"Proceedings of 13th STOC"},{"key":"S0022481200008069_ref011","first-page":"338","volume-title":"Proceedings of the Annual Conference of the European Association of Computer Science Logic, (CSL 99)","volume":"1683","author":"Marcinkowski"},{"key":"S0022481200008069_ref012","volume-title":"Technical Report 9807","author":"Matz","year":"1998"},{"key":"S0022481200008069_ref010","first-page":"79","volume":"38","author":"Keisler","year":"1973","journal-title":"The diversity of quantifier prefixes"},{"key":"S0022481200008069_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200008069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T21:29:05Z","timestamp":1557178145000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200008069\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["S0022481200008069"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1080938831","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}