{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T06:09:24Z","timestamp":1768284564768,"version":"3.49.0"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T00:00:00Z","timestamp":1236124800000},"content-version":"unspecified","delay-in-days":5298,"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,9]]},"abstract":"<jats:p>In this article, we indicate how the category theoretical approach to tree automata, due to Betti and Kasangian, can be fruitfully combined with Walters\u2019 categorical approach to context-free grammars to provide a simple way of establishing the well-known correspondence between context-free languages and the behaviors of non-deterministic tree automata. The connecting link between the two notions is provided by the theory of relational presheaves.<\/jats:p>","DOI":"10.1017\/s0960129500000487","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T09:00:39Z","timestamp":1236157239000},"page":"287-293","source":"Crossref","is-referenced-by-count":2,"title":["A categorical look at tree automata and context-free languages"],"prefix":"10.1017","volume":"4","author":[{"given":"Kimmo I.","family":"Rosenthal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"S0960129500000487_ref003","volume-title":"Tree Automata","author":"Gecseg","year":"1986"},{"key":"S0960129500000487_ref005","first-page":"137","article-title":"Decompositions of automata and enriched category theory","volume":"XXVII","author":"Kasangian","year":"1986","journal-title":"Cah. de Top. et G\u00e9om. Diff. Cat"},{"key":"S0960129500000487_ref001","first-page":"243","article-title":"Cauchy completion and the associated sheaf","volume":"XXIII","author":"Betti","year":"1982","journal-title":"Cah. de Top. et G\u00e9om. Diff"},{"key":"S0960129500000487_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360303"},{"key":"S0960129500000487_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(92)90085-T"},{"key":"S0960129500000487_ref002","first-page":"71","article-title":"Tree automata and enriched category theory","volume":"17","author":"Betti","year":"1985","journal-title":"Rend. Istit. Mat. Univ. Trieste"},{"key":"S0960129500000487_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90151-5"},{"key":"S0960129500000487_ref006","first-page":"217","volume-title":"Cont. Math","author":"Lambek","year":"1989"},{"key":"S0960129500000487_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90152-7"},{"key":"S0960129500000487_ref013","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511608872","volume-title":"Category Theory and Computer Science","author":"Walters","year":"1992"},{"key":"S0960129500000487_ref010","unstructured":"Rosenthal K. I. (1993) The Theory of Quantaloids (manuscript)."},{"key":"S0960129500000487_ref007","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.50.5.869"},{"key":"S0960129500000487_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(91)90130-T"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500000487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T02:48:10Z","timestamp":1557888490000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500000487\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["S0960129500000487"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500000487","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}