{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:26:14Z","timestamp":1747189574399,"version":"3.40.5"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>Order-preserving DAG grammars (OPDGs) is a formalism for representing languages of structurally restricted graphs. As demonstrated in [17], they are sufficiently expressive to model abstract meaning representations in natural language processing, a graph-based form of semantic representation in which nodes encode objects and edges relations. At the same time, they can be parsed in [Formula: see text], where [Formula: see text] and [Formula: see text] are the sizes of the grammar and the input graph, respectively. In this work, we provide an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars under an equivalence theory. This makes it possible to transfer results from the field of formal tree languages to the domain of OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable under the \u201cminimal adequeate teacher\u201d paradigm, that is, by querying an oracle for equivalence between languages, and membership of individual graphs. To conclude, we demonstrate that the languages generated by OPDGs are definable in monadic second-order logic.<\/jats:p>","DOI":"10.1142\/s0129054123480106","type":"journal-article","created":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T08:55:33Z","timestamp":1701075333000},"page":"215-243","source":"Crossref","is-referenced-by-count":2,"title":["Tree-Based Generation of Restricted Graph Languages"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4696-9787","authenticated-orcid":false,"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0596-627X","authenticated-orcid":false,"given":"Johanna","family":"Bj\u00f6rklund","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8722-5661","authenticated-orcid":false,"given":"Petter","family":"Ericson","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Ume\u00e5 University, Sweden"}]}],"member":"219","published-online":{"date-parts":[[2023,11,24]]},"reference":[{"key":"S0129054123480106BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"volume-title":"7th Linguistic Annotation Workshop & Interoperability with Discourse","year":"2013","author":"Banarescu L.","key":"S0129054123480106BIB002"},{"key":"S0129054123480106BIB003","first-page":"94","volume-title":"Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13)","author":"Berglund M.","year":"2017"},{"key":"S0129054123480106BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60134-2_3"},{"key":"S0129054123480106BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_40"},{"key":"S0129054123480106BIB007","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 11th International Conference on Developments in Language Theory (DLT 2007), Turku, Finnland","volume":"4588","author":"Bj\u00f6rklund J.","year":"2007"},{"key":"S0129054123480106BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_33"},{"key":"S0129054123480106BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45007-6_11"},{"key":"S0129054123480106BIB010","first-page":"924","volume-title":"51st Annual Meeting of the Association for Computational Linguistics (ACL 2013)","author":"Chiang D.","year":"2013"},{"key":"S0129054123480106BIB011","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00309"},{"volume-title":"A Formal View on Training of Weighted Tree Automata by Likelihood-driven State Splitting and Merging","year":"2004","author":"Dietze T.","key":"S0129054123480106BIB012"},{"key":"S0129054123480106BIB013","doi-asserted-by":"publisher","DOI":"10.1142\/9789812384720_0002"},{"issue":"3","key":"S0129054123480106BIB014","first-page":"332","volume":"12","author":"Drewes F.","year":"2007","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054123480106BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5"},{"key":"S0129054123480106BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90078-G"},{"key":"S0129054123480106BIB018","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W17-3410"},{"key":"S0129054123480106BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75414-5_14"},{"key":"S0129054123480106BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.01.004"},{"key":"S0129054123480106BIB021","first-page":"433","volume-title":"Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics","author":"Petrov S.","year":"2016"},{"key":"S0129054123480106BIB022","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1192.001.0001","volume-title":"Algorithmic Program DeBugging","author":"Shapiro E. Y.","year":"1983"},{"key":"S0129054123480106BIB023","first-page":"455","volume-title":"Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics","volume":"1","author":"Socher R.","year":"2013"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123480106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,3]],"date-time":"2024-11-03T11:53:51Z","timestamp":1730634831000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123480106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,24]]},"references-count":21,"journal-issue":{"issue":"01n02","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.1142\/S0129054123480106"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123480106","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,11,24]]}}}