{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:28:19Z","timestamp":1777645699090,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1-4","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>We study an extension of monadic second-order logic of order with\n\t\t\t the uncountability quantifier \"there exist uncountably many\n\t\t\t sets\". We prove that, over the class of finitely branching trees,\n\t\t\t this extension is equally expressive to plain monadic second-order logic of\n\t\t\t order.<\/jats:p>\n                  <jats:p>Additionally we find that the continuum hypothesis holds for classes of\n\t\t\t sets definable in monadic second-order logic over finitely branching trees,\n\t\t\t which is notable for not all of these classes are analytic.<\/jats:p>\n                  <jats:p>Our approach is based on Shelah's composition method and uses basic results from\n\t\t\t descriptive set theory. The elimination result is constructive, yielding a\n\t\t\t decision procedure for the extended logic.<\/jats:p>","DOI":"10.3233\/fi-2010-260","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T23:08:01Z","timestamp":1575328081000},"page":"1-17","source":"Crossref","is-referenced-by-count":9,"title":["Expressing Cardinality Quantifiers in Monadic Second-Order Logic\t\t\t over Trees"],"prefix":"10.1177","volume":"100","author":[{"given":"Vince","family":"B\u00e1r\u00e1ny","sequence":"first","affiliation":[{"name":"Oxford University Computing Laboratory, United Kingdom.\r\t\t\t E-mail: vbarany@comlab.ox.ac.uk"}]},{"given":"\u0141ukasz","family":"Kaiser","sequence":"additional","affiliation":[{"name":"RWTH Aachen, Mathematische Grundlagen der Informatik,\r\t\t\t Germany. E-mail: kaiser@logic.rwth-aachen.de"}]},{"given":"Alex","family":"Rabinovich","sequence":"additional","affiliation":[{"name":"Tel Aviv University, The Blavatnik School of Computer\r\t\t\t Science, Israel. E-mail: rabinoa@post.tau.ac.il"}]}],"member":"179","published-online":{"date-parts":[[2010,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-260","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2010-260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:33:02Z","timestamp":1777444382000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2010-260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":0,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.3233\/FI-2010-260"],"URL":"https:\/\/doi.org\/10.3233\/fi-2010-260","relation":{"is-cited-by":[{"id-type":"doi","id":"10.4204\/EPTCS.218.1","asserted-by":"object"}]},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}