Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tree-based generation of restricted graph languages
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4696-9787
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0001-8503-0118
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-8722-5661
2024 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 35, no 1 & 2, p. 215-243Article in journal (Refereed) Published
Abstract [en]

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 O (n2 + nm) , where m and n 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 \minimal adequeate teacher" 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.

Place, publisher, year, edition, pages
World Scientific, 2024. Vol. 35, no 1 & 2, p. 215-243
Keywords [en]
Graph languages, logic characterisation, MAT learning, minimization
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-217981DOI: 10.1142/S0129054123480106ISI: 001109806500001Scopus ID: 2-s2.0-85178101785OAI: oai:DiVA.org:umu-217981DiVA, id: diva2:1819857
Funder
Swedish Research Council, 2020-03852Wallenberg AI, Autonomous Systems and Software Program (WASP), Nest project StingAvailable from: 2023-12-15 Created: 2023-12-15 Last updated: 2024-05-14Bibliographically approved

Open Access in DiVA

fulltext(747 kB)19 downloads
File information
File name FULLTEXT01.pdfFile size 747 kBChecksum SHA-512
641c1a1266fab41f003482bd4de9a171fd868ab931ba3b5f2fab1ab0399df86f68cfd93892ece022e861efa8925d12f3f9860ca93ad759052dca593bb818e0a7
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Björklund, HenrikBjörklund, JohannaEricson, Petter

Search in DiVA

By author/editor
Björklund, HenrikBjörklund, JohannaEricson, Petter
By organisation
Department of Computing Science
In the same journal
International Journal of Foundations of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 19 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 90 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf