{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:18Z","timestamp":1742617098834,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_91","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:59:15Z","timestamp":1330203555000},"page":"445-457","source":"Crossref","is-referenced-by-count":2,"title":["Pushdown automata on infinite trees and omega-Kleene closure of context-free tree sets"],"prefix":"10.1007","author":[{"given":"A.","family":"Saoudi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01744297","volume":"13","author":"A. Arnold","year":"1980","unstructured":"A. Arnold and M. Nivat, Formal computations of nondeterministic program schemes, Math. Syst. Theory 13(1980)219\u2013236.","journal-title":"Math. Syst. Theory"},{"key":"39_CR2","unstructured":"J.R. B\u00fcchi, On a decision method in restricted second order arithmetic, Proc. Cong. Logic Method and Philos. of Sci. 1960, Univ. Press, Stanford California."},{"key":"39_CR3","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0022-0000(77)80005-6","volume":"15","author":"R. S. Cohen","year":"1977","unstructured":"R. S. Cohen and A. Y. Gold, Theory of \u03c9-languages II: A study of various models of \u03c9-types generation and recognition, J. Comput. Syst. Sci. 15(1977)185\u2013208.","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0022-0000(78)90019-3","volume":"16","author":"R. S. Cohen","year":"1978","unstructured":"R. S. Cohen and A. Y. Gold, \u03c9-computations of deterministic pushdown machines, J. Comput. Syst. Sci. 16(1978)275\u2013300.","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR5","unstructured":"S. Eilenberg, Automata, Languages, and Machines, Academic Press(1974)."},{"key":"39_CR6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0022-0000(85)90002-9","volume":"30","author":"J. H. Gallier","year":"1985","unstructured":"J. H. Gallier and K. Schimpf, Tree pushdown automata, J. Comput. Syst. Sci. 30(1985)25\u201340.","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR7","unstructured":"F. G\u00e9cseg and M. Steinby, Tree automata, Akademiai Kiado, Budapest (1984)."},{"key":"39_CR8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF01744582","volume":"16","author":"I. Guessarian","year":"1983","unstructured":"I. Guessarian, Pushdown tree automata, Math. Syst. Theory 16(1983) 237\u2013264.","journal-title":"Math. Syst. Theory"},{"key":"39_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-10284-1","volume-title":"Algebraic semantics, Lect. Notes Comp. Sci. no. 99","author":"I. Guessarian","year":"1981","unstructured":"I. Guessarian, Algebraic semantics, Lect. Notes Comp. Sci. no. 99, Springer-Verlag, Berlin (1981)."},{"key":"39_CR10","series-title":"LNCS","first-page":"269","volume-title":"Computation tree logic CTL* and path quantifiers in the theory of the binary tree","author":"T. Hafer","year":"1987","unstructured":"T. Hafer and W. Thomas, Computation tree logic CTL* and path quantifiers in the theory of the binary tree, Proc. 14th ICALP, (T. Ottmann, ed.), LNCS no. 267, Springer-Verlag, Berlin(1987)269\u2013279."},{"key":"39_CR11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.5109\/13369","volume":"21","author":"T. Hayashi","year":"1985","unstructured":"T. Hayashi and S. Miyano, Finite tree automata on infinite trees, Bull. Inform. Cybern. 21(1985)71\u201382.","journal-title":"Bull. Inform. Cybern."},{"key":"39_CR12","volume-title":"Logical formulas and four subclasses of \u03c9-regular languages, in Automata on infinite words","author":"K. Kobayashi","year":"1984","unstructured":"K. Kobayashi, M. Takahashi and H. Yamasaki, Logical formulas and four subclasses of \u03c9-regular languages, in Automata on infinite words, (M. Nivat and D. Perrin eds.), LNCS no. 192, Springer Verlag, Berlin(1984)."},{"key":"39_CR13","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L. H. Landweber","year":"1969","unstructured":"L. H. Landweber, Decision problem for \u03c9-automata, Math. Syst. Theory 3(1969)376\u2013384.","journal-title":"Math. Syst. Theory"},{"key":"39_CR14","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0019-9958(76)90415-0","volume":"31","author":"M. Linna","year":"1976","unstructured":"M. Linna, On \u03c9-sets associated with context-free languages, Inf. and Control 31(1976)272\u2013293.","journal-title":"Inf. and Control"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"D. E. Muller, Infinite sequences and finite machines, Proc. 4th IEEE on Switching Circuit Theory and Logical Design(1963)3\u201316.","DOI":"10.1109\/SWCT.1963.8"},{"key":"39_CR16","series-title":"L.N.C.S","first-page":"275","volume-title":"Alternating automata, the weak monadic theory and its complexity,13th Inter. Colloquium Automata, Languages and Programming","author":"D. Muller","year":"1986","unstructured":"D. Muller, A. Saoudi and P. Schupp, Alternating automata, the weak monadic theory and its complexity,13th Inter. Colloquium Automata, Languages and Programming, (L. Kott, ed.), L.N.C.S no. 226, Springer-Verlag, Berlin(1986)275\u2013283."},{"key":"39_CR17","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0304-3975(87)90085-5","volume":"52","author":"T. Moriya","year":"1987","unstructured":"T. Moriya, Topological characterisations of infinite tree languages, Theoret. Comput. Sci. 52(1987)165\u2013171.","journal-title":"Theoret. Comput. Sci."},{"key":"39_CR18","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. Mc Naughton","year":"1966","unstructured":"R. Mc Naughton, Testing and generating infinite sequences by a finite automata, Inform. and Control 9(1966)521\u2013530.","journal-title":"Inform. and Control"},{"key":"39_CR19","unstructured":"M. Nivat et A. Saoudi, Automata on infinite trees and rational infinite tree sets, Rapport L.I.T.P no. 87\u201359, Univ. Paris VII, Submitted to J. Comput. Syst. Sci."},{"key":"39_CR20","unstructured":"M. Nivat and A. Saoudi, Automata on infinite objects and their applications to logic programming, Univ. Paris VII, report no. 87\u201360(1987), to appear in Inf. and Computation."},{"key":"39_CR21","first-page":"134","volume":"176","author":"D. Perrin","year":"1984","unstructured":"D. Perrin, Recent results on automata and infinite words, Proc. Math. Found. of Comput. Sci. (M. P. Chytil and V. Koubek, eds.), LNCS no. 176(1984)134\u2013148.","journal-title":"Proc. Math. Found. of Comput. Sci."},{"key":"39_CR22","first-page":"1","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"M. O. Rabin, Decidability of second order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141(1969)1\u201335.","journal-title":"Trans. Amer. Math. Soc."},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"M. O. Rabin, Weakly definable relations and special automata, Math. Logic and Foundation of set theory, Y.Bar Hillel, Edit. Amsterdam North Holland (1970)1\u201323.","DOI":"10.1016\/S0049-237X(08)71929-3"},{"key":"39_CR24","first-page":"455","volume":"13","author":"G. Rozenberg","year":"1977","unstructured":"G. Rozenberg, Selective substitution grammars, Part I, Elektron. Inform. Kybernet. 13(1977)455\u2013463.","journal-title":"Elektron. Inform. Kybernet"},{"key":"39_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(86)90183-0","volume":"43","author":"A. Saoudi","year":"1986","unstructured":"A. Saoudi, Vari\u00e9t\u00e9s d'automates descendants d'arbres infinis, Theoret. Comput. Sci. 43(1986)1\u201321.","journal-title":"Theoret. Comput. Sci."},{"key":"39_CR26","unstructured":"A. Saoudi, Generalized automata on infinite trees and Muller-Mc Naughton's theorem, Univ. Paris VII, report no. 88-06(1988)"},{"key":"39_CR27","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0304-3975(86)90123-4","volume":"44","author":"M. Takahashi","year":"1986","unstructured":"M. Takahashi, The greatest fixed points and rational omega-tree languages, Theoret. Comput. Sci. 44(1986)259\u2013274.","journal-title":"Theoret. Comput. Sci."},{"key":"39_CR28","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"J. W. Thatcher and J.B. Wright, Generalized finite automata theory with applications to a decision problem of second order logic, Math. Syst. Theory 2(1968)57\u201381.","journal-title":"Math. Syst. Theory"},{"key":"39_CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0019-9958(81)90663-X","volume":"48","author":"W. Thomas","year":"1981","unstructured":"W. Thomas, A Combinatorial approach to the theory of \u03c9-automata, Inform. and Control 48(1981)261\u2013283.","journal-title":"Inform. and Control"},{"key":"39_CR30","series-title":"L.N.C.S","first-page":"335","volume-title":"A Hierarchy of sets of infinite trees","author":"W. Thomas","year":"1982","unstructured":"W. Thomas, A Hierarchy of sets of infinite trees, G.I Conference, L.N.C.S no. 145, (A. B. Cremers, H. P. Kriegel, eds.), Springer-Verlag, Berlin (1982)335\u2013342."},{"key":"39_CR31","unstructured":"W. Thomas, On chain logic, path logic, and first order logic over infinite trees, Proc. 2nd Symp. on Logic in Computer Sci. (1987)245\u2013256."},{"key":"39_CR32","first-page":"379","volume":"10","author":"K. Wagner","year":"1974","unstructured":"K. Wagner and L. Staiger, Automatatheoretische und Automatenfreie Characterisierugen Topologischer Klasses Regular Folgmmengen, EIK 10(1974)379\u2013392.","journal-title":"EIK"},{"key":"39_CR33","unstructured":"P. Wolper and M. Vardi, Reasoning about Fair Concurrent programs, Proc. 18th Symp. on Theory of Computing, Berkeley(1986)."},{"issue":"4","key":"39_CR34","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0020-0190(82)90097-7","volume":"15","author":"A. W. Mostowski","year":"1982","unstructured":"A. W. Mostowski, Determinancy of Sinking Automata on Infinite trees and Inequalities between various Rabin's Pair Indices, Inform. Proc. Letters, vol. 15, no. 4(1982) 159\u2013163.","journal-title":"Inform. Proc. Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_91.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:54:45Z","timestamp":1742590485000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}