Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Parsing Weighted Order-Preserving Hyperedge Replacement 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)ORCID-id: 0000-0001-7349-7693
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-8722-5661
2018 (engelsk)Rapport (Annet vitenskapelig)
Abstract [en]

We introduce a weighted extension of the recently proposed notion of order-preserving hyperedge-replacement grammars and prove that the weight of a graph according to such a weighted graph grammar can be computed uniformly in quadratic time (under assumptions made precise in the paper).

sted, utgiver, år, opplag, sider
Umeå: Umeå Universitet , 2018. , s. 12
Serie
Report / UMINF, ISSN 0348-0542 ; 18.16
Emneord [en]
graph grammars, order-preservation, parsing, weighted graph grammars
HSV kategori
Forskningsprogram
administrativ databehandling
Identifikatorer
URN: urn:nbn:se:umu:diva-153395OAI: oai:DiVA.org:umu-153395DiVA, id: diva2:1264055
Tilgjengelig fra: 2018-11-19 Laget: 2018-11-19 Sist oppdatert: 2019-07-05bibliografisk kontrollert
Inngår i avhandling
1. Order-preserving graph grammars
Åpne denne publikasjonen i ny fane eller vindu >>Order-preserving graph grammars
2019 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Alternativ tittel[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.

sted, utgiver, år, opplag, sider
Umeå: Umeå universitet, Institutionen för datavetenskap, 2019. s. 56
Serie
Report / UMINF, ISSN 0348-0542 ; 19.01
Emneord
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
HSV kategori
Identifikatorer
urn:nbn:se:umu:diva-154777 (URN)978-91-7855-017-3 (ISBN)
Disputas
2019-02-04, MA121, Umeå, 13:00 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2019-01-14 Laget: 2019-01-07 Sist oppdatert: 2019-07-05bibliografisk kontrollert

Open Access i DiVA

fulltext(347 kB)107 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 347 kBChecksum SHA-512
c511642b56ca5c03650eadeedd4a63986d41ed08a2eeace2ae5fe855d3a24921fd594744467db726069d2099064d4d1ea0e95d421ee5157cbf8de1e0b275ef75
Type fulltextMimetype application/pdf

Andre lenker

URL

Person

Björklund, HenrikDrewes, FrankEricson, Petter

Søk i DiVA

Av forfatter/redaktør
Björklund, HenrikDrewes, FrankEricson, Petter
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 107 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 1141 treff
RefereraExporteraLink to record
Permanent link

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