{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:59:09Z","timestamp":1725562749909},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153488"},{"type":"electronic","value":"9783642153495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15349-5_3","type":"book-chapter","created":{"date-parts":[[2010,8,21]],"date-time":"2010-08-21T03:39:27Z","timestamp":1282361967000},"page":"29-50","source":"Crossref","is-referenced-by-count":3,"title":["Temporal Logics over Linear Time Domains Are in PSPACE"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Rabinovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-540-79709-8_11","volume-title":"CSR 2008","author":"N. Bedon","year":"2008","unstructured":"Bedon, N., Bes, A., Carton, O., Rispal, C.: Logic and Rational Languages of Words Indexed by Linear Orderings. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol.\u00a05010, pp. 76\u201385. Springer, Heidelberg (2008)"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-44683-4_21","volume-title":"Mathematical Foundations of Computer Science 2001","author":"V. Bruy\u00e8re","year":"2001","unstructured":"Bruy\u00e8re, V., Carton, O.: Automata on linear orderings. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 236\u2013247. Springer, Heidelberg (2001)"},{"key":"3_CR3","first-page":"1","volume-title":"Logic, Methodology and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1962","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford University Press, Stanford (1962)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R., Siefkes, D.: The Monadic Second-order Theory of all Countable Ordinals. Springer Lecture Notes, vol.\u00a0328 (1973)","DOI":"10.1007\/BFb0082721"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1305\/ndjfl\/1093870820","volume":"26","author":"J.P. Burgess","year":"1985","unstructured":"Burgess, J.P., Gurevich, Y.: The decision problem for linear temporal logic. Notre Dame J. Formal Logic\u00a026(2), 115\u2013128 (1985)","journal-title":"Notre Dame J. Formal Logic"},{"key":"3_CR6","unstructured":"Cristau, J.: Automata and temporal logic over arbitrary linear time. In: FSTTCS 2009, pp. 133\u2013144 (2009)"},{"key":"3_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-540-75560-9_38","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"S. Demri","year":"2007","unstructured":"Demri, S., Rabinovich, A.: The Complexity of Temporal Logic with Until and Since over Ordinals. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol.\u00a04790, pp. 531\u2013545. Springer, Heidelberg (2007)"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"S. Feferman","year":"1959","unstructured":"Feferman, S., Vaught, R.L.: The first-order properties of products of algebraic systems. Fundamenta Mathematicae\u00a047, 57\u2013103 (1959)","journal-title":"Fundamenta Mathematicae"},{"key":"3_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0013976","volume-title":"Temporal Logics","author":"D.M. Gabbay","year":"1994","unstructured":"Gabbay, D.M., Hodkinson, I., Reynolds, M.: Temporal Logics, vol.\u00a01. Clarendon Press, Oxford (1994)"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Gabbay, D.M., Pnueli, A., Shelah, S., Stavi, J.: On the Temporal Analysis of Fairness. In: 7th POPL, pp. 163\u2013173 (1980)","DOI":"10.1145\/567446.567462"},{"key":"3_CR11","first-page":"479","volume-title":"Model-Theoretic Logics","author":"Y. Gurevich","year":"1985","unstructured":"Gurevich, Y.: Monadic second-order theories. In: Barwise, J., Feferman, S. (eds.) Model-Theoretic Logics, pp. 479\u2013506. Springer, Heidelberg (1985)"},{"key":"3_CR12","unstructured":"Kamp, H.: Tense Logic and the Theory of Linear Order. Ph.D. thesis, University of California L.A (1968)"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.4064\/fm-59-1-109-116","volume":"59","author":"H. L\u00e4uchli","year":"1966","unstructured":"L\u00e4uchli, H., Leonard, J.: On the elementary theory of linear order. Fundamenta Mathematicae\u00a059, 109\u2013116 (1966)","journal-title":"Fundamenta Mathematicae"},{"key":"3_CR14","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. Transactions of the American Mathematical Society\u00a0141, 1\u201335 (1969)","journal-title":"Transactions of the American Mathematical Society"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Rabinovich, A.: Temporal logics over linear time domains are in PSPACE (manuscript) (2009)","DOI":"10.1007\/978-3-642-15349-5_3"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S0022-0000(03)00005-9","volume":"66","author":"M. Reynolds","year":"2003","unstructured":"Reynolds, M.: The complexity of the temporal logic with until over general linear time. J. Comput. Syst. Sci.\u00a066, 393\u2013426 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"3_CR17","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1016\/j.apal.2010.01.002","volume":"161","author":"M. Reynolds","year":"2010","unstructured":"Reynolds, M.: The Complexity of Temporal Logic over the Reals. The Annals of Pure and Applied Logic\u00a0161(8), 1063\u20131096 (2010)","journal-title":"The Annals of Pure and Applied Logic"},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1142\/S0129054105003285","volume":"16","author":"C. Rispal","year":"2005","unstructured":"Rispal, C., Carton, O.: Complementation of rational sets on countable scattered linear orderings. Int. J. Found. Comput. Sci.\u00a016(4), 767\u2013786 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR19","volume-title":"Linear ordering","author":"J.G. Rosenstein","year":"1982","unstructured":"Rosenstein, J.G.: Linear ordering. Academic Press, New York (1982)"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Ann. of Math.\u00a0102, 349\u2013419 (1975)","journal-title":"Ann. of Math."},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1145\/3828.3837","volume":"32","author":"A.P. Sistla","year":"1985","unstructured":"Sistla, A.P., Clarke, E.M.: The Complexity of Propositional Linear Temporal Logics. J. ACM\u00a032(3), 733\u2013749 (1985)","journal-title":"J. ACM"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/3-540-63246-8_8","volume-title":"Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol.\u00a01261, pp. 118\u2013143. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15349-5_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:04:55Z","timestamp":1606187095000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15349-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153488","9783642153495"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15349-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}