{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:59:14Z","timestamp":1761976754741,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_12","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T07:57:26Z","timestamp":1384847846000},"page":"123-136","source":"Crossref","is-referenced-by-count":5,"title":["Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs"],"prefix":"10.1007","author":[{"given":"Mateus","family":"de Oliveira Oliveira","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1006\/jcss.1999.1691","volume":"60","author":"M. Ajtai","year":"2000","unstructured":"Ajtai, M., Fagin, R., Stockmeyer, L.J.: The closure of monadic NP. J. Comput. Syst. Sci.\u00a060(3), 660\u2013716 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"issue":"1","key":"12_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.2307\/1969218","volume":"48","author":"E. Artin","year":"1947","unstructured":"Artin, E.: The theory of braids. Annals of Mathematics\u00a048(1), 101\u2013126 (1947)","journal-title":"Annals of Mathematics"},{"issue":"2","key":"12_CR4","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J. Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics\u00a022(2), 161\u2013172 (2006)","journal-title":"Graphs and Combinatorics"},{"issue":"2-3","key":"12_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Mathematical Systems Theory\u00a020(2-3), 83\u2013127 (1987)","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"12_CR6","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.jctb.2012.04.004","volume":"102","author":"D. Berwanger","year":"2012","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S., Obdrz\u00e1lek, J.: The DAG-width of directed graphs. J. Comb. Theory, Ser. B\u00a0102(4), 900\u2013923 (2012)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"12_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Berwanger","year":"2005","unstructured":"Berwanger, D., Gr\u00e4del, E.: Entanglement - A measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 209\u2013223. Springer, Heidelberg (2005)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.07.010","volume":"463","author":"D. Berwanger","year":"2012","unstructured":"Berwanger, D., Gr\u00e4del, E., Kaiser, L., Rabinovich, R.: Entanglement and the complexity of directed graphs. Theor. Comput. Sci.\u00a0463, 2\u201325 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"12_CR9","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/0404043","volume":"4","author":"R.B. Borie","year":"1991","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Deterministic decomposition of recursive graph classes. SIAM J. Discrete Math.\u00a04(4), 481\u2013501 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"8-9","key":"12_CR10","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00236-006-0006-z","volume":"42","author":"S. Bozapalidis","year":"2006","unstructured":"Bozapalidis, S., Kalampakas, A.: Recognizability of graph and pattern languages. Acta Inf.\u00a042(8-9), 553\u2013581 (2006)","journal-title":"Acta Inf."},{"issue":"1-3","key":"12_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.tcs.2004.09.040","volume":"332","author":"F.-J. Brandenburg","year":"2005","unstructured":"Brandenburg, F.-J., Skodinis, K.: Finite graph automata for linear and boundary graph languages. Theoretical Computer Science\u00a0332(1-3), 199\u2013232 (2005)","journal-title":"Theoretical Computer Science"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"B. Courcelle","year":"1987","unstructured":"Courcelle, B.: Graph expressions and graph rewritings. Math. Syst. Theory\u00a020, 83\u2013127 (1987)","journal-title":"Math. Syst. Theory"},{"doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, pp. 194\u2013242 (1990)","key":"12_CR13","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol.\u00a0138. Cambridge University Press (2012)","key":"12_CR14","DOI":"10.1017\/CBO9780511977619"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Th. of Comp. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Th. of Comp. Syst."},{"issue":"1-2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"12_CR17","doi-asserted-by":"crossref","first-page":"263","DOI":"10.3233\/FI-2010-367","volume":"105","author":"M. Oliveira Oliveira de","year":"2010","unstructured":"de Oliveira Oliveira, M.: Hasse diagram generators and Petri nets. Fundam. Inform.\u00a0105(3), 263\u2013289 (2010)","journal-title":"Fundam. Inform."},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-642-28332-1_38","volume-title":"Language and Automata Theory and Applications","author":"M. Oliveira Oliveira de","year":"2012","unstructured":"de Oliveira Oliveira, M.: Canonizable partial order generators. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 445\u2013457. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"de Oliveira Oliveira, M.: Subgraphs satisfying MSO properties on z-topologically orderable digraphs. Preprint (full version of this paper) arXiv:1303.4443 (2013)","key":"12_CR19","DOI":"10.1007\/978-3-319-03898-8_12"},{"unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)","key":"12_CR20"},{"issue":"4","key":"12_CR21","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L.C. Eggan","year":"1963","unstructured":"Eggan, L.C.: Transition graphs and the star height of regular events. Michigan Mathematical Journal\u00a010(4), 385\u2013397 (1963)","journal-title":"Michigan Mathematical Journal"},{"issue":"10","key":"12_CR22","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1007\/s002360050106","volume":"34","author":"J. Engelfriet","year":"1997","unstructured":"Engelfriet, J., Vereijken, J.J.: Context-free graph grammars and concatenation of graphs. Acta Informatica\u00a034(10), 773\u2013803 (1997)","journal-title":"Acta Informatica"},{"unstructured":"Evans, W., Hunter, P., Safari, M.: D-width and cops and robbers. Manuscript (2007)","key":"12_CR23"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-11269-0_15","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., Rossmanith, P.: On digraph width measures in parameterized algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 185\u2013197. Springer, Heidelberg (2009)"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-17493-3_14","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Meister, D., Obdr\u017e\u00e1lek, J., Rossmanith, P., Sikdar, S.: Are there any good digraph width measures? In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 135\u2013146. Springer, Heidelberg (2010)"},{"unstructured":"Ganian, R., Hlinen\u00fd, P., Langer, A., Obdrz\u00e1lek, J., Rossmanith, P., Sikdar, S.: Lower bounds on the complexity of MSO1 model-checking. In: STACS 2012, vol.\u00a014, pp. 326\u2013337 (2012)","key":"12_CR26"},{"issue":"2-3","key":"12_CR27","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1142\/S021800149200014X","volume":"6","author":"D. Giammarresi","year":"1992","unstructured":"Giammarresi, D., Restivo, A.: Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence\u00a06(2-3), 241\u2013256 (1992)","journal-title":"International Journal Pattern Recognition and Artificial Intelligence"},{"issue":"3","key":"12_CR28","doi-asserted-by":"crossref","first-page":"399","DOI":"10.3233\/FI-1996-253411","volume":"25","author":"D. Giammarresi","year":"1996","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional finite state recognizability. Fundam. Inform.\u00a025(3), 399\u2013422 (1996)","journal-title":"Fundam. Inform."},{"unstructured":"Gruber, H.: On the d-width of directed graphs. Manuscript (2007)","key":"12_CR29"},{"issue":"2","key":"12_CR30","first-page":"189","volume":"14","author":"H. Gruber","year":"2012","unstructured":"Gruber, H.: Digraph complexity measures and applications in formal language theory. Discrete Math. & Theor. Computer Science\u00a014(2), 189\u2013204 (2012)","journal-title":"Discrete Math. & Theor. Computer Science"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-70583-3_4","volume-title":"Automata, Languages and Programming","author":"H. Gruber","year":"2008","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 39\u201350. Springer, Heidelberg (2008)"},{"issue":"3","key":"12_CR32","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P. Hunter","year":"2008","unstructured":"Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci.\u00a0399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"12_CR33","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B\u00a082(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"doi-asserted-by":"crossref","unstructured":"Kreutzer, S.: On the parameterized intractability of monadic second-order logic. Logical Methods in Computer Science\u00a08(1) (2012)","key":"12_CR34","DOI":"10.2168\/LMCS-8(1:27)2012"},{"doi-asserted-by":"crossref","unstructured":"Kreutzer, S., Tazari, S.: Lower bounds for the complexity of monadic second-order logic. In: LICS, pp. 189\u2013198 (2010)","key":"12_CR35","DOI":"10.1109\/LICS.2010.39"},{"issue":"1","key":"12_CR36","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.disopt.2010.03.010","volume":"8","author":"M. Lampis","year":"2011","unstructured":"Lampis, M., Kaouri, G., Mitsou, V.: On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization\u00a08(1), 129\u2013138 (2011)","journal-title":"Discrete Optimization"},{"doi-asserted-by":"crossref","unstructured":"Matz, O., Thomas, W.: The monadic quantifier alternation hierarchy over graphs is infinite. In: LICS, pp. 236\u2013244 (1997)","key":"12_CR37","DOI":"10.1109\/LICS.1997.614951"},{"key":"12_CR38","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"E.L. Post","year":"1946","unstructured":"Post, E.L.: A variant of a recursively unsolvable problem. Bulletion of the American Mathematical Society\u00a052, 264\u2013268 (1946)","journal-title":"Bulletion of the American Mathematical Society"},{"key":"12_CR39","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S1571-0653(05)80061-7","volume":"3","author":"B.A. Reed","year":"1999","unstructured":"Reed, B.A.: Introducing directed tree width. Electronic Notes in Discrete Mathematics\u00a03, 222\u2013229 (1999)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"12_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/11549345_64","volume-title":"Mathematical Foundations of Computer Science 2005","author":"M.A. Safari","year":"2005","unstructured":"Safari, M.A.: D-width: A more natural measure for directed tree width. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 745\u2013756. Springer, Heidelberg (2005)"},{"key":"12_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-39658-1_44","volume-title":"Algorithms - ESA 2003","author":"A. Slivkins","year":"2003","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 482\u2013493. Springer, Heidelberg (2003)"},{"key":"12_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-25870-1_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Tamaki","year":"2011","unstructured":"Tamaki, H.: A polynomial time algorithm for bounded directed pathwidth. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 331\u2013342. Springer, Heidelberg (2011)"},{"key":"12_CR43","first-page":"147","volume":"172","author":"W. Thomas","year":"1992","unstructured":"Thomas, W.: Finite-state recognizability of graph properties. Theorie des Automates et Applications\u00a0172, 147\u2013159 (1992)","journal-title":"Theorie des Automates et Applications"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T21:17:05Z","timestamp":1746047825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}