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
2023 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541Article in journal (Refereed) Epub ahead of print
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, 2023.
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: 2023-12-18

Open Access in DiVA

No full text in DiVA

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 46 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