{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T19:55:29Z","timestamp":1758398129384,"version":"3.40.5"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_3","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"47-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hankel Matrices: From Words to Graphs (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Johann A.","family":"Makowsky","sequence":"first","affiliation":[]},{"given":"Nadia","family":"Labai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer (1998)","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Butkovi\u010d, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer (2010)","DOI":"10.1007\/978-1-84996-299-5"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0022-0000(71)80005-3","volume":"5","author":"JW Carlyle","year":"1971","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. J. Comp. Syst. Sc. 5, 26\u201340 (1971)","journal-title":"J. Comp. Syst. Sc."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-order Logic, a Language Theoretic Approach. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511977619"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/10692760_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Courcelle","year":"1998","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) WG 1998. LNCS, vol. 1517, pp. 1\u201316. Springer, Heidelberg (1998)"},{"issue":"2","key":"3_CR6","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. Theory of Computing Systems 33(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"1\u20132","key":"3_CR7","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 108(1\u20132), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Cuninghame-Green, R.A., Butkovi\u010d, P.: Bases in max-algebra. Linear Algebra and its Applications 389, 107\u2013120 (2004)","DOI":"10.1016\/j.laa.2004.03.022"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.F., Parametrized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1\u20132","key":"3_CR10","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","volume":"380","author":"M Droste","year":"2007","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1\u20132), 69\u201386 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR11","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Proving NP-hardness for clique width i: Non-approximability of linear clique-width. Electronic Colloquium on Computational Complexity (2005)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Fischer, E., Kotek, T., Makowsky, J.A.: Application of logic to combinatorial sequences and their recurrence relations. In: Grohe, M., Makowsky, J.A. (eds), Model Theoretic Methods in Finite Combinatorics, vol. 558. Contemporary Mathematics, pp. 1\u201342. American Mathematical Society (2011)","DOI":"10.1090\/conm\/558\/11047"},{"key":"3_CR13","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer (2006)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Freedman, M., Lov\u00e1sz, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphisms of graphs. Journal of AMS 20, 37\u201351 (2007)","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"3_CR15","unstructured":"Glikson, A., Verification of generally intractable graph properties on graphs generated by graph grammars. Master\u2019s thesis, Technion - Israel Institute of Technology, Haifa, Israel (2004)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-39890-5_21","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Glikson","year":"2003","unstructured":"Glikson, A., Makowsky, J.A.: NCE Graph Grammars and Clique-Width. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 237\u2013248. Springer, Heidelberg (2003)"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1093\/logcom\/exq006","volume":"22","author":"B Godlin","year":"2012","unstructured":"Godlin, B., Katz, E., Makowsky, J.A.: Graph polynomials: From recursive definitions to subset expansion formulas. Journal of Logic and Computation 22(2), 237\u2013265 (2012)","journal-title":"Journal of Logic and Computation"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-540-92248-3_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Godlin","year":"2008","unstructured":"Godlin, B., Kotek, T., Makowsky, J.A.: Evaluations of Graph Polynomials. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 183\u2013194. Springer, Heidelberg (2008)"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Guterman, A.E.: Matrix invariants over semirings. In: Hazewinkel, M. (ed.) Handbook of Algebra, vol. 6. Handbook of Algebra, pp. 3\u201333. North-Holland (2009)","DOI":"10.1016\/S1570-7954(08)00201-5"},{"issue":"3","key":"3_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"key":"3_CR21","unstructured":"Jacob, G.: Repr\u00e9sentations et substitutions matricielles dans la th\u00e9orie alg\u00e9brique des transductions. PhD thesis, Universit\u00e9 de Paris, VII (1975)"},{"key":"3_CR22","unstructured":"Kotek, T.: Definability of combinatorial functions. PhD thesis, Technion - Israel Institute of Technology, Haifa, Israel (March 2012)"},{"key":"3_CR23","unstructured":"Kotek, T., Makowsky, J.A.: Connection matrices and the definability of graph parameters. CSL 2012, pp. 411\u2013425 (2012)"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Kotek, T., Makowsky, J.A.: Connection matrices and the definability of graph parameters. Logical Methods in Computer Science 10(4) (2014)","DOI":"10.2168\/LMCS-10(4:1)2014"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Kotek, T., Makowsky, J.A., Ravve, E.V.: A computational framework for the study of partition functions and graph polynomials (abstract). In: Negru, V., et al. (eds) SYNASC 2012, Proceedings of the International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC, Timisoara, Romania, page in press. IEEE Computer Society (2013)","DOI":"10.1109\/SYNASC.2012.36"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Kotek, T., Makowsky, J.A., Zilber, B.: On counting generalized colorings. In: Grohe, M., Makowsky, J.A. (eds) Model Theoretic Methods in Finite Combinatorics, vol. 558. Contemporary Mathematics, pp. 207\u2013242. American Mathematical Society (2011)","DOI":"10.1090\/conm\/558\/11052"},{"key":"3_CR27","unstructured":"Labai, N.: Hankel matrices and definability of graph parameters. Master\u2019s thesis, Technion - Israel Institute of Technology, Haifa, Israel (2015)"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Labai, N., Makowsky, J.A.: Weighted automata and monadic second order logic. In: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2013, Borca di Cadore, Dolomites, Italy, August 29-31, pp. 122\u2013135 (2013)","DOI":"10.4204\/EPTCS.119.12"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Labai, N., Makowsky, J.A.: Weighted automata and monadic second order logic. arXiv preprint arXiv:1307.4472 (2013)","DOI":"10.4204\/EPTCS.119.12"},{"key":"3_CR30","unstructured":"Labai, N., Makowsky, J.A.: Finiteness conditions for graph algebras over tropical semirings. arXiv preprint arXiv:1405.2547 (2014)"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"Labai, N., Makowsky, J.A.: Tropical graph parameters. In: 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings, pp. 357\u2013368 (2014)","DOI":"10.46298\/dmtcs.2406"},{"key":"3_CR32","unstructured":"Labai, N., Makowsky, J.A.: to be determined. (in preparation, 2015)"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Connection matrics. In: Grimmet, G., McDiarmid, C. (eds) Combinatorics, Complexity and Chance, A Tribute to Dominic Welsh, pp. 179\u2013190. Oxford University Press (2007)","DOI":"10.1093\/acprof:oso\/9780198571278.003.0012"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Large Networks and Graph Limits, vol. 60. Colloquium Publications. AMS (2012)","DOI":"10.1090\/coll\/060"},{"issue":"1-3","key":"3_CR35","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"JA Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic 126(1-3), 159\u2013213 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Makowsky, J.A., Kotek, T., Ravve, E.V.: A computational framework for the study of partition functions and graph polynomials. In: Proceedings of the 12th Asian Logic Conference 2011, pp. 210\u2013230. World Scientific (2013)","DOI":"10.1142\/9789814449274_0012"},{"key":"3_CR37","volume-title":"Recursive functions","author":"R P\u00e9ter","year":"1967","unstructured":"P\u00e9ter, R., F\u00f6ldes, I.: Recursive functions. Academic Press, New York (1967)"},{"key":"3_CR38","volume-title":"Subrecursion: functions and hierarchies","author":"HE Rose","year":"1984","unstructured":"Rose, H.E.: Subrecursion: functions and hierarchies. Clarendon Press, Oxford (1984)"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1305\/ndjfl\/1093957149","volume":"3","author":"T Skolem","year":"1963","unstructured":"Skolem, T.: Proof of some theorems on recursively enumerable sets. Notre Dame J. Formal Logic 3, 65\u201374 (1963)","journal-title":"Notre Dame J. Formal Logic"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:57:30Z","timestamp":1747691850000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}