{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:00:16Z","timestamp":1725512416040},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797081"},{"type":"electronic","value":"9783540797098"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79709-8_11","type":"book-chapter","created":{"date-parts":[[2008,5,13]],"date-time":"2008-05-13T14:33:17Z","timestamp":1210689197000},"page":"76-85","source":"Crossref","is-referenced-by-count":8,"title":["Logic and Rational Languages of Words Indexed by Linear Orderings"],"prefix":"10.1007","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","reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"publisher","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. Journal of Computer and System Science\u00a063(3), 394\u2013431 (2001)","journal-title":"Journal of Computer and System Science"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/11505877_12","volume-title":"Developments in Language Theory","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 2005. LNCS, vol.\u00a03572, pp. 134\u2013145. Springer, Heidelberg (2005)"},{"issue":"3","key":"11_CR3","doi-asserted-by":"publisher","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.\u00a017(3), 519\u2013542 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"11_CR4","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":"11_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 Publishers, Dordrecht (2002)"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","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. System Sci.\u00a073(1), 1\u201324 (2007)","journal-title":"J. Comput. System Sci."},{"key":"11_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 2003, pp. 222\u2013231. Turku Center for Computer Science (2003)","DOI":"10.1007\/3-540-45005-X_9"},{"key":"11_CR8","doi-asserted-by":"publisher","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. Logik und grundl. Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik und grundl. Math."},{"key":"11_CR9","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 (1962)"},{"key":"11_CR10","first-page":"2","volume-title":"Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem 1964","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":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-45687-2_12","volume-title":"Mathematical Foundations of Computer Science 2002","author":"O. Carton","year":"2002","unstructured":"Carton, O.: Accessibility in automata on scattered linear orderings. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 155\u2013164. Springer, Heidelberg (2002)"},{"key":"11_CR12","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, Heidelberg (1985)"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Ladner, R.E.: Application of model theoretic games to discrete linear orders and finite automata. Inform. Control\u00a033 (1977)","DOI":"10.1016\/S0019-9958(77)90443-0"},{"key":"11_CR14","volume-title":"Counter free automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter free automata. MIT Press, Cambridge, MA (1971)"},{"issue":"303","key":"11_CR15","first-page":"939","volume":"I","author":"C. Michaux","year":"1986","unstructured":"Michaux, C., Point, F.: Les ensembles k-reconnaissables sont d\u00e9finissables dans <\u2009N,\u2009+\u2009,V k \u2009> (the k-recognizable sets are definable in <\u2009N,\u2009+\u2009,V k \u2009>\u2009). C. R. Acad. Sci. Paris S\u00e9r.\u00a0I (303), 939\u2013942 (1986)","journal-title":"C. R. Acad. Sci. Paris S\u00e9r."},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","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: Perrin, D., Nivat, M. (eds.) Automata on Infinite Words. LNCS, vol.\u00a0192, pp. 2\u201317. Springer, Heidelberg (1984)"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BFb0030294","volume-title":"Mathematical Foundations of Computer Science 1984","author":"D. Perrin","year":"1984","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 134\u2013148. Springer, Heidelberg (1984)"},{"key":"11_CR18","doi-asserted-by":"publisher","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. System Sci.\u00a032, 393\u2013406 (1986)","journal-title":"J. Comput. System Sci."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","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":"11_CR20","unstructured":"Rispal, C.: Automates sur les ordres lin\u00e9aires: Compl\u00e9mentation. PhD thesis, University of Marne-la-Vall\u00e9e, France (2004)"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/978-3-540-30550-7_32","volume-title":"Developments in Language Theory","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 2004. LNCS, vol.\u00a03340, pp. 381\u2013392. Springer, Heidelberg (2004)"},{"key":"11_CR22","volume-title":"Linear orderings","author":"J.G. Rosenstein","year":"1982","unstructured":"Rosenstein, J.G.: Linear orderings. Academic Press, New York (1982)"},{"key":"11_CR23","doi-asserted-by":"publisher","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. Inform. Control\u00a08, 190\u2013194 (1965)","journal-title":"Inform. Control"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Annals of Mathematics\u00a0102, 379\u2013419 (1975)","journal-title":"Annals of Mathematics"},{"key":"11_CR25","doi-asserted-by":"publisher","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. Inform. Control\u00a042, 148\u2013156 (1979)","journal-title":"Inform. Control"},{"key":"11_CR26","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","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)"},{"key":"11_CR27","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.\u00a0III, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"issue":"3-4","key":"11_CR28","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. Fundamenta informatic\u00e6\u00a08(3-4), 379\u2013396 (1985)","journal-title":"Fundamenta informatic\u00e6"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79709-8_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T13:13:36Z","timestamp":1631279616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79709-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797081","9783540797098"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79709-8_11","relation":{},"subject":[]}}