{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:19Z","timestamp":1761611179355},"reference-count":11,"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":9873,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1987,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let S2S [WS2S] respectively be the strong [weak] monadic second order theory of the binary tree <jats:italic>T<\/jats:italic> in the language of two successor functions. An S2S-formula whose free variables are just individual variables defines a relation on <jats:italic>T<\/jats:italic> (rather than on the power set of <jats:italic>T<\/jats:italic>). We show that S2S and WS2S define the same relations on <jats:italic>T<\/jats:italic>, and we give a simple characterization of these relations.<\/jats:p>","DOI":"10.2307\/2273878","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:20:33Z","timestamp":1146954033000},"page":"219-226","source":"Crossref","is-referenced-by-count":27,"title":["Monadic second order definable relations on the binary tree"],"prefix":"10.1017","volume":"52","author":[{"given":"Hans","family":"L\u00e4uchli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Savioz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200030152_bib007","first-page":"1","volume-title":"Mathematical logic and foundations of set theory (proceedings of an international colloquium, Jerusalem, 1968)","author":"Rabin","year":"1970"},{"key":"S0022481200030152_bib004","first-page":"60","volume-title":"Proceedings of the fourteenth ACM symposium on the theory of computing (San Francisco, 1982)","author":"Gurevich","year":"1982"},{"key":"S0022481200030152_bib003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19800260105"},{"key":"S0022481200030152_bib005","first-page":"3","volume-title":"Automata studies","author":"Kleene","year":"1956"},{"key":"S0022481200030152_bib011","first-page":"334","volume":"45","author":"Thomas","year":"1980","journal-title":"On the bounded monadic theory of well-ordered structures"},{"key":"S0022481200030152_bib009","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0093479-4"},{"key":"S0022481200030152_bib010","unstructured":"Savioz, CH. , Extensions d\u00e9cidantes et ind\u00e9cidables de la th\u00e9orie monadique du deuxi\u00e8me ordre de deux fonctions de successeur, Dissertation No. 7898, ETH, Z\u00fcrich, 1985."},{"key":"S0022481200030152_bib006","first-page":"1","article-title":"Decidability of second order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200030152_bib008","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/013"},{"key":"S0022481200030152_bib001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S0022481200030152_bib002","first-page":"1","volume-title":"Proceedings of the international conference on logic, methodology and philosophy of science, 1960","author":"B\u00fcchi","year":"1962"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200030152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T08:11:42Z","timestamp":1649664702000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/product\/identifier\/S0022481200030152\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,3]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,3]]}},"alternative-id":["S0022481200030152"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.2307\/2273878","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,3]]}}}