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
Minimisation and Characterisation of Order-Preserving DAG Grammars
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-4696-9787
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-8722-5661
2018 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Order-preserving DAG grammars (OPDGs) is a formalism for processing semantic infor- mation in natural languages [5, 4]. OPDGs are sufficiently expressive to model abstract meaning representations, a graph-based form of semantic representation in which nodes en- code objects and edges relations. At the same time, they allow for efficient parsing in the uniform setting, where both the grammar and subject graph are taken as part of the input.

In this article, we introduce an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars. This makes it possible to transfer a number of results from that domain to 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 in the so-called MAT setting. To conclude, we show that the languages generated by OPDGs are MSO-definable.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University , 2018. , s. 19
Serie
Report / UMINF, ISSN 0348-0542 ; 18.15
Nyckelord [en]
graph grammars, minimally adequate teacher, order preservation, weighted graph grammars, weighted learning
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
administrativ databehandling
Identifikatorer
URN: urn:nbn:se:umu:diva-153394OAI: oai:DiVA.org:umu-153394DiVA, id: diva2:1264053
Tillgänglig från: 2018-11-19 Skapad: 2018-11-19 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
Ingår i avhandling
1. Order-preserving graph grammars
Öppna denna publikation i ny flik eller fönster >>Order-preserving graph grammars
2019 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Alternativ titel[sv]
Ordningsbevarande grafgrammatiker
Abstract [en]

The field of semantic modelling concerns formal models for semantics, that is, formal structures for the computational and algorithmic processing of meaning. This thesis concerns formal graph languages motivated by this field. In particular, we investigate two formalisms: Order-Preserving DAG Grammars (OPDG) and Order-Preserving Hyperedge Replacement Grammars (OPHG), where OPHG generalise OPDG.

Graph parsing is the practise of, given a graph grammar and a graph, to determine if, and in which way, the grammar could have generated the graph. If the grammar is considered fixed, it is the non-uniform graph parsing problem, while if the grammars is considered part of the input, it is named the uniform graph parsing problem. Most graph grammars have parsing problems known to be NP-complete, or even exponential, even in the non-uniform case. We show both OPDG and OPHG to have polynomial uniform parsing problems, under certain assumptions.

We also show these parsing algorithms to be suitable, not just for determining membership in graph languages, but for computing weights of graphs in graph series.

Additionally, OPDG is shown to have several properties common to regular languages, such as MSO definability and MAT learnability. We moreover show a direct corresponcence between OPDG and the regular tree grammars.

Finally, we present some limited practical experiments showing that real-world semantic graphs appear to mostly conform to the requirements set by OPDG, after minimal, reversible processing.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå universitet, Institutionen för datavetenskap, 2019. s. 56
Serie
Report / UMINF, ISSN 0348-0542 ; 19.01
Nyckelord
Graph grammars, graph parsing, graph series, hyperedge replacement, uniform parsing problem, abstract meaning representation, semantic modelling, order preservation, reentrancy preservation, minimally adequate teacher, weighted graph grammars
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-154777 (URN)978-91-7855-017-3 (ISBN)
Disputation
2019-02-04, MA121, Umeå, 13:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2019-01-14 Skapad: 2019-01-07 Senast uppdaterad: 2019-07-05Bibliografiskt granskad

Open Access i DiVA

fulltext(324 kB)21 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 324 kBChecksumma SHA-512
a989bcad4d96e76e484412feece897dc95378be4efd20e77ed930ce2704052a958c7f8dcbca39586f2c4e9f38954efac9e4e39d35fb084efd710d346939f94aa
Typ fulltextMimetyp application/pdf

Övriga länkar

URL

Personposter BETA

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
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 21 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.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 442 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