{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:19Z","timestamp":1759637599760,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540926863"},{"type":"electronic","value":"9783540926870"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92687-0_5","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T04:25:38Z","timestamp":1234239938000},"page":"61-75","source":"Crossref","is-referenced-by-count":2,"title":["Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Bedon","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","series-title":"Series in algebra","volume-title":"Finite semigroups and universal algebra","author":"J. Almeida","year":"1994","unstructured":"Almeida, J.: Finite semigroups and universal algebra. Series in algebra, vol.\u00a03. World Scientific, Singapore (1994)"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-540-79709-8_11","volume-title":"Computer Science \u2013 Theory and Applications","author":"N. Bedon","year":"2008","unstructured":"Bedon, N., B\u00e8s, 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.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 76\u201385. Springer, Heidelberg (2008)"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-74456-6_43","volume-title":"Mathematical Foundations of Computer Science 2007","author":"N. Bedon","year":"2007","unstructured":"Bedon, N., Rispal, C.: Series-parallel languages on scattered and countable posets. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 477\u2013488. Springer, Heidelberg (2007)"},{"issue":"3","key":"5_CR4","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":"5_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-45005-X_9","volume-title":"Developments in Language Theory","author":"V. Bruy\u00e8re","year":"2003","unstructured":"Bruy\u00e8re, V., Carton, O.: Automata on linear orderings. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol.\u00a02450, pp. 103\u2013115. Springer, Heidelberg (2003)"},{"key":"5_CR6","first-page":"1","volume-title":"Proc. Intern. Congr. on Logic, Methodology and Philosophy of Science, Berkeley 1960","author":"J. Richard B\u00fcchi","year":"1962","unstructured":"Richard B\u00fcchi, J.: On a decision method in the restricted second-order arithmetic. In: Proc. Intern. Congr. on Logic, Methodology and Philosophy of Science, Berkeley 1960, pp. 1\u201311. Stanford University Press, Stanford (1962)"},{"key":"5_CR7","first-page":"2","volume-title":"Proc. Int. Congress Logic, Methodology, and Philosophy of Science","author":"J.R. B\u00fcchi","year":"1964","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, pp. 2\u201323. North Holland, Amsterdam (1964)"},{"issue":"4","key":"5_CR8","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1142\/S0129054105003285","volume":"16","author":"O. Carton","year":"2005","unstructured":"Carton, O., Rispal, C.: 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":"5_CR9","series-title":"Springer monographs in mathematics","volume-title":"Finite model theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite model theory, 2nd edn. Springer monographs in mathematics. Springer, Heidelberg (1999)","edition":"2"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-46011-X_18","volume-title":"Developments in Language Theory","author":"Z. \u00c9sik","year":"2002","unstructured":"\u00c9sik, Z., N\u00e9meth, Z.L.: Automata on series-parallel biposets. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 217\u2013227. Springer, Heidelberg (2002)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1007\/3-540-45022-X_55","volume-title":"Automata, Languages and Programming","author":"D. Kuske","year":"2000","unstructured":"Kuske, D.: Infinite series-parallel posets: logic and languages. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 648\u2013662. Springer, Heidelberg (2000)"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0304-3975(02)00370-5","volume":"299","author":"D. Kuske","year":"2003","unstructured":"Kuske, D.: Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci.\u00a0299, 347\u2013386 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.4064\/fm-59-1-109-116","volume":"59","author":"H. La\u00fcchli","year":"1966","unstructured":"La\u00fcchli, H., Leonard, J.: On the elementary theory of linear order. Fund. Math.\u00a059, 109\u2013116 (1966)","journal-title":"Fund. Math."},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BFb0028590","volume-title":"STACS 98","author":"K. Lodaya","year":"1998","unstructured":"Lodaya, K., Weil, P.: Series-parallel posets: algebra, automata and languages. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 555\u2013565. Springer, Heidelberg (1998)"},{"issue":"1\u20132","key":"5_CR15","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0304-3975(00)00031-1","volume":"237","author":"K. Lodaya","year":"2000","unstructured":"Lodaya, K., Weil, P.: Series-parallel languages and the bounded-width property. Theoret. Comput. Sci.\u00a0237(1\u20132), 347\u2013380 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Lodaya, K., Weil, P.: Rationality in algebras with a series operation. Inform. Comput., 269\u2013293 (2001)","DOI":"10.1006\/inco.2001.3077"},{"issue":"303","key":"5_CR17","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\n                \n                  k\n                \u2009> (the k-recognizable sets are definable in <\u2009N,\u2009+\u2009,V\n                \n                  k\n                \u2009>\u2009). C. R. Acad. Sci. Paris, S\u00e9r\u00a0I(303), 939\u2013942 (1986)","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r"},{"key":"5_CR18","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. Amer. Math. Soc.\u00a0141, 1\u201335 (1969)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR19","volume-title":"Linear Orderings","author":"J.G. Rosenstein","year":"1982","unstructured":"Rosenstein, J.G.: Linear Orderings. Academic Press, London (1982)"},{"issue":"3","key":"5_CR20","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(3), 379\u2013419 (1975)","journal-title":"Annals of Mathematics"},{"key":"5_CR21","doi-asserted-by":"publisher","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)"},{"key":"5_CR22","unstructured":"Valdes, J.: Parsing flowcharts and series-parallel graphs. Technical Report STAN-CS-78-682, Computer science departement of the Stanford University, Standford, Ca (1978)"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput.\u00a011, 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1007\/3-540-54233-7_166","volume-title":"Automata, Languages and Programming","author":"T. Wilke","year":"1991","unstructured":"Wilke, T.: An Eilenberg theorem for \u221e-languages. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 588\u2013599. Springer, Heidelberg (1991)"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92687-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:49:52Z","timestamp":1558266592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92687-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540926863","9783540926870"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92687-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}