{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:09:01Z","timestamp":1750306141387,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alan Turing Institute under the EPSRC","award":["EP\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}]},{"name":"French Agence Nationale de la Recherche, AGGREG project","award":["ANR-14-CE25-0017-01"],"award-info":[{"award-number":["ANR-14-CE25-0017-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            We study Monadic Second-Order Logic (\n            <jats:bold>MSO<\/jats:bold>\n            ) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic, and machine-independent characterizations. We consider the\n            <jats:italic>regularity question<\/jats:italic>\n            : Given a language in this class, when is it regular? To answer this, we show a\n            <jats:italic>substitution property<\/jats:italic>\n            and the existence of a\n            <jats:italic>syntactical predicate<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We give three applications. The first two are to give very simple proofs that the Straubing Conjecture holds for all fragments of\n            <jats:bold>MSO<\/jats:bold>\n            with monadic predicates and that the Crane Beach Conjecture holds for\n            <jats:bold>MSO<\/jats:bold>\n            with monadic predicates. The third is to show that it is decidable whether a language defined by an\n            <jats:bold>MSO<\/jats:bold>\n            formula with morphic predicates is regular.\n          <\/jats:p>","DOI":"10.1145\/3091124","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Monadic Second-Order Logic with Arbitrary Monadic Predicates"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6576-4680","authenticated-orcid":false,"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"first","affiliation":[{"name":"University of Warwick"}]},{"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[{"name":"Institut Math\u00e9matiques de Jussieu, Paris rive gauche, France"}]}],"member":"320","published-online":{"date-parts":[[2017,8,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.07.004"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1029"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Congress on Logic, Methodology, and Philosophy of Science (CLMPS\u201962)","author":"B\u00fcchi Julius R.","year":"1962","unstructured":"Julius R. B\u00fcchi . 1962 . On a decision method in restricted second-order arithmetic . In Proceedings of the Congress on Logic, Methodology, and Philosophy of Science (CLMPS\u201962) . Stanford University Press, 1--11. Julius R. B\u00fcchi. 1962. On a decision method in restricted second-order arithmetic. In Proceedings of the Congress on Logic, Methodology, and Philosophy of Science (CLMPS\u201962). Stanford University Press, 1--11."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3139"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2013035"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269808"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80062-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_2_1_13_1","unstructured":"Mitrofanov Ivan. 2012. A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780.  Mitrofanov Ivan. 2012. A proof for the decidability of HD0L ultimate periodicity. arXiv:1110.4780."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_27"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.12"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.96.18"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1186666149"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90328-D"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.12.004"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.06.001"},{"key":"e_1_2_1_21_1","first-page":"351","article-title":"More on generalized automatic sequences","volume":"7","author":"Rigo Michel","year":"2002","unstructured":"Michel Rigo and Arnaud Maes . 2002 . More on generalized automatic sequences . J. Auto. Lang. Combinat. 7 , 3, 351 -- 376 . Michel Rigo and Arnaud Maes. 2002. More on generalized automatic sequences. J. Auto. Lang. Combinat. 7, 3, 351--376.","journal-title":"J. Auto. Lang. Combinat."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_37"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030296"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55719-9_60"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1067"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1318338853"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3091124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3091124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:28Z","timestamp":1750217848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3091124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3091124"],"URL":"https:\/\/doi.org\/10.1145\/3091124","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}