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
Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0002-4696-9787
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0002-8722-5661
2018 (English)Report (Other academic)
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).

Place, publisher, year, edition, pages
Umeå: Umeå Universitet , 2018. , p. 12
Series
Report / UMINF, ISSN 0348-0542 ; 18.16
Keywords [en]
graph grammars, order-preservation, parsing, weighted graph grammars
National Category
Computer Sciences
Research subject
business data processing
Identifiers
URN: urn:nbn:se:umu:diva-153395OAI: oai:DiVA.org:umu-153395DiVA, id: diva2:1264055
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-07-05Bibliographically approved
In thesis
1. Order-preserving graph grammars
Open this publication in new window or tab >>Order-preserving graph grammars
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[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.

Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för datavetenskap, 2019. p. 56
Series
Report / UMINF, ISSN 0348-0542 ; 19.01
Keywords
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
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-154777 (URN)978-91-7855-017-3 (ISBN)
Public defence
2019-02-04, MA121, Umeå, 13:00 (English)
Opponent
Supervisors
Available from: 2019-01-14 Created: 2019-01-07 Last updated: 2019-07-05Bibliographically approved

Open Access in DiVA

fulltext(347 kB)15 downloads
File information
File name FULLTEXT01.pdfFile size 347 kBChecksum SHA-512
c511642b56ca5c03650eadeedd4a63986d41ed08a2eeace2ae5fe855d3a24921fd594744467db726069d2099064d4d1ea0e95d421ee5157cbf8de1e0b275ef75
Type fulltextMimetype application/pdf

Other links

URL

Authority records BETA

Björklund, HenrikDrewes, FrankEricson, Petter

Search in DiVA

By author/editor
Björklund, HenrikDrewes, FrankEricson, Petter
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 15 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

urn-nbn

Altmetric score

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