Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies.
Saved in:
| Title: | Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies. |
|---|---|
| Authors: | Björklund, Johanna1 (AUTHOR) johanna@cs.umu.se, Drewes, Frank1 (AUTHOR) drewes@cs.umu.se, Jonsson, Anna1 (AUTHOR) aj@cs.umu.se |
| Source: | Computational Linguistics. Dec2023, Vol. 49 Issue 4, p841-882. 42p. |
| Subjects: | Natural language processing, Graph grammars, Linguistic models, Polynomials, Language & languages |
| Abstract: | Graph-based semantic representations are popular in natural language processing, 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 that 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Computational Linguistics is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 175132509 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Björklund%2C+Johanna%22">Björklund, Johanna</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> johanna@cs.umu.se</i><br /><searchLink fieldCode="AR" term="%22Drewes%2C+Frank%22">Drewes, Frank</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> drewes@cs.umu.se</i><br /><searchLink fieldCode="AR" term="%22Jonsson%2C+Anna%22">Jonsson, Anna</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> aj@cs.umu.se</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Computational+Linguistics%22">Computational Linguistics</searchLink>. Dec2023, Vol. 49 Issue 4, p841-882. 42p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Natural+language+processing%22">Natural language processing</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+grammars%22">Graph grammars</searchLink><br /><searchLink fieldCode="DE" term="%22Linguistic+models%22">Linguistic models</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Language+%26+languages%22">Language & languages</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Graph-based semantic representations are popular in natural language processing, 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 that 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. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Computational Linguistics is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=175132509 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1162/coli_a_00488 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 42 StartPage: 841 Subjects: – SubjectFull: Natural language processing Type: general – SubjectFull: Graph grammars Type: general – SubjectFull: Linguistic models Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Language & languages Type: general Titles: – TitleFull: Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Björklund, Johanna – PersonEntity: Name: NameFull: Drewes, Frank – PersonEntity: Name: NameFull: Jonsson, Anna IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2023 Type: published Y: 2023 Identifiers: – Type: issn-print Value: 08912017 Numbering: – Type: volume Value: 49 – Type: issue Value: 4 Titles: – TitleFull: Computational Linguistics Type: main |
| ResultId | 1 |
