{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T10:59:23Z","timestamp":1779361163167,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,6,11]],"date-time":"2009-06-11T00:00:00Z","timestamp":1244678400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00224-009-9222-6","type":"journal-article","created":{"date-parts":[[2009,6,10]],"date-time":"2009-06-10T13:47:41Z","timestamp":1244641661000},"page":"737-760","source":"Crossref","is-referenced-by-count":9,"title":["Logic and Rational Languages of Words Indexed by\u00a0Linear Orderings"],"prefix":"10.1007","volume":"46","author":[{"given":"Nicolas","family":"Bedon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexis","family":"B\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Carton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chlo\u00e9","family":"Rispal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,6,11]]},"reference":[{"issue":"3","key":"9222_CR1","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1006\/jcss.2001.1782","volume":"63","author":"N. Bedon","year":"2001","unstructured":"Bedon, N.: Logic over words on denumerable ordinals. J. Comput. Syst. Sci. 63(3), 394\u2013431 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9222_CR2","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/11505877_12","volume-title":"DLT\u20192005","author":"N. Bedon","year":"2005","unstructured":"Bedon, N., Rispal, C.: Sch\u00fctzenberger and Eilenberg theorems for words on linear orderings. In: De Felice, C., Restivo, A. (eds.) DLT\u20192005. Lect. Notes in Comput. Sci., vol. 3572, pp. 134\u2013145. Springer, Berlin (2005)"},{"issue":"3","key":"9222_CR3","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1142\/S0129054106003978","volume":"17","author":"A. B\u00e8s","year":"2006","unstructured":"B\u00e8s, A., Carton, O.: A Kleene theorem for languages of words indexed by linear orderings. Int. J. Found. Comput. Sci. 17(3), 519\u2013542 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9222_CR4","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-44683-4_21","volume-title":"MFCS\u20192001","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\u20192001. Lect. Notes in Comput. Sci., vol. 2136, pp. 236\u2013247. Springer, Berlin (2001)"},{"key":"9222_CR5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-0-387-35608-2_10","volume-title":"Foundation of Information Technology in the Era of Network and Mobile Computing","author":"V. Bruy\u00e8re","year":"2002","unstructured":"Bruy\u00e8re, V., Carton, O.: Hierarchy among automata on linear orderings. In: Baeza-Yate, R., Montanari, U., Santoro, N. (eds.) Foundation of Information Technology in the Era of Network and Mobile Computing, pp. 107\u2013118. Kluwer Academic, Dordrecht (2002)"},{"issue":"1","key":"9222_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2006.10.009","volume":"73","author":"V. Bruy\u00e8re","year":"2007","unstructured":"Bruy\u00e8re, V., Carton, O.: Automata on linear orderings. J. Comput. Syst. Sci. 73(1), 1\u201324 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"9222_CR7","doi-asserted-by":"crossref","unstructured":"Bruy\u00e8re, V., Carton, O., S\u00e9nizergues, G.: Tree automata and automata on linear orderings. In: Harju, T., Karhum\u00e4ki, J. (eds.) WORDS\u20192003, pp. 222\u2013231. Turku Center for Computer Science (2003)","DOI":"10.1007\/3-540-45005-X_9"},{"key":"9222_CR8","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Log. Grundl. Math. 6, 66\u201392 (1960)","journal-title":"Z. Math. Log. Grundl. Math."},{"key":"9222_CR9","first-page":"1","volume-title":"Proc. Int. Congress Logic, Methodology and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1962","unstructured":"B\u00fcchi, J.R.: On a decision method in the restricted second-order arithmetic. In: Proc. Int. Congress Logic, Methodology and Philosophy of Science, Berkeley, 1960, pp. 1\u201311. Stanford University Press, Stanford (1962)"},{"key":"9222_CR10","first-page":"2","volume-title":"Proc. Int. Congress Logic, Methodology, and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1965","unstructured":"B\u00fcchi, J.R.: Transfinite automata recursions and weak second order theory of ordinals. In: Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem, 1964, pp. 2\u201323. North-Holland, Amsterdam (1965)"},{"key":"9222_CR11","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/3-540-45687-2_12","volume-title":"MFCS\u20192002","author":"O. Carton","year":"2002","unstructured":"Carton, O.: Accessibility in automata on scattered linear orderings. In: Diks, K., Rytter, W. (eds.) MFCS\u20192002. Lect. Notes in Comput. Sci., vol. 2420, pp. 155\u2013164. Springer, Berlin (2002)"},{"key":"9222_CR12","series-title":"Perspectives in Mathematical Logic","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. Perspectives in Mathematical Logic, pp. 479\u2013506. Springer, Berlin (1985)"},{"key":"9222_CR13","doi-asserted-by":"crossref","unstructured":"Ladner, R.E.: Application of model theoretic games to discrete linear orders and finite automata. Inf. Control 33 (1977)","DOI":"10.1016\/S0019-9958(77)90443-0"},{"key":"9222_CR14","volume-title":"Counter Free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter Free Automata. MIT Press, Cambridge (1971)"},{"key":"9222_CR15","first-page":"939","volume":"303","author":"C. Michaux","year":"1986","unstructured":"Michaux, C., Point, F.: Les ensembles k-reconnaissables sont d\u00e9finissables dans \u2329N,+,V k \u232a (the k-recognizable sets are definable in \u2329N,+,V k \u232a). C. R. Acad. Sci. Paris, S\u00e9r. I 303, 939\u2013942 (1986)","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r. I"},{"key":"9222_CR16","series-title":"Lect. Notes in Comput. Sci.","first-page":"2","volume-title":"Automata on Infinite Words","author":"D. Perrin","year":"1984","unstructured":"Perrin, D.: An introduction to automata on infinite words. In: Nivat, M. (ed.) Automata on Infinite Words. Lect. Notes in Comput. Sci., vol. 192, pp. 2\u201317. Springer, Berlin (1984)"},{"key":"9222_CR17","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/BFb0030294","volume-title":"Mathematical Foundations of Computer Science","author":"D. Perrin","year":"1984","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: Chytil, M.P., Koubek, V. (eds.) Mathematical Foundations of Computer Science. Lect. Notes in Comput. Sci., vol. 176, pp. 134\u2013148. Springer, Berlin (1984)"},{"key":"9222_CR18","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0022-0000(86)90037-1","volume":"32","author":"D. Perrin","year":"1986","unstructured":"Perrin, D., Pin, J.E.: First order logic and star-free sets. J. Comput. Syst. Sci. 32, 393\u2013406 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"9222_CR19","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. Am. Math. Soc. 141, 1\u201335 (1969)","journal-title":"Trans. Am. Math. Soc."},{"key":"9222_CR20","unstructured":"Rispal, C.: Automates sur les ordres lin\u00e9aires: compl\u00e9mentation. PhD thesis, University of Marne-la-Vall\u00e9e, France (2004)"},{"key":"9222_CR21","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/978-3-540-30550-7_32","volume-title":"DLT\u20192004","author":"C. Rispal","year":"2004","unstructured":"Rispal, C., Carton, O.: Complementation of rational sets on countable scattered linear orderings. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT\u20192004. Lect. Notes in Comput. Sci., vol. 3340, pp. 381\u2013392. Springer, Berlin (2004)"},{"key":"9222_CR22","volume-title":"Linear Orderings","author":"J.G. Rosenstein","year":"1982","unstructured":"Rosenstein, J.G.: Linear Orderings. Academic Press, New York (1982)"},{"key":"9222_CR23","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.P. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"9222_CR24","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Ann. Math. 102, 379\u2013419 (1975)","journal-title":"Ann. Math."},{"key":"9222_CR25","doi-asserted-by":"crossref","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, Basel (1994)"},{"key":"9222_CR26","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/S0019-9958(79)90629-6","volume":"42","author":"W. Thomas","year":"1979","unstructured":"Thomas, W.: Star free regular sets of \u03c9-sequences. Inf. Control 42, 148\u2013156 (1979)","journal-title":"Inf. Control"},{"key":"9222_CR27","series-title":"Lect. Notes in Comput. Sci.","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: Structures in Logic and Computer Science, a Selection of Essays in Honor of A. Ehrenfeucht. Lect. Notes in Comput. Sci., vol. 1261, pp. 118\u2013143. Springer, Berlin (1997)"},{"key":"9222_CR28","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. III, pp. 389\u2013455. Springer, Berlin (1997)"},{"issue":"3\u20134","key":"9222_CR29","doi-asserted-by":"crossref","first-page":"379","DOI":"10.3233\/FI-1985-83-407","volume":"8","author":"J. Wojciechowski","year":"1985","unstructured":"Wojciechowski, J.: Finite automata on transfinite sequences and regular expressions. Fundam. Inform. 8(3\u20134), 379\u2013396 (1985)","journal-title":"Fundam. Inform."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9222-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9222-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9222-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T06:41:23Z","timestamp":1633588883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9222-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,11]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["9222"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9222-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,11]]}}}