liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 32) Show all publications
Drewes, F., Knight, K. & Kuhlmann, M. (2015). Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122). Dagstuhl Reports, 5(3), 143-161
Open this publication in new window or tab >>Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)
2015 (English)In: Dagstuhl Reports, ISSN 2192-5283, Vol. 5, no 3, p. 143-161Article in journal, Meeting abstract (Other academic) Published
Abstract [en]

In natural language processing (NLP) there is an increasing interest in formal models for processing graphs rather than more restricted structures such as strings or trees. Such models of graph transformation have previously been studied and applied in various other areas of computer science, including formal language theory, term rewriting, theory and implementation of programming languages, concurrent processes, and software engineering. However, few researchers from NLP are familiar with this work, and at the same time, few researchers from the theory of graph transformation are aware of the specific desiderata, possibilities and challenges that one faces when applying the theory of graph transformation to NLP problems. The Dagstuhl Seminar 15122 “Formal Models of Graph Transformation in Natural Language Processing” brought researchers from the two areas together. It initiated an interdisciplinary exchange about existing work, open problems, and interesting applications.

Keyword
natural language processing, graph transformation
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-124720 (URN)10.4230/DagRep.5.3.143 (DOI)
Available from: 2016-02-11 Created: 2016-02-11 Last updated: 2018-01-10
Kuhlmann, M., Koller, A. & Satta, G. (2015). Lexicalization and Generative Power in CCG. Computational linguistics - Association for Computational Linguistics (Print), 41(2), 215-247
Open this publication in new window or tab >>Lexicalization and Generative Power in CCG
2015 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 41, no 2, p. 215-247Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Massachusetts Institute of Technology Press (MIT Press): STM Titles / MIT Press, 2015
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-121145 (URN)10.1162/COLI_a_00219 (DOI)000359625700002 ()
Available from: 2015-09-08 Created: 2015-09-08 Last updated: 2018-01-11
Kuhlmann, M., Kanazawa, M. & Kobele, G. (Eds.). (2015). MoL 2015: the 14th meeting on the Mathematics of language. Proceedings, July 25-26, Chicago, USA. Paper presented at 14th Meeting on Mathematics of Language (MoL 2015), July 25-26, 2015, Chicago, USA. Stroudsburg: Association for Computational Linguistics
Open this publication in new window or tab >>MoL 2015: the 14th meeting on the Mathematics of language. Proceedings, July 25-26, Chicago, USA
2015 (English)Conference proceedings (editor) (Refereed)
Abstract [en]

This volume contains eleven regular papers and  two invited papers. The regular papers, which were selected by the Program Committee from a total of twenty-two submissions, feature a broad variety of work on mathematics of language, including phonology, formal language theory, natural language semantics, and language learning. The invited papers are presented by two distinguished researchers in the field: David McAllester, Professor and Chief Academic Officer at the Toyota Technological Institute at Chicago, and Ryo Yoshinaka, Assistant Professor at Kyoto University.

Place, publisher, year, edition, pages
Stroudsburg: Association for Computational Linguistics, 2015. p. 165
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-124719 (URN)9781941643563 (ISBN)
Conference
14th Meeting on Mathematics of Language (MoL 2015), July 25-26, 2015, Chicago, USA
Available from: 2016-02-11 Created: 2016-02-11 Last updated: 2018-01-10Bibliographically approved
Kuhlmann, M. & Jonsson, P. (2015). Parsing to Noncrossing Dependency Graphs. Transactions of the Association for Computational Linguistics, 3, 559-570
Open this publication in new window or tab >>Parsing to Noncrossing Dependency Graphs
2015 (English)In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 3, p. 559-570Article in journal (Refereed) Published
Abstract [en]

We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restriction to noncrossing dependency graphs. Our main contribution is a cubic-time exact inference algorithm for this class. We extend this algorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most $k$ and show that the resulting optimization problem is NP-hard for k ≥ 2.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2015
Keyword
natural language processing, algorithms, complexity theory
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-124718 (URN)
Available from: 2016-02-11 Created: 2016-02-11 Last updated: 2018-01-10
Oepen, S., Kuhlmann, M., Miyao, Y., Zeman, D., Cinková, S., Flickinger, D., . . . Urešová, Z. (2015). SemEval 2015 Task 18: Broad-Coverage Semantic Dependency Parsing. In: Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015): . Paper presented at 9th International Workshop on Semantic Evaluation (SemEval 2015) (pp. 915-926). Association for Computational Linguistics
Open this publication in new window or tab >>SemEval 2015 Task 18: Broad-Coverage Semantic Dependency Parsing
Show others...
2015 (English)In: Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015), Association for Computational Linguistics, 2015, p. 915-926Conference paper, Published paper (Refereed)
Abstract [en]

