{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T05:10:07Z","timestamp":1746335407179,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662445211"},{"type":"electronic","value":"9783662445228"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44522-8_24","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"279-290","source":"Crossref","is-referenced-by-count":2,"title":["Monadic Second-Order Logic with Arbitrary Monadic Predicates"],"prefix":"10.1007","author":[{"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"first","affiliation":[]},{"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. Journal of Computer and System Sciences\u00a038(1), 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D.A.M. Barrington","year":"1992","unstructured":"Barrington, D.A.M., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular languages in NC1. Journal of Computer and System Sciences\u00a044(3), 478\u2013499 (1992)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.jcss.2004.07.004","volume":"70","author":"D.A.M. Barrington","year":"2005","unstructured":"Barrington, D.A.M., Immerman, N., Lautemann, C., Schweikardt, N., Th\u00e9rien, D.: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. Journal of Computer and System Sciences\u00a070(2), 101\u2013127 (2005)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"24_CR4","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D.A.M. Barrington","year":"1988","unstructured":"Barrington, D.A.M., Th\u00e9rien, D.: Finite monoids and the fine structure of NC1. Journal of the Association for Computing Machinery\u00a035(4), 941\u2013952 (1988)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"24_CR5","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second-order arithmetic. In: Proceedings of the 1st International Congress of Logic, Methodology, and Philosophy of Science, CLMPS 1960, pp. 1\u201311. Stanford University Press (1962)"},{"issue":"1","key":"24_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/inco.2001.3139","volume":"176","author":"O. Carton","year":"2002","unstructured":"Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Information and Computation\u00a0176(1), 51\u201365 (2002)","journal-title":"Information and Computation"},{"issue":"1-3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(94)90254-2","volume":"126","author":"F.M. Dekking","year":"1994","unstructured":"Dekking, F.M.: Iteration of maps by an automaton. Discrete Mathematics\u00a0126(1-3), 81\u201386 (1994)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"24_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1051\/ita\/2013035","volume":"47","author":"F. Durand","year":"2013","unstructured":"Durand, F.: Decidability of the HD0L ultimate periodicity problem. RAIRO Theor. Inform. Appl.\u00a047(2), 201\u2013214 (2013)","journal-title":"RAIRO Theor. Inform. Appl."},{"issue":"2","key":"24_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"C.C. Elgot","year":"1966","unstructured":"Elgot, C.C., Rabin, M.O.: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. Journal of Symbolic Logic\u00a031(2), 169\u2013181 (1966)","journal-title":"Journal of Symbolic Logic"},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM Journal of Computing\u00a016(4), 760\u2013778 (1987)","journal-title":"SIAM Journal of Computing"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Kouck\u00fd, M., Lautemann, C., Poloczek, S., Th\u00e9rien, D.: Circuit Lower Bounds via Ehrenfeucht-Fraiss\u00e9 Games. In: IEEE Conference on Computational Complexity, pp. 190\u2013201 (2006)","DOI":"10.1109\/CCC.2006.12"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"Kruckman, A., Rubin, S., Sheridan, J., Zax, B.: A myhill-nerode theorem for automata with advice. In: Faella, M., Murano, A. (eds.) GandALF. EPTCS, vol.\u00a096, pp. 238\u2013246 (2012)","DOI":"10.4204\/EPTCS.96.18"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Nies, A.: Describing groups. Bulletin of Symbolic Logic\u00a013, 305\u2013339, 9 (2007)","DOI":"10.2178\/bsl\/1186666149"},{"issue":"2","key":"24_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(92)90328-D","volume":"93","author":"P. P\u00e9ladeau","year":"1992","unstructured":"P\u00e9ladeau, P.: Logically defined subsets of \u2115 k . Theoretical Computer Science\u00a093(2), 169\u2013183 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"24_CR15","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1016\/j.ic.2006.12.004","volume":"205","author":"A. Rabinovich","year":"2007","unstructured":"Rabinovich, A.: On decidability of monadic logic of order over the naturals extended by monadic predicates. Information and Computation\u00a0205(6), 870\u2013889 (2007)","journal-title":"Information and Computation"},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2012.06.001","volume":"218","author":"A. Rabinovich","year":"2012","unstructured":"Rabinovich, A.: The Church problem for expansions of (\u2115, <) by unary predicates. Information and Computation\u00a0218, 1\u201316 (2012)","journal-title":"Information and Computation"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/11874683_37","volume-title":"Computer Science Logic","author":"A. Rabinovich","year":"2006","unstructured":"Rabinovich, A., Thomas, W.: Decidable theories of the ordering of natural numbers with unary predicates. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 562\u2013574. Springer, Heidelberg (2006)"},{"key":"24_CR18","unstructured":"Schweikardt, N.: On the Expressive Power of First-Order Logic with Built-In Predicates. PhD thesis, Gutenberg-Universt\u00e4t in Mainz (2001)"},{"key":"24_CR19","series-title":"LNCS","first-page":"162","volume-title":"MFCS","author":"A.L. Semenov","year":"1984","unstructured":"Semenov, A.L.: Decidability of monadic theories. In: Chytil, M., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 162\u2013175. Springer, Heidelberg (1984)"},{"key":"24_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite automata, formal logic, and circuit complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite automata, formal logic, and circuit complexity. Birkh\u00e4user Boston Inc., Boston (1994)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:29:26Z","timestamp":1746332966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}