{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T12:56:45Z","timestamp":1783256205678,"version":"3.54.6"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,9,13]],"date-time":"2013-09-13T00:00:00Z","timestamp":1379030400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this article, we provide three coalgebraic characterizations of the class\nof context-free languages, each based on the idea of adding coalgebraic\nstructure to an existing algebraic structure by specifying output-derivative\npairs. Final coalgebra semantics then gives an interpretation function into the\nfinal coalgebra of all languages with the usual output and derivative\noperations. The first characterization is based on systems, where each\nderivative is given as a finite language over the set of nonterminals; the\nsecond characterization on systems where derivatives are given as elements of a\nterm-algebra; and the third characterization is based on adding coalgebraic\nstructure to a class of closed (unique) fixed point expressions. We prove\nequivalences between these characterizations, discuss the generalization from\nlanguages to formal power series, as well as the relationship to the\ngeneralized powerset construction.<\/jats:p>","DOI":"10.2168\/lmcs-9(3:14)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:44:29Z","timestamp":1385732669000},"source":"Crossref","is-referenced-by-count":11,"title":["Coalgebraic Characterizations of Context-Free Languages"],"prefix":"10.46298","volume":"Volume 9, Issue 3","author":[{"given":"Joost","family":"Winter","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan J. M.","family":"Rutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3746-3618","authenticated-orcid":false,"given":"Marcello M.","family":"Bonsangue","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2013,9,13]]},"reference":[{"key":"735:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/739\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/739\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:54:51Z","timestamp":1681242891000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,13]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(3:14)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1308.1228","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1308.1228","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/978-3-662-44602-7_21","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,13]]},"article-number":"739"}}