{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:49:36Z","timestamp":1648900176092},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T00:00:00Z","timestamp":1236124800000},"content-version":"unspecified","delay-in-days":5482,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:p>The notion of a <jats:italic>recognizable set<\/jats:italic> of words, trees or graphs is relative to an algebraic structure on the set of words, trees or graphs respectively. We establish that several algebraic structures yield the same notion of a <jats:italic>recognizable set of graphs<\/jats:italic>. This notion is equivalent to that of a <jats:italic>fully cutset-regular set of graphs<\/jats:italic> introduced by Fellows and Abrahamson. We also establish that the class of recognizable sets of graphs is closed under the operations considered in these various equivalent definitions. This fact is not a standard consequence of the definition of recognizability.<\/jats:p>","DOI":"10.1017\/s0960129500000359","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T09:01:18Z","timestamp":1236157278000},"page":"1-32","source":"Crossref","is-referenced-by-count":15,"title":["Recognizable sets of graphs: equivalent definitions and closure properties"],"prefix":"10.1017","volume":"4","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"S0960129500000359_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90353-1"},{"key":"S0960129500000359_ref025","first-page":"675","volume-title":"Handbook of Theoretical Computer Science, Volume B","author":"Wirsing","year":"1990"},{"key":"S0960129500000359_ref008","first-page":"93","volume-title":"Resolution of equations in Algebraic Structures, Vol. 1","author":"Courcelle","year":"1989"},{"key":"S0960129500000359_ref017","volume-title":"Automata, languages and machines, Vol. A","author":"Eilenberg","year":"1974"},{"key":"S0960129500000359_ref019","volume-title":"Tree automata","author":"Gegsec"},{"key":"S0960129500000359_ref010","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B","author":"Courcelle","year":"1990"},{"key":"S0960129500000359_ref015","unstructured":"Courcelle B. and Lagergren J. (1992). Recognizable sets of graphs of bounded tree-width. Report 92\u201368, Bordeaux-1 University. (Springer-Verlag Lecture Notes in Computer Science, to appear)."},{"key":"S0960129500000359_ref022","doi-asserted-by":"crossref","unstructured":"Lengauer T. and Wanke E. (1988) Efficient analysis of graph properties on context-free graph languages, Proceedings ICALP '88. Springer-Verlag Lecture Notes in Computer Science 317 379\u2013393.","DOI":"10.1007\/3-540-19488-6_129"},{"key":"S0960129500000359_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90050-2"},{"key":"S0960129500000359_ref013","first-page":"565","volume-title":"Contemporary Mathematics","volume":"147","author":"Courcelle","year":"1993"},{"key":"S0960129500000359_ref009","first-page":"12","volume-title":"Information and Computation","volume":"85","author":"Courcelle","year":"1990"},{"key":"S0960129500000359_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90148-9"},{"key":"S0960129500000359_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90102-2"},{"key":"S0960129500000359_ref002","doi-asserted-by":"crossref","unstructured":"Arnborg S. , Courcelle B. , Proskurowski A. and Seese D. (1991a) An algebraic theory of graph reduction. Report 91\u201336, Bordeaux-1 University. (Short version in Springer- Verlag Lecture Notes in Computer Science 532 70\u201383; full paper to appear in J. ACM.)","DOI":"10.1007\/BFb0017382"},{"key":"S0960129500000359_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90387-H"},{"key":"S0960129500000359_ref020","article-title":"Hyperedge replacement: grammar and languages","volume":"643","author":"Habel","year":"1992","journal-title":"Springer-Verlag Lecture Notes In Computer Science"},{"key":"S0960129500000359_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"S0960129500000359_ref004","first-page":"159","volume-title":"Tree automata and languages","author":"Arnold","year":"1992"},{"key":"S0960129500000359_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/147\/01199"},{"key":"S0960129500000359_ref024","volume-title":"Universal algebra for computer scientists","author":"Wechler","year":"1991"},{"key":"S0960129500000359_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69962-7"},{"key":"S0960129500000359_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"S0960129500000359_ref018","volume-title":"Proceedings of the Graph Minors Conference","author":"Fellows","year":"1993"},{"key":"S0960129500000359_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90354-V"},{"key":"S0960129500000359_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692060"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500000359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:03:28Z","timestamp":1557947008000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500000359\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["S0960129500000359"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500000359","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}