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
Order-preserving graph grammars
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-8722-5661
2019 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)Alternativ titel
Ordningsbevarande grafgrammatiker (Svenska)
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 [en]
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: urn:nbn:se:umu:diva-154777ISBN: 978-91-7855-017-3 (tryckt)OAI: oai:DiVA.org:umu-154777DiVA, id: diva2:1275818
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
Delarbeten
1. Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars
Öppna denna publikation i ny flik eller fönster >>Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars
2016 (Engelska)Ingår i: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, Vol. 9618, s. 521-532Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Motivated by applications in natural language processing, we study the uniform membership problem for hyperedge-replacement grammars that generate directed acyclic graphs. Our major result is a low-degree polynomial-time algorithm that solves the uniform membership problem for a restricted type of such grammars. We motivate the necessity of the restrictions by two different NP-completeness results.

Ort, förlag, år, upplaga, sidor
Springer Publishing Company, 2016
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9618
Nyckelord
Graph grammar, Hyperedge replacement, Abstract meaning representation, DAG grammar, Uniform membership problem, Parsing
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-111984 (URN)10.1007/978-3-319-30000-9_40 (DOI)000378745100045 ()978-3-319-30000-9 (ISBN)978-3-319-29999-0 (ISBN)
Konferens
10th International Conference on Language and Automata Theory and Applications (LATA 2016), Prague, Czech Republic, March 14-18, 2016
Tillgänglig från: 2015-11-29 Skapad: 2015-11-29 Senast uppdaterad: 2019-01-07Bibliografiskt granskad
2. On the Regularity and Learnability of Ordered DAG Languages
Öppna denna publikation i ny flik eller fönster >>On the Regularity and Learnability of Ordered DAG Languages
2017 (Engelska)Ingår i: Implementation and Application of Automata: 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / [ed] Arnaud Carayol and Cyril Nicaud, Cham, 2017, s. 27-39Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Order-Preserving DAG Grammars (OPDGs) is a subclass of Hyper-Edge Replacement Grammars that can be parsed in polynomial time. Their associated class of languages is known as Ordered DAG Lan- guages, and the graphs they generate are characterised by being acyclic, rooted, and having a natural order on their nodes. OPDGs are useful in natural-language processing to model abstract meaning representa- tions. We state and prove a Myhill-Nerode theorem for ordered DAG languages, and translate it into a MAT-learning algorithm for the same class. The algorithm infers a minimal OPDG G for the target language in time polynomial in G and the samples provided by the MAT oracle. 

Ort, förlag, år, upplaga, sidor
Cham: , 2017
Serie
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, E-ISSN 1611-3349 ; 10329
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:umu:diva-135010 (URN)10.1007/978-3-319-60134-2_3 (DOI)2-s2.0-85022042128 (Scopus ID)978-3-319-60133-5 (ISBN)978-3-319-60134-2 (ISBN)
Konferens
22nd International Conference Implementation and Application of Automata, CIAA 2017, Université Paris-Est Marne-la-Vallée, France, 27-30 June 2017
Tillgänglig från: 2017-05-16 Skapad: 2017-05-16 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
3. Minimisation and Characterisation of Order-Preserving DAG Grammars
Öppna denna publikation i ny flik eller fönster >>Minimisation and Characterisation of Order-Preserving DAG Grammars
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
graph grammars, minimally adequate teacher, order preservation, weighted graph grammars, weighted learning
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
administrativ databehandling
Identifikatorer
urn:nbn:se:umu:diva-153394 (URN)
Tillgänglig från: 2018-11-19 Skapad: 2018-11-19 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
4. Uniform Parsing for Hyperedge Replacement Grammars
Öppna denna publikation i ny flik eller fönster >>Uniform Parsing for Hyperedge Replacement Grammars
2018 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to be fixed rather than being part of the input. Little is known about restrictions under which truly uniform polynomial parsing is possible. In this paper we propose a low-degree polynomial-time algorithm that solves the uniform parsing problem for a restricted type of hyperedge-replacement grammars which we expect to be of interest for practical applications.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå universitet, 2018. s. 21
Serie
Report / UMINF, ISSN 0348-0542 ; 18.13
Nyckelord
graph grammars, hyperedge replacement, order-preserving graph grammars, uniform parsing problem
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
administrativ databehandling
Identifikatorer
urn:nbn:se:umu:diva-153384 (URN)
Tillgänglig från: 2018-11-19 Skapad: 2018-11-19 Senast uppdaterad: 2019-01-07Bibliografiskt granskad
5. Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
Öppna denna publikation i ny flik eller fönster >>Parsing Weighted Order-Preserving Hyperedge Replacement Grammars
2018 (Engelska)Rapport (Övrigt vetenskapligt)
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).

Ort, förlag, år, upplaga, sidor
Umeå: Umeå Universitet, 2018. s. 12
Serie
Report / UMINF, ISSN 0348-0542 ; 18.16
Nyckelord
graph grammars, order-preservation, parsing, weighted graph grammars
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
administrativ databehandling
Identifikatorer
urn:nbn:se:umu:diva-153395 (URN)
Tillgänglig från: 2018-11-19 Skapad: 2018-11-19 Senast uppdaterad: 2019-07-05Bibliografiskt granskad

Open Access i DiVA

kappa(490 kB)57 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 490 kBChecksumma SHA-512
a65683f37614dc7c59a24b38c8e67cb4a5e234392de0f17239873e68adb9ac9154d1030f4f838aa804180fb0abf84332b57dcf488938b36e72b6346b0c516915
Typ fulltextMimetyp application/pdf
spikblad(106 kB)23 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 106 kBChecksumma SHA-512
2b311452f568a6de89ebf010d922c40c8a3243095df78bb423c77673582709e0c7af8d89c5c449cfe612672cf051053473b6f424db438d97f1bd28297d1ad57e
Typ spikbladMimetyp application/pdf

Personposter BETA

Ericson, Petter

Sök vidare i DiVA

Av författaren/redaktören
Ericson, Petter
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

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

isbn
urn-nbn

Altmetricpoäng

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