Task 18 at SemEval 2015 defines Broad-Coverage Semantic Dependency Parsing (SDP) as the problem of recovering sentence-internal predicate–argument relationships for all content words, i.e. the semantic structure constituting the relational core of sentence meaning. In this task description, we position the problem in comparison to other language analysis sub-tasks, introduce and compare the semantic dependency target representations used, and summarize the task setup, participating systems, and main results. 

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2015
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-118631 (URN)978-1-941643-39-6 (ISBN)
Conference
9th International Workshop on Semantic Evaluation (SemEval 2015)
Available from: 2015-06-02 Created: 2015-06-02 Last updated: 2018-01-11
Kuhlmann, M. & Satta, G. (2014). A New Parsing Algorithm for Combinatory Categorial Grammar. Transactions of the Association for Computational Linguistics, 2(2014), 405-418
Open this publication in new window or tab >>A New Parsing Algorithm for Combinatory Categorial Grammar
2014 (English)In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 2, no 2014, p. 405-418Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2014
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-114364 (URN)
Available from: 2015-02-19 Created: 2015-02-19 Last updated: 2018-01-11
Kuhlmann, M. (2014). Linköping: Cubic-Time Graph Parsing with a Simple Scoring Scheme. In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014): . Paper presented at 8th International Workshop on Semantic Evaluation (SemEval 2014) (pp. 395-399). Association for Computational Linguistics
Open this publication in new window or tab >>Linköping: Cubic-Time Graph Parsing with a Simple Scoring Scheme
2014 (English)In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014), Association for Computational Linguistics, 2014, p. 395-399Conference paper, Published paper (Refereed)
Abstract [en]

We turn the Eisner algorithm for parsing to projective dependency trees into a cubic-time algorithm for parsing to a restricted class of directed graphs. To extend the algorithm into a data-driven parser, we combine it with an edge-factored feature model and online learning. We report and discuss results on the SemEval-2014 Task 8 data sets (Oepen et al., 2014).

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2014
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-114366 (URN)978-1-941643-24-2 (ISBN)
Conference
8th International Workshop on Semantic Evaluation (SemEval 2014)
Available from: 2015-02-19 Created: 2015-02-19 Last updated: 2018-01-11
Oepen, S., Kuhlmann, M., Miyao, Y., Zeman, D., Flickinger, D., Hajič, J., . . . Zhang, Y. (2014). SemEval 2014 Task 8: Broad-Coverage Semantic Dependency Parsing. In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014): . Paper presented at 8th International Workshop on Semantic Evaluation (SemEval 2014) (pp. 63-72). Association for Computational Linguistics
Open this publication in new window or tab >>SemEval 2014 Task 8: Broad-Coverage Semantic Dependency Parsing
Show others...
2014 (English)In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014), Association for Computational Linguistics, 2014, p. 63-72Conference paper, Published paper (Refereed)
Abstract [en]

Task 8 at SemEval 2014 defines Broad-Coverage Semantic Dependency Parsing (SDP) as the problem of recovering sentence-internal predicate–argument relationships for all content words, i.e. the semantic structure constituting the relational core of sentence meaning. In this task description, we position the problem in comparison to other sub-tasks in computational language analysis, introduce the semantic dependency target representations used, reflect on high-level commonalities and differences between these representations, and summarize the task setup, participating systems, and main results.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2014
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-114368 (URN)978-1-941643-24-2 (ISBN)
Conference
8th International Workshop on Semantic Evaluation (SemEval 2014)
Available from: 2015-02-19 Created: 2015-02-19 Last updated: 2018-01-11
Satta, G. & Kuhlmann, M. (2013). Efficient Parsing for Head-Split Dependency Trees. Transactions of the Association for Computational Linguistics, 1(July), 267-278
Open this publication in new window or tab >>Efficient Parsing for Head-Split Dependency Trees
2013 (English)In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 1, no July, p. 267-278Article in journal (Other academic) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Stroudsburg, PA, USA: Association for Computational Linguistics, 2013
National Category
Language Technology (Computational Linguistics)
Research subject
Computational Linguistics
Identifiers
urn:nbn:se:liu:diva-100278 (URN)
Available from: 2013-07-17 Created: 2013-11-04 Last updated: 2018-01-11Bibliographically approved
Kuhlmann, M. (2013). Mildly Non-Projective Dependency Grammar. Computational linguistics - Association for Computational Linguistics (Print), 39(2), 355-387
Open this publication in new window or tab >>Mildly Non-Projective Dependency Grammar
2013 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 39, no 2, p. 355-387Article in journal (Refereed) Published
Abstract [en]

Syntactic representations based on word-to-word dependencies have a long-standing tradition in descriptive linguistics, and receive considerable interest in many applications. Nevertheless, dependency syntax has remained somewhat of an island from a formal point of view. Moreover, most formalisms available for dependency grammar are restricted to projective analyses, and thus not able to support natural accounts of phenomena such as wh-movement and cross–serial dependencies. In this article we present a formalism for non-projective dependency grammar in the framework of linear context-free rewriting systems. A characteristic property of our formalism is a close correspondence between the non-projectivity of the dependency trees admitted by a grammar on the one hand, and the parsing complexity of the grammar on the other. We show that parsing with unrestricted grammars is intractable. We therefore study two constraints on non-projectivity, block-degree and well-nestedness. Jointly, these two constraints define a class of “mildly” non-projective dependency grammars that can be parsed in polynomial time. An evaluation on five dependency treebanks shows that these grammars have a good coverage on empirical data.

Place, publisher, year, edition, pages
Cambridge, MA, USA: MIT Press, 2013
National Category
Language Technology (Computational Linguistics)
Research subject
Computational Linguistics
Identifiers
urn:nbn:se:liu:diva-100297 (URN)10.1162/COLI_a_00125 (DOI)000318556900004 ()
Available from: 2013-11-04 Created: 2013-11-04 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-2492-9872

Search in DiVA

Show all publications