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
Weighted DAG automata for semantic graphs
University of Notre Dame.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
University of Rochester.
University of Edinburgh.
Show others and affiliations
2018 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, no 1, p. 119-186Article in journal (Refereed) Published
Abstract [en]

Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the frameworks of finite automata for strings and finite tree automata for trees. A possible starting point for such a framework is the formalism of directed acyclic graph (DAG) automata, defined by Kamimura and Slutzki and extended by Quernheim and Knight. In this article, we study the latter in depth, demonstrating several new results, including a practical recognition algorithm that can be used for inference and learning with models defined on DAG automata. We also propose an extension to graphs with unbounded node degree and show that our results carry over to the extended formalism.

Place, publisher, year, edition, pages
Cambridge: MIT Press, 2018. Vol. 44, no 1, p. 119-186
Keywords [en]
semantic graph, DAG automaton, abstract meaning representation
National Category
Computer Sciences Language Technology (Computational Linguistics)
Research subject
datorlingvistik
Identifiers
URN: urn:nbn:se:umu:diva-146106DOI: 10.1162/COLI_a_00309ISI: 000427544200005OAI: oai:DiVA.org:umu-146106DiVA, id: diva2:1194217
Available from: 2018-03-29 Created: 2018-03-29 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

fulltext(528 kB)73 downloads
File information
File name FULLTEXT01.pdfFile size 528 kBChecksum SHA-512
656670f632e19678da139d7dd1d05d1bfd2fa0916ddfdf90dce5cac3eeec475aaa6e47ea185f3d1af47b488732562a0a2d0557e70545c33574f5819068d24353
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Drewes, Frank

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
In the same journal
Computational linguistics - Association for Computational Linguistics (Print)
Computer SciencesLanguage Technology (Computational Linguistics)

Search outside of DiVA

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