{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:16Z","timestamp":1725662896087},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108542"},{"type":"electronic","value":"9783540387657"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10854-8_49","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:31:26Z","timestamp":1330191086000},"page":"453-466","source":"Crossref","is-referenced-by-count":1,"title":["The complexity of automata and subtheories of monadic second order arithmetics"],"prefix":"10.1007","author":[{"given":"A. W\u0142odzimierz","family":"Mostowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,28]]},"reference":[{"key":"49_CR1","volume-title":"On a decision method in restricted second ordre arithmetic","author":"J.R. B\u00fcchi","year":"1962","unstructured":"B\u00fcchi J.R., On a decision method in restricted second ordre arithmetic, Proc. of the Int. Congr. on Logic, Math. and Phil. of Sc. 1960, Stanford Univ. Press, Stanford Calif. 1962."},{"key":"49_CR2","doi-asserted-by":"crossref","unstructured":"B\u00fcchi J.R., Siefkes D., The Monadic second Order Theory of all countable ordinals, Lecture Notes in Math. 328, Decidable Theories II, 1973 pp. 89.","DOI":"10.1007\/BFb0082720"},{"key":"49_CR3","first-page":"441","volume":"XXI","author":"M. Karpi\u0144ski","year":"1973","unstructured":"Karpi\u0144ski M., Free structure tree automata. I. Equivalence, Bull de l'Academie des Sciences, vol. XXI, 1973, pp. 441\u2013446.","journal-title":"Bull de l'Academie des Sciences"},{"key":"49_CR4","first-page":"447","volume":"XXI","author":"M. Karpi\u0144ski","year":"1973","unstructured":"Karpi\u0144ski M., Free structure tree automata. II Nondeterministic and deterministic regularity, Vol. XXI, 1973, pp. 447\u2013450.","journal-title":"II Nondeterministic and deterministic regularity"},{"key":"49_CR5","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"McNaughton R., Testing and generating infinite sequences by a finite automaton. Inform. and Control 9, 1966, p. 521\u2013530.","journal-title":"Inform. and Control"},{"key":"49_CR6","unstructured":"Meyer A.R., Weak Monadic Second Order Theory of Successor is Not Elementary Reoursive. Proc. Boston University Logic Coll. 1972\u20131973, Lecture Notes of Math. 453, 1975, p. 137\u2013154."},{"key":"49_CR7","unstructured":"Mostowski A.W., A note concerning the complexity of a decision problem for positive formulas in SkS, Les Arbres en Algebre et en programmation, 4-eme Colloque de Lille, p. 173\u2013180."},{"key":"49_CR8","unstructured":"Mostowski A.W., Nearly deterministic automata acceptation of infinite trees and a complexity of a weak theory of SkS, Les Arbres en algebre et en programmation, 5-eme Colloque de Lille, 1980, p. 54\u201362."},{"key":"49_CR9","unstructured":"Mostowski A.W., Finite automata on infimite trees and subtheories of SkS, Les Arbres en Algebre et en programmation, 5-eme Colloque de Lille, 1980, p. 228\u2013240"},{"key":"49_CR10","unstructured":"Mostowski A.W., Types of finite automata acceptances and subtheories of SkS, 3rd Symposium on Mathematical Foundations of Computer Science, Zabor\u00f3w, January 21\u201326, 1980, ICS PAS reports, 411, 1980, Warszawa, p. 53\u201357."},{"key":"49_CR11","unstructured":"Mostowski A.W., Positive properties of Infinite trees and nearly deterministic automata, Preprint No 38, Univ. of Gda\u0144sk, p. 1\u201311, (ibidem also text of [7\u20139])."},{"key":"49_CR12","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin M.O., Decidability of Second-Order Theories and Automata on Infinite Trees, Trans. of Amer. Math. Soc. 141, 1969, p. 1\u201335.","journal-title":"Trans. of Amer. Math. Soc."},{"key":"49_CR13","unstructured":"Rabin M.O., Decidability and Definiability of Second-Order Theories Actes, Congres Intern. Math. 1970, tome I, p. 239\u2013244."},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"Rabin M.O., Weakly Definiable Relations and Special Automata, Math. Logic Foundations Set Theory, North Holland, 1970, p. 1\u201323.","DOI":"10.1016\/S0049-237X(08)71929-3"},{"key":"49_CR15","unstructured":"Raceff C.W., The Emptiness and Complementation Problems for Automata on Infinite Trees, MIT 1972 Thesis."},{"key":"49_CR16","unstructured":"Stupp J., The Latties Model is Recursive in the Orginal Model, 1975 Manuscript."},{"key":"49_CR17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher J.W., Wright J.B., Generalised Finite Automata Theory with an Application to a decision Problem of Second Order Logic, Math. System theory, 2, 1968, p. 57\u201382.","journal-title":"Math. System theory"},{"key":"49_CR18","unstructured":"Trachtenbrodt B.A. and Barsdin J.M., Finite Automata, Behavior and Synthesis (in Russian) Moscow 1970."},{"key":"49_CR19","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(79)90653-3","volume":"43","author":"K. Wagner","year":"1979","unstructured":"Wagner K., On \u03c9-regular Sets, Inform. and Control, 43, 1979, p. 123\u2013177.","journal-title":"Inform. and Control"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10854-8_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:03:54Z","timestamp":1605643434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10854-8_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108542","9783540387657"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-10854-8_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}