{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T14:21:14Z","timestamp":1726323674953},"reference-count":41,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[1994,10,1]],"date-time":"1994-10-01T00:00:00Z","timestamp":780969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6864,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1994,10]]},"DOI":"10.1016\/0166-218x(94)90019-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:43:01Z","timestamp":1027654981000},"page":"117-149","source":"Crossref","is-referenced-by-count":83,"title":["The monadic second order logic of graphs VI: on several representations of graphs by relational structures"],"prefix":"10.1016","volume":"54","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(94)90019-1_BIB1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","article-title":"Reachability is harder for directed than for undirected finite graphs","volume":"55","author":"Ajtai","year":"1990","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0166-218X(94)90019-1_BIB2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","article-title":"Easy problems easy for tree-decomposable graphs","volume":"12","author":"Arnborg","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(94)90019-1_BIB3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90292-P","article-title":"Forbidden minors characterization of partial 3-trees","volume":"80","author":"Arnborg","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(94)90019-1_BIB4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","article-title":"Graph expressions and graphs rewritings","volume":"20","author":"Bauderon","year":"1987","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0166-218X(94)90019-1_BIB5","series-title":"External Graph Theory","author":"Bollobas","year":"1978"},{"key":"10.1016\/0166-218X(94)90019-1_BIB6","first-page":"227","article-title":"On polynomial time graph grammars","volume":"294","author":"Brandenburg","year":"1988"},{"key":"10.1016\/0166-218X(94)90019-1_BIB7","doi-asserted-by":"crossref","unstructured":"R. Cori and E. Sopena, Some combinatorial aspects of time-stamp systems, European J. Combin., to appear.","DOI":"10.1006\/eujc.1993.1013"},{"key":"10.1016\/0166-218X(94)90019-1_BIB8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","article-title":"An axiomatic definition of context-free rewriting and its application to NLC graph grammars","volume":"55","author":"Courcelle","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(94)90019-1_BIB9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs I: Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inform. and Comput."},{"key":"10.1016\/0166-218X(94)90019-1_BIB10","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","article-title":"The monadic second-order logic of graphs III: Tree-decompositions, minors, and complexity issues","volume":"26","author":"Courcelle","year":"1992","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"10.1016\/0166-218X(94)90019-1_BIB11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0304-3975(91)90387-H","article-title":"The monadic second-order logic of graphs V: On closing the gap between definability and recognizability","volume":"80","author":"Courcelle","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(94)90019-1_BIB12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(92)90148-9","article-title":"The monadic second-order logic of graphs VII: Graphs as relational structures","volume":"101","author":"Courcelle","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(94)90019-1_BIB13","article-title":"The monadic second-order logic of graphs VIII: Orientations","author":"Courcelle","year":"1992","journal-title":"Research Report 92-69"},{"key":"10.1016\/0166-218X(94)90019-1_BIB14","first-page":"124","article-title":"Monadic second-order definable graph transductions","volume":"581","author":"Courcelle","year":"1992"},{"key":"10.1016\/0166-218X(94)90019-1_BIB15","first-page":"193","article-title":"Graph rewriting: An algebraic and logic approach","volume":"Vol. B","author":"Courcelle","year":"1990"},{"key":"10.1016\/0166-218X(94)90019-1_BIB16","article-title":"A logical characterization of hypergraph languages defined by hyperedge replacement grammars","author":"Courcelle","year":"1991","journal-title":"Research Report 91-44"},{"key":"10.1016\/0166-218X(94)90019-1_BIB17","first-page":"253","article-title":"Handle-rewriting hypergraph grammars","volume":"532","author":"Courcelle","year":"1991"},{"key":"10.1016\/0166-218X(94)90019-1_BIB18","first-page":"148","article-title":"Context-free NCE graph grammars","volume":"380","author":"Engelfriet","year":"1989"},{"key":"10.1016\/0166-218X(94)90019-1_BIB19","first-page":"253","article-title":"A characterization of context-free NCE graph languages by monadic second-order logic on trees","volume":"532","author":"Engelfriet","year":"1991"},{"key":"10.1016\/0166-218X(94)90019-1_BIB20","unstructured":"J. Engelfriet and L. Heyker, Context-free hypergraph languages of bounded degree, in preparation."},{"key":"10.1016\/0166-218X(94)90019-1_BIB21","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0890-5401(90)90038-J","article-title":"A comparison of boundary graph grammars and context-free hypergraph grammars","volume":"84","author":"Engelfriet","year":"1990","journal-title":"Inform. and Comput."},{"key":"10.1016\/0166-218X(94)90019-1_BIB22","first-page":"43","article-title":"Generalized first-order spectra and polynomial time recognizable sets","volume":"7","author":"Fagin","year":"1974"},{"key":"10.1016\/0166-218X(94)90019-1_BIB23","series-title":"Logic Colloquium (Herbrand Symposium)","first-page":"105","article-title":"Local and non-local properties","author":"Gaifman","year":"1981"},{"key":"10.1016\/0166-218X(94)90019-1_BIB24","first-page":"15","article-title":"May we introduce to you: hyperedge replacement","volume":"291","author":"Habel","year":"1987"},{"key":"10.1016\/0166-218X(94)90019-1_BIB25","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages that capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90019-1_BIB26","first-page":"371","article-title":"Bounded time-stamps","author":"Israeli","year":"1987","journal-title":"Proceedings of the 28th IEEE Symposium on Foundations of Computer Science"},{"key":"10.1016\/0166-218X(94)90019-1_BIB27","first-page":"1073","article-title":"Elements of relational data base theory","volume":"101","author":"Kannellakis","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0166-218X(94)90019-1_BIB28","first-page":"532","article-title":"Finding minimal forbidden minors using a finite congruence","volume":"510","author":"Lagergren","year":"1991"},{"key":"10.1016\/0166-218X(94)90019-1_BIB29","first-page":"362","article-title":"Efficient algorithms on context-free graph languages","volume":"317","author":"Lautemann","year":"1988"},{"key":"10.1016\/0166-218X(94)90019-1_BIB30","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01364272","article-title":"Homomorphieeigenschaften und mittlere Kanten-dichte von Graphen","volume":"174","author":"Mader","year":"1967","journal-title":"Math. Ann."},{"key":"10.1016\/0166-218X(94)90019-1_BIB31","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","article-title":"Decomposition of finite graphs into forests","volume":"39","author":"Nash-Williams","year":"1964","journal-title":"J. London Math. Soc."},{"key":"10.1016\/0166-218X(94)90019-1_BIB32","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/0210028","article-title":"Recursive graphs, recursive labellings and shortest paths","volume":"10","author":"Proskurowski","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90019-1_BIB33","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0166-218X(94)90019-1_BIB34","series-title":"Handbook of Mathematical Logic","first-page":"595","article-title":"Decidable theories","author":"Rabin","year":"1977"},{"key":"10.1016\/0166-218X(94)90019-1_BIB35","author":"Raspaud","year":"1991","journal-title":"Good and semistrong colorings of oriented planar graphs"},{"key":"10.1016\/0166-218X(94)90019-1_BIB36","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0095-8956(90)90120-O","article-title":"Graph minors IV: tree width and well-quasi-ordering","volume":"48","author":"Robertson","year":"1990","journal-title":"J. Combin. Theory Ser. B."},{"key":"10.1016\/0166-218X(94)90019-1_BIB37","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","article-title":"Boundary NLC grammars, Basic definitions normal forms and complexity","volume":"69","author":"Rozenberg","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/0166-218X(94)90019-1_BIB38","doi-asserted-by":"crossref","DOI":"10.1016\/0168-0072(91)90054-P","article-title":"The structure of the models of decidable monadic theories of graphs","volume":"53","author":"Seese","year":"1991","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0166-218X(94)90019-1_BIB39","first-page":"676","article-title":"Recognizing edge replacement graph languages in cubic time","volume":"532","author":"Vogler","year":"1991"},{"key":"10.1016\/0166-218X(94)90019-1_BIB40","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01361181","article-title":"Beweis einer Abschwachung der Hadwiger-Vermutung","volume":"153","author":"Wagner","year":"1964","journal-title":"Math. Ann."},{"key":"10.1016\/0166-218X(94)90019-1_BIB41","author":"Zielonka","year":"1990","journal-title":"Time-stamp systems for a fixed set of agents"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X94900191?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X94900191?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T06:29:25Z","timestamp":1555136965000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X94900191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,10]]},"references-count":41,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1994,10]]}},"alternative-id":["0166218X94900191"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(94)90019-1","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1994,10]]}}}