Umeå University's logo

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
Generation and polynomial parsing of graph languages with non-structural reentrancies
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-8503-0118
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-9873-4170
2023 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 49, no 4, p. 841-882Article in journal (Refereed) Published
Abstract [en]

Graph-based semantic representations are popular in natural language processing (NLP), where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but which context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2023. Vol. 49, no 4, p. 841-882
Keywords [en]
Graph grammar, semantic graph, meaning representation, graph parsing
National Category
Language Technology (Computational Linguistics)
Research subject
Computer Science; computational linguistics
Identifiers
URN: urn:nbn:se:umu:diva-209515DOI: 10.1162/coli_a_00488ISI: 001152974700005Scopus ID: 2-s2.0-85173016925OAI: oai:DiVA.org:umu-209515DiVA, id: diva2:1765463
Projects
STING – Synthesis and analysis with Transducers and Invertible Neural Generators
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Swedish Research Council, 2020-03852Available from: 2023-06-10 Created: 2023-06-10 Last updated: 2024-02-19Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full textScopus

Authority records

Björklund, JohannaDrewes, FrankJonsson, Anna

Search in DiVA

By author/editor
Björklund, JohannaDrewes, FrankJonsson, Anna
By organisation
Department of Computing Science
In the same journal
Computational linguistics - Association for Computational Linguistics (Print)
Language Technology (Computational Linguistics)

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

doi
urn-nbn

Altmetric score

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