| 1. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- 2019
-
Ingår i: Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. - : Association for Computational Linguistics. ; , s. 7-17
-
Konferensbidrag (refereegranskat)abstract
- We propose a formal model for translating unranked syntactic trees, such as dependency trees, into semantic graphs. These tree-to-graph transducers can serve as a formal basis of transition systems for semantic parsing which recently have been shown to perform very well, yet hitherto lack formalization. Our model features "extended" rules and an arc-factored normal form, comes with an efficient translation algorithm, and can be equipped with weights in a straightforward manner.
|
|
| 2. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 870, s. 3-28
-
Tidskriftsartikel (refereegranskat)abstract
- We develop a finite-state transducer for translating unranked trees into general graphs. This work is motivated by recent progress in semantic parsing for natural language, where sentences are first mapped into tree-shaped syntactic representations, and then these trees are translated into graph semantic representations. We investigate formal properties of our tree-to-graph transducers and develop a polynomial time algorithm for translating a weighted language of input trees into a packed representation, from which best-score graphs can be efficiently recovered.
|
|
| 3. |
- Björklund, Johanna, et al.
(författare)
-
Z-Automata for Compact and Direct Representation of Unranked Tree Languages
- 2019
-
Ingår i: Implementation and Application of Automata. - Cham : Springer. - 9783030236786 - 9783030236793 ; , s. 83-94
-
Konferensbidrag (refereegranskat)abstract
- Unranked tree languages are valuable in natural language processing for modelling dependency trees. We introduce a new type of automaton for unranked tree languages, called Z-automaton, that is tailored for this particular application. The Z-automaton offers a compact form of representation, and unlike the closely related notion of stepwise automata, does not require a binary encoding of its input. We establish an arc-factored normal form, and prove the membership problem of Z-automata in normal form to be in O(mn), where m is the size of the transition table of the Z-automaton and n is the size of the input tree.
|
|
| 4. |
- Chiang, David, et al.
(författare)
-
Weighted DAG automata for semantic graphs
- 2018
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - Cambridge : MIT Press. - 0891-2017 .- 1530-9312. ; 44:1, s. 119-186
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 5. |
- Gómez-Rodríguez, Carlos, et al.
(författare)
-
Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems
- 2010
-
Ingår i: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. - Stroudsburg, PA, USA : Association for Computational Linguistics. ; , s. 276-284, s. 276-284
-
Konferensbidrag (refereegranskat)abstract
- The use of well-nested linear context-free rewriting systems has been empirically motivated for modeling of the syntax of languages with discontinuous constituents or relatively free word order. We present a chart-based parsing algorithm that asymptotically improves the known running time upper bound for this class of rewriting systems. Our result is obtained through a linear space construction of a binary normal form for the grammar at hand.
|
|
| 6. |
- Gómez-Rodriguez, Carlos, et al.
(författare)
-
Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
- 2009
-
Ingår i: Human Language Technologies. - Stroudsburg, PA, USA : Association for Computational Linguistics. - 9781932432411 ; , s. 539-547
-
Konferensbidrag (refereegranskat)abstract
- Linear Context-free Rewriting Systems (LCFRS) is an expressive grammar formalism with applications in syntax-based machine translation. The parsing complexity of an LCFRS is exponential in both the rank of a production, defined as the number of nonterminals on its right-hand side, and a measure for the discontinuity of a phrase, called fan-out. In this paper, we present an algorithm that transforms an LCFRS into a strongly equivalent form in which all productions have rank at most 2, and has minimal fan-out. Our results generalize previous work on Synchronous Context-Free Grammar, and are particularly relevant for machine translation from or to languages that require syntactic analyses with discontinuous constituents.
|
|
| 7. |
- Kuhlmann, Marco, 1977-, et al.
(författare)
-
A New Parsing Algorithm for Combinatory Categorial Grammar
- 2014
-
Ingår i: Transactions of the Association for Computational Linguistics. - : Association for Computational Linguistics. - 2307-387X. ; 2:2014, s. 405-418
-
Tidskriftsartikel (refereegranskat)abstract
- We present a polynomial-time parsing algorithm for CCG, based on a new decomposition of derivations into small, shareable parts. Our algorithm has the same asymptotic complexity, O(n⁶), as a previous algorithm by Vijay-Shanker and Weir (1993), but is easier to understand, implement, and prove correct.
|
|
| 8. |
- Kuhlmann, Marco, 1977-, et al.
(författare)
-
Dynamic Programming Algorithms for Transition-Based Dependency Parsers
- 2011
-
Ingår i: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics. - Stroudsburg, PA, USA : Association for Computational Linguistics. - 9781932432879 ; , s. 673-682
-
Konferensbidrag (refereegranskat)abstract
- We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms.
|
|
| 9. |
- Kuhlmann, Marco, et al.
(författare)
-
Lexicalization and Generative Power in CCG
- 2015
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : Massachusetts Institute of Technology Press (MIT Press): STM Titles / MIT Press. - 0891-2017 .- 1530-9312. ; 41:2, s. 215-247
-
Tidskriftsartikel (refereegranskat)abstract
- The weak equivalence of Combinatory Categorial Grammar (CCG) and Tree-Adjoining Grammar (TAG) is a central result of the literature on mildly context-sensitive grammar formalisms. However, the categorial formalism for which this equivalence has been established differs significantly from the versions of CCG that are in use today. In particular, it allows restriction of combinatory rules on a per grammar basis, whereas modern CCG assumes a universal set of rules, isolating all cross-linguistic variation in the lexicon. In this article we investigate the formal significance of this difference. Our main result is that lexicalized versions of the classical CCG formalism are strictly less powerful than TAG.
|
|
| 10. |
- Kuhlmann, Marco, et al.
(författare)
-
On the Complexity of CCG Parsing
- 2018
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : MIT PRESS. - 0891-2017 .- 1530-9312. ; 44:3, s. 447-482
-
Tidskriftsartikel (refereegranskat)abstract
- We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.
|
|
| 11. |
- Kuhlmann, Marco, 1977-, et al.
(författare)
-
The Importance of Rule Restrictions in CCG
- 2010
-
Ingår i: Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. - Stroudsburg, PA, USA : Association for Computational Linguistics. - 9781932432664 - 9781932432671 ; , s. 534-543
-
Konferensbidrag (refereegranskat)abstract
- Combinatory Categorial Grammar (CCG) is generally construed as a fully lexicalized formalism, where all grammars use one and the same universal set of rules, and cross-linguistic variation is isolated in the lexicon. In this paper, we show that the weak generative capacity of this `pure’ form of CCG is strictly smaller than that of CCG with grammar-specific rules, and of other mildly context-sensitive grammar formalisms, including Tree Adjoining Grammar (TAG). Our result also carries over to a multi-modal extension of CCG.
|
|
| 12. |
- Kuhlmann, Marco, 1977-, et al.
(författare)
-
Tree-Adjoining Grammars are not Closed Under Strong Lexicalization
- 2012
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - Cambridge, MA, USA : MIT Press. - 0891-2017 .- 1530-9312. ; 38:3, s. 617-629
-
Tidskriftsartikel (refereegranskat)abstract
- A lexicalized tree-adjoining grammar is a tree-adjoining grammar where each elementary tree contains some overt lexical item. Such grammars are being used to give lexical accounts of syntactic phenomena, where an elementary tree defines the domain of locality of the syntactic and semantic dependencies of its lexical items. It has been claimed in the literature that for every tree-adjoining grammar, one can construct a strongly equivalent lexicalized version. We show that such a procedure does not exist: Tree-adjoining grammars are not closed under strong lexicalization.
|
|
| 13. |
- Kuhlmann, Marco, 1977-, et al.
(författare)
-
Treebank Grammar Techniques for Non-Projective Dependency Parsing
- 2009
-
Ingår i: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics. - Stroudsburg, PA, USA : Association for Computational Linguistics. ; , s. 478-486
-
Konferensbidrag (refereegranskat)abstract
- An open problem in dependency parsing is the accurate and efficient treatment of non-projective structures. We propose to attack this problem using chart-parsing algorithms developed for mildly context-sensitive grammar formalisms. In this paper, we provide two key tools for this approach. First, we show how to reduce non-projective dependency parsing to parsing with Linear Context-Free Rewriting Systems (LCFRS), by presenting a technique for extracting LCFRS from dependency treebanks. For efficient parsing, the extracted grammars need to be transformed in order to minimize the number of nonterminal symbols per production. Our second contribution is an algorithm that computes this transformation for a large, empirically relevant class of grammars.
|
|
| 14. |
|
|
| 15. |
- Satta, Giorgio, et al.
(författare)
-
Efficient Parsing for Head-Split Dependency Trees
- 2013
-
Ingår i: Transactions of the Association for Computational Linguistics. - Stroudsburg, PA, USA : Association for Computational Linguistics. - 2307-387X. ; 1:July, s. 267-278
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Head splitting techniques have been successfully exploited to improve the asymptotic runtime of parsing algorithms for projective dependency trees, under the arc-factored model. In this article we extend these techniques to a class of non-projective dependency trees, called well-nested dependency trees with block-degree at most 2, which has been previously investigated in the literature. We define a structural property that allows head splitting for these trees, and present two algorithms that improve over the runtime of existing algorithms at no significant loss in coverage.
|
|
| 16. |
- Schiffer, Lena Katharina, et al.
(författare)
-
Tractable Parsing for CCGs of Bounded Degree
- 2022
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : MIT PRESS. - 0891-2017 .- 1530-9312. ; 48:3, s. 593-633
-
Tidskriftsartikel (refereegranskat)abstract
- Unlike other mildly context-sensitive formalisms, Combinatory Categorial Grammar (CCG) cannot be parsed in polynomial time when the size of the grammar is taken into account. Refining this result, we show that the parsing complexity of CCG is exponential only in the maximum degree of composition. When that degree is fixed, parsing can be carried out in polynomial time. Our finding is interesting from a linguistic perspective because a bounded degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.
|
|
