Weighted DAG Automata for Semantic Graphs
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 fi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The MIT Press
2017-12-01
|
| Series: | Computational Linguistics |
| Online Access: | http://dx.doi.org/10.1162/coli_a_00309 |
| _version_ | 1797795400715862016 |
|---|---|
| author | David Chiang Frank Drewes Daniel Gildea Adam Lopez Giorgio Satta |
| author_facet | David Chiang Frank Drewes Daniel Gildea Adam Lopez Giorgio Satta |
| author_sort | David Chiang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-13T03:18:27Z |
| format | Article |
| id | doaj.art-b089f8da0a3447d692fb2fe87b7448ff |
| institution | Directory Open Access Journal |
| issn | 1530-9312 |
| language | English |
| last_indexed | 2024-03-13T03:18:27Z |
| publishDate | 2017-12-01 |
| publisher | The MIT Press |
| record_format | Article |
| series | Computational Linguistics |
| spelling | doaj.art-b089f8da0a3447d692fb2fe87b7448ff2023-06-25T14:50:05ZengThe MIT PressComputational Linguistics1530-93122017-12-0144110.1162/coli_a_00309Weighted DAG Automata for Semantic GraphsDavid ChiangFrank DrewesDaniel GildeaAdam LopezGiorgio SattaGraphs 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.http://dx.doi.org/10.1162/coli_a_00309 |
| spellingShingle | David Chiang Frank Drewes Daniel Gildea Adam Lopez Giorgio Satta Weighted DAG Automata for Semantic Graphs Computational Linguistics |
| title | Weighted DAG Automata for Semantic Graphs |
| title_full | Weighted DAG Automata for Semantic Graphs |
| title_fullStr | Weighted DAG Automata for Semantic Graphs |
| title_full_unstemmed | Weighted DAG Automata for Semantic Graphs |
| title_short | Weighted DAG Automata for Semantic Graphs |
| title_sort | weighted dag automata for semantic graphs |
| url | http://dx.doi.org/10.1162/coli_a_00309 |
| work_keys_str_mv | AT davidchiang weighteddagautomataforsemanticgraphs AT frankdrewes weighteddagautomataforsemanticgraphs AT danielgildea weighteddagautomataforsemanticgraphs AT adamlopez weighteddagautomataforsemanticgraphs AT giorgiosatta weighteddagautomataforsemanticgraphs |