{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T23:10:07Z","timestamp":1736550607756,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388708"},{"type":"electronic","value":"9783540388722"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841883_5","type":"book-chapter","created":{"date-parts":[[2006,9,19]],"date-time":"2006-09-19T11:29:11Z","timestamp":1158665351000},"page":"46-60","source":"Crossref","is-referenced-by-count":1,"title":["Automata on Directed Graphs: Edge Versus Vertex Marking"],"prefix":"10.1007","author":[{"given":"Dietmar","family":"Berwanger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Janin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed rather than undirected finite graphs. Journal of Symbolic Logic\u00a055, 113\u2013150 (1990)","journal-title":"Journal of Symbolic Logic"},{"key":"5_CR2","series-title":"Studies in Logic and the Foundations of Mathematics","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(01)80001-X","volume-title":"Rudiments of mu-calculus","author":"A. Arnold","year":"2001","unstructured":"Arnold, A., Niwi\u0144ski, D.: Rudiments of mu-calculus. Studies in Logic and the Foundations of Mathematics, vol.\u00a0146. North-Holland, Amsterdam (2001)"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/3-540-57208-2_19","volume-title":"CONCUR\u201993","author":"O. Bernholtz","year":"1993","unstructured":"Bernholtz, O., Grumberg, O.: Branching time temporal logic and amorphous tree automata. In: Best, E. (ed.) CONCUR 1993. LNCS, vol.\u00a0715, pp. 262\u2013277. Springer, Heidelberg (1993)"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second order logic of graph I: Recognizable sets of finite graphs. Inf. and Comp.\u00a085, 12\u201375 (1990)","journal-title":"Inf. and Comp."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B.: The monadic second-order logic of graphs VI: On several representations of graphs by logical structures. Discrete Applied Mathematics\u00a054, 117\u2013149 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.tcs.2005.03.018","volume":"342","author":"B. Courcelle","year":"2005","unstructured":"Courcelle, B., Weil, P.: The recognizability of sets of graphs is a robust property. Theoretical Computer Science\u00a0342, 173\u2013228 (2005)","journal-title":"Theoretical Computer Science"},{"key":"5_CR7","doi-asserted-by":"publisher","DOI":"10.1142\/9789814261456","volume-title":"The Book of Traces","author":"V. Diekert","year":"1995","unstructured":"Diekert, V.: The Book of Traces. World Scientific Publishing Co., Inc., Singapore (1995)"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00166-3","volume":"247","author":"M. Droste","year":"2000","unstructured":"Droste, M., Gastin, P., Kuske, D.: Asynchronous cellular automata for pomsets. Theoretical Computer Science\u00a0247, 1\u201338 (2000)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: IEEE Symp. on Logic in Computer Science (LICS), pp. 368\u2013377 (1991)","key":"5_CR9","DOI":"10.1109\/SFCS.1991.185392"},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-642-59126-6_4","volume-title":"Handbook of Formal Languages","author":"D. Giammaresi","year":"1997","unstructured":"Giammaresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0III, pp. 215\u2013268. Springer, Heidelberg (1997)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.2307\/2273673","volume":"48","author":"Y. Gurevich","year":"1983","unstructured":"Gurevich, Y., Shelah, S.: Rabin\u2019s uniformization problem. J. Symb. Log.\u00a048, 1105\u20131119 (1983)","journal-title":"J. Symb. Log."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/LICS.2001.932510","volume-title":"IEEE Symp. on Logic in Computer Science (LICS)","author":"D. Janin","year":"2001","unstructured":"Janin, D., Lenzi, G.: Relating levels of the mu-calculus hierarchy and levels of the monadic hierarchy. In: IEEE Symp. on Logic in Computer Science (LICS), pp. 347\u2013356. IEEE Computer Society, Los Alamitos (2001)"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Mathematical Foundations of Computer Science 1995","author":"D. Janin","year":"1995","unstructured":"Janin, D., Walukiewicz, I.: Automata for the modal mu-calculus and related results. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969. Springer, Heidelberg (1995)"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/3-540-61604-7_60","volume-title":"CONCUR \u201996: Concurrency Theory","author":"D. Janin","year":"1996","unstructured":"Janin, D., Walukiewicz, I.: On the expressive completeness of the modal mu-calculus with respect to monadic second order logic. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol.\u00a01119, pp. 263\u2013277. Springer, Heidelberg (1996)"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"Kamimura, T., Slutzki, G.: Parallel and two-way automata on directed ordered acyclic graphs. Information and Control\u00a049, 10\u201351 (1981)","journal-title":"Information and Control"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional \u03bc-calculus. Theoretical Comp. Science\u00a027, 333\u2013354 (1983)","journal-title":"Theoretical Comp. Science"},{"key":"5_CR17","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. Theoretical Computer Science\u00a0237, 347\u2013380 (2000)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Matz, O., Thomas, W.: The monadic quantifier alternation hierarchy over finite graphs is infinite. In: IEEE Symp. on Logic in Computer Science (LICS), pp. 236\u2013244 (1997)","key":"5_CR18","DOI":"10.1109\/LICS.1997.614951"},{"key":"5_CR19","first-page":"220","volume":"42","author":"A.A. Muchnik","year":"1992","unstructured":"Muchnik, A.A.: Games on infinite trees and automata with dead-ends: a new proof for the decidability of the monadic second order theory of two successors. Bull. EATCS\u00a042, 220\u2013267 (1992) (traduction d\u2019un article en Russe de 1984)","journal-title":"Bull. EATCS"},{"doi-asserted-by":"crossref","unstructured":"Niwi\u0144ski, D.: Fixed points vs. infinite generation. In: IEEE Symp. on Logic in Computer Science (LICS), pp. 402\u2013409 (1988)","key":"5_CR20","DOI":"10.1109\/LICS.1988.5137"},{"key":"5_CR21","volume-title":"Infinite Words","author":"D. Perrin","year":"2002","unstructured":"Perrin, D., Pin, J.-E.: Infinite Words. Academic Press, London (2002)"},{"key":"5_CR22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.36045\/bbms\/1103408550","volume":"1","author":"A. Potthoff","year":"1994","unstructured":"Potthoff, A., Seibert, S., Thomas, W.: Nondeterminism versus determinism of finite automata over directed acyclic graphs. Bull. Belg. Math. Soc. Simon Stevin\u00a01, 285\u2013298 (1994)","journal-title":"Bull. Belg. Math. Soc. Simon Stevin"},{"key":"5_CR23","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. Trans. Amer. Math. Soc.\u00a0141, 1\u201335 (1969)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second\u2013order logic. Math. Systems Theory\u00a02, 57\u201381 (1968)","journal-title":"Math. Systems Theory"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/3-540-54233-7_154","volume-title":"Automata, Languages and Programming","author":"W. Thomas","year":"1991","unstructured":"Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 441\u2013454. Springer, Heidelberg (1991)"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/BFb0030586","volume-title":"TAPSOFT\u201997: Theory and Practice of Software Development","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Automata theory on trees and partial orders. In: Bidoit, M., Dauchet, M. (eds.) CAAP 1997, FASE 1997, and TAPSOFT 1997. LNCS, vol.\u00a01214, pp. 20\u201338. Springer, Heidelberg (1997)"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0304-3975(01)00229-8","volume":"292","author":"W. Thomas","year":"2003","unstructured":"Thomas, W.: Uniform and nonuniform recognizability. Theor. Comput. Sci.\u00a0292, 299\u2013316 (2003)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Walukiewicz, I.: On the ambiguity problem. Notes non publi\u00e9es (1994)","key":"5_CR28"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(01)00185-2","volume":"275","author":"I. Walukiewicz","year":"2002","unstructured":"Walukiewicz, I.: Monadic second order logic on tree-like structures. Theoretical Comp. Science\u00a0275, 311\u2013346 (2002)","journal-title":"Theoretical Comp. Science"}],"container-title":["Lecture Notes in Computer Science","Graph Transformations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841883_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T22:31:46Z","timestamp":1736548306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841883_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388708","9783540388722"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11841883_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}