{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:38:07Z","timestamp":1725489487809},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_15","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"188-200","source":"Crossref","is-referenced-by-count":0,"title":["The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Ly","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"15_CR1","unstructured":"J.R. B\u00fcchi, On a decision method in restricted second order arithmetic. Proc. Internat. Congr. on Logic, Methodology and Philosophy of Science, E. Nagel and al. eds. p1\u201311 (1960)."},{"key":"15_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/3-540-61440-0_128","volume-title":"ICALP\u201996","author":"D. Caucal","year":"1996","unstructured":"D. Caucal, On Infinite Transition Graphs having Decidable Monadic Theory, ICALP\u201996-LNCS 1099:194\u2013205 (1996)."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","volume":"25","author":"B. Courcelle","year":"1983","unstructured":"B. Courcelle, Fundamental Properties of Infinite Trees, TCS 25:95\u2013169 (1983).","journal-title":"TCS"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle, The monadic second-order logic of graphs II: Infinite Graphs of Bounded Width, Math. System Theory 21:187\u2013221 (1989).","journal-title":"Math. System Theory"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","volume":"49","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, The monadic second-order logic of graphs IV: Definability properties of Equational Graphs, Annals of Pure and Applied Logic 49:193\u2013255 (1990).","journal-title":"Annals of Pure and Applied Logic"},{"key":"15_CR6","unstructured":"Ebbinghaus H.-D and Flum J., Finite Model Theory, second edition, Springer Verlag (1999)."},{"key":"15_CR7","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In \u201cComplexity of Computation\u201d, SIAM-AMS Proceedings 43\u201373 (1974)."},{"key":"15_CR8","unstructured":"Y. Gurevich, Monadic Second-Order Theories, in Model Theoretic Logic, Barwise and Ferferman eds. Springer (1985)."},{"key":"15_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/3-540-48340-3_28","volume-title":"MFCS\u201999","author":"D. Janin","year":"1999","unstructured":"D. Janin and G. Lenzi, On the structure of the monadic logic of the binary tree. MFCS\u201999, LNCS 1672:310\u2013320 (1999)."},{"key":"15_CR10","unstructured":"R. Lassaigne and M. de Rougemond, Logique et Complexit\u00e9, Hermes-collection informatique (1996)."},{"key":"15_CR11","unstructured":"O. Ly, On Hierarchy of Graphs, internal report no 1178-97 LaBRI-1997."},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"R. McNaughton, Testing and Generating Infinite Sequences by a Finite Automaton, Inf. Contr. 9:521\u2013530 (1966)","journal-title":"Inf. Contr."},{"issue":"10\/11","key":"15_CR13","first-page":"509","volume":"23","author":"A.W. Mostowski","year":"1987","unstructured":"A.W. Mostowski Hierarchies of Weak Monadic Formulas for Two Successors Arithmetic, J. Inf. Process. Cybern. EIK 23 10\/11, 509\u2013515 (1987).","journal-title":"J. Inf. Process. Cybern. EIK"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D.E. Muller","year":"1985","unstructured":"D.E. Muller and P.E. Schupp, The Theory of Ends, Pushdown Automata, and Second-Order Logic, TCS 37: 51\u201375 (1985).","journal-title":"TCS"},{"key":"15_CR15","unstructured":"C.H. Papadimitriou, Computational Complexity, Addison-Wexley Pub. Comp. (1994)."},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0022-0000(86)90037-1","volume":"32","author":"D. Perrin","year":"1986","unstructured":"D. Perrin and J. E. Pin, First-Order Logic and Star-Free Sets, J. Comp. Syst. Sci. 32:393\u2013406 (1986).","journal-title":"J. Comp. Syst. Sci."},{"key":"15_CR17","first-page":"343","volume":"23","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. Seymour, Some new results onWell-Quasi Ordering of Graphs. Annals of Discrete Math., 23:343\u2013354 (1984).","journal-title":"Annals of Discrete Math"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"M.O. Rabin, Decidability of second order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969).","DOI":"10.2307\/1995086"},{"key":"15_CR19","unstructured":"M.O. Rabin, Weakly Definable Relations and Special Automata"},{"key":"15_CR20","unstructured":"H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, Series in Higher Mathematics (1967)."},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"G. Rozenberg ed., Handbookof Graph Grammars and Computing by Graph Transformation, vol. 1, World Scientific (1997).","DOI":"10.1142\/3303"},{"key":"15_CR22","unstructured":"G. S\u00e9nizergues, D\u00e9finissabilit\u00e9 des graphes context-free, unpublished work."},{"key":"15_CR23","first-page":"16","volume":"28","author":"G. S\u00e9nizergues","year":"1992","unstructured":"G. S\u00e9nizergues, Definability in weakmo nadic second order logic of some infinite Graphs, Dagstuhl seminar on Automata theory: Infinite Computations 28:16\u201316 (1992).","journal-title":"Dagstuhl seminar on Automata theory: Infinite Computations"},{"key":"15_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BFb0036493","volume-title":"A Hierarchie of Sets of Infinite Trees","author":"W. Thomas","year":"1982","unstructured":"W. Thomas, A Hierarchie of Sets of Infinite Trees, LNCS 145:335\u2013342 (1982)."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:17:08Z","timestamp":1556770628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}