Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Tree-based generation of restricted graph languages
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4696-9787
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0001-8503-0118
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-8722-5661
2024 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 35, nr 1 & 2, s. 215-243Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
World Scientific, 2024. Vol. 35, nr 1 & 2, s. 215-243
Nyckelord [en]
Graph languages, logic characterisation, MAT learning, minimization
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-217981DOI: 10.1142/S0129054123480106ISI: 001109806500001Scopus ID: 2-s2.0-85178101785OAI: oai:DiVA.org:umu-217981DiVA, id: diva2:1819857
Forskningsfinansiär
Vetenskapsrådet, 2020-03852Wallenberg AI, Autonomous Systems and Software Program (WASP), Nest project StingTillgänglig från: 2023-12-15 Skapad: 2023-12-15 Senast uppdaterad: 2024-05-14Bibliografiskt granskad

Open Access i DiVA

fulltext(747 kB)15 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 747 kBChecksumma SHA-512
641c1a1266fab41f003482bd4de9a171fd868ab931ba3b5f2fab1ab0399df86f68cfd93892ece022e861efa8925d12f3f9860ca93ad759052dca593bb818e0a7
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Björklund, HenrikBjörklund, JohannaEricson, Petter

Sök vidare i DiVA

Av författaren/redaktören
Björklund, HenrikBjörklund, JohannaEricson, Petter
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
International Journal of Foundations of Computer Science
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 15 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 82 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf