liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 37 of 37
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Debusmann, Ralph
    et al.
    Saarland University, Saarbrücken, Germany.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Dependency Grammar: Classification and Exploration2010In: Resource-Adaptive Cognitive Processes / [ed] Matthew W. Crocker, Jörg Siekmann, Springer Berlin/Heidelberg, 2010, p. 365-388Chapter in book (Other academic)
    Abstract [en]

    Syntactic representations based on word-to-word dependencies have a long tradition in descriptive linguistics [29]. In recent years, they have also become increasingly used in computational tasks, such as information extraction [5], machine translation [43], and parsing [42]. Among the purported advantages of dependency over phrase structure representations are conciseness, intuitive appeal, and closeness to semantic representations such as predicate-argument structures. On the more practical side, dependency representations are attractive due to the increasing availability of large corpora of dependency analyses, such as the Prague Dependency Treebank [19].

  • 2.
    Dienes, Péter
    et al.
    Saarland University, Saarbrücken, Germany.
    Koller, Alexander
    Saarland University, Saarbrücken, Germany.
    Kuhlmann, Marco
    Saarland University, Saarbrücken, Germany.
    Statistical A-Star Dependency Parsing2003In: Proceedings of the Workshop on Prospects and Advances in the Syntax/Semantics Interface / [ed] Denys Duchier and Geert-Jan Kruijff, 2003, p. 85-89Conference paper (Refereed)
    Abstract [en]

    Extensible Dependency Grammar (XDG; Duchier and Debusmann (2001)) is a recently developed dependency grammar formalism that allows the characterization of linguistic structures along multiple dimensions of description. It can be implemented efficiently using constraint programming (CP; Koller and Niehren 2002). In the CP context, parsing is cast as a search problem: The states of the search are partial parse trees, successful end states are complete and valid parses. In this paper, we propose a probability model for XDG dependency trees and an A-Star search control regime for the XDG parsing algorithm that guarantees the best parse to be found first. Extending XDG with a statistical component has the benefit of bringing the formalism further into the grammatical mainstream; it also enables XDG to efficiently deal with large, corpus-induced grammars that come with a high degree of ambiguity.

  • 3.
    Drewes, Frank
    et al.
    Umeå University.
    Knight, Kevin
    University of Southern California, Information Sciences Institute.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)2015In: Dagstuhl Reports, ISSN 2192-5283, Vol. 5, no 3, p. 143-161Article in journal (Other academic)
    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.

  • 4.
    Drewes, Frank
    et al.
    Umeå University, Umeå, Sweden.
    Kuhlmann, MarcoUppsala universitet, Institutionen för lingvistik och filologi.
    ATANLP 2012 Workshop on Applications of Tree Automata Techniques in Natural Language Processing: Proceedings of the Workshop2012Conference proceedings (editor) (Other academic)
  • 5.
    Drewes, Frank
    et al.
    Umeå University, Umeå, Sweden.
    Kuhlmann, MarcoUppsala universitet, Institutionen för lingvistik och filologi.
    Workshop on Applications of Tree Automata in Natural Language Processing 2010 (ATANLP 2010)2010Conference proceedings (editor) (Other academic)
  • 6.
    Fallgren, Per
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Segeblad, Jesper
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Towards a Standard Dataset of Swedish Word Vectors2016In: Proceedings of the Sixth Swedish Language Technology Conference (SLTC), 2016Conference paper (Refereed)
    Abstract [en]

    Word vectors, embeddings of words into a low-dimensional space, have been shown to be useful for a large number of natural language processing tasks. Our goal with this paper is to provide a useful dataset of such vectors for Swedish. To this end, we investigate three standard embedding methods: the continuous bag-of-words and the skip-gram model with negative sampling of Mikolov et al. (2013a), and the global vectors of Pennington et al. (2014). We compare these methods using QVEC-CCA (Tsvetkov et al., 2016), an intrinsic evaluation measure that quantifies the correlation of learned word vectors with external linguistic resources. For this propose we use SALDO, the Swedish Association Lexicon (Borin et al., 2013). Our experiments show that the continuous bag-of-words model produces vectors that are most highly correlated to SALDO, with the skip-gram model very close behind. Our learned vectors will be provided for download at the paper’s website.

  • 7.
    Ferrara Boston, Marisa
    et al.
    Department of Linguistics, Cornell University, Ithaca, NY, USA.
    Hale, John
    Department of Linguistics, Cornell University, Ithaca, NY, USA.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Dependency Structures Derived from Minimalist Grammars2010In: The Mathematics of Language: 10th and 11th Biennial Conference, MOL 10, Los Angeles, CA, USA, July 28–30, 2007, and MOL 11, Bielefeld, Germany, August 20–21, 2009, Revised Selected Papers, Springer Berlin/Heidelberg, 2010, p. 1-12Conference paper (Refereed)
    Abstract [en]

    This paper provides an interpretation of Minimalist Grammars (Stabler, 1997; Stabler & Keenan, 2003) in terms of dependency structures. Under this interpretation, merge operations derive projective dependency structures, and movement operations create both non-projective and illnested structures. This provides a new characterization of the generative capacity of Minimalist Grammar, and makes it possible to discuss the linguistic relevance of non-projectivity and illnestedness based on grammars that derive structures with these properties.

  • 8.
    Gómez-Rodriguez, Carlos
    et al.
    Departamento de Computación, Universidade da Coruña, A Coruña, Spain.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Satta, Giorgio
    Department of Information Engineering, University of Padua, Padua, Italy.
    Weir, David
    Department of Informatics, University of Sussex, East Sussex, Storbritannien.
    Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems2009In: Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Stroudsburg, PA, USA: Association for Computational Linguistics, 2009, p. 539-547Conference paper (Other academic)
    Abstract [en]

    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.

  • 9.
    Gómez-Rodríguez, Carlos
    et al.
    Departamento de Computación, Universidade da Coruña, A Coruña, Spain.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Satta, Giorgio
    Department of Information Engineering, University of Padua, Padua, Italy.
    Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems2010In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Proceedings of the Main Conference, Stroudsburg, PA, USA: Association for Computational Linguistics, 2010, p. 276-284Conference paper (Refereed)
    Abstract [en]

    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.

  • 10.
    Kallmeyer, Laura
    et al.
    Heinrich Heine University Düsseldorf, Düsseldorf, Germany.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    A Formal Model for Plausible Dependencies in Lexicalized Tree Adjoining Grammar2012In: Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms, 2012, p. 108-116Conference paper (Other academic)
    Abstract [en]

    Several authors have pointed out that the correspondence between LTAG derivation trees and dependency structures is not as direct as it may seem at first glance, and various proposals have been made to overcome this divergence. In this paper we propose to view the correspondence between derivation trees and dependency structures as a tree transformation during which the direction of some of the original edges is reversed. We show that, under this transformation, LTAG is able to induce both ill-nested dependency trees and dependency trees with gap-degree greater than 1, which is not possible under the direct reading of derivation trees as dependency trees.

  • 11.
    Koller, Alexander
    et al.
    Dept. of Linguistics, University of Potsdam, Potsdam, Germany.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    A Generalized View on Parsing and Translation2011In: Proceedings of the Twelfth International Conference on Parsing Technologies (IWPT), Stroudsburg, PA, USA: Association for Computational Linguistics, 2011, p. 2-13Conference paper (Other academic)
    Abstract [en]

    We present a formal framework that generalizes a variety of monolingual and synchronous grammar formalisms for parsing and translation. Our framework is based on regular tree grammars that describe derivation trees, which are interpreted in arbitrary algebras. We obtain generic parsing algorithms by exploiting closure properties of regular tree languages.

  • 12.
    Koller, Alexander
    et al.
    University of Potsdam, Potsdam, Germany.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Decomposing TAG Parsing Algorithms Using Simple Algebraizations2012In: Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms, 2012, p. 135-143Conference paper (Other academic)
    Abstract [en]

    We review a number of different ‘algebraic’ perspectives on TAG and STAG in the framework of interpreted regular tree grammars (IRTGs). We then use this framework to derive a new parsing algorithm for TAGs, based on two algebras that describe strings and derived trees. Our algorithm is extremely modular, and can easily be adapted to the synchronous case.

  • 13.
    Koller, Alexander
    et al.
    Department of Computational Linguistics, Saarland University, Saarbrücken, Germany.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Dependency Trees and the Strong Generative Capacity of CCG2009In: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, Stroudsburg, PA, USA: Association for Computational Linguistics, 2009, p. 460-468Conference paper (Refereed)
    Abstract [en]

    We propose a novel algorithm for extracting dependencies from CCG derivations. Unlike earlier proposals, our dependency structures are always tree-shaped. We then use these dependency trees to compare the strong generative capacities of CCG and TAG and obtain surprising results: Although both formalisms generate the same string languages, their strong generative capacities are equivalent if we ignore word order, and incomparable if we take it into account.

  • 14.
    Kornai, András
    et al.
    Hungarian Academy of Sciences, Hungary.
    Kuhlmann, MarcoUppsala University, Sweden.
    Proceedings of the 13th Meeting on the Mathematics of Language (MoL)2013Conference proceedings (editor) (Other academic)
    Abstract [en]

    The Mathematics of Language (MoL) special interest group traces its origins to a meeting held in October 1984 at Ann Arbor, Michigan. While MoL is among the oldest SIGs of the ACL, it is the first time that the proceedings are produced by our parent organization. The first volume was published by Benjamins, later ones became special issues of the Annals of Mathematics and Artificial Intelligence and Linguistics and Philosophy, and for the last three occasions (really six years, since MoL only meets every second year) we relied on the Springer LNCS series. Perhaps the main reason for this aloofness was that the past three decades have brought the ascendancy of statistical methods in computational linguistics, with the formal, grammar-based methods that were the mainstay of mathematical linguistics viewed with increasing suspicion.

    To make matters worse, the harsh anti-formal rhetoric of leading linguists relegated important attempts at formalizing Government-Binding and later Minimalist theory to the fringes of syntax. Were it not for phonology and morphology, where the incredibly efficient finite state methods pioneered by Kimmo Koskenniemi managed to bridge the gap between computational practice and linguistic theory, and were it not for the realization that the mathematical approach has no alternative in machine learning, MoL could have easily disappeared from the frontier of research.

    The current volume marks a time when we can begin to see the computational and the theoretical linguistics camps together again. The selection of papers, while still strong on phonology (Heinz and Lai, Heinz and Rogers) and morphology (Kornai et al.), extends well to syntax (Hunter and Dyer, Fowlie) and semantics (Clark et al., Fernando). Direct computational concerns such as machine translation (Martzoukos et al.), decoding (Corlett and Penn), and complexity (Berglund et al.) are now clearly seen as belonging to the core focus of the field.

    The 10 papers presented in this volume were selected by the Program Committee from 16 submissions. We would like to thank the authors, the members of the Program Committee, and our invited speaker for their contributions to the planning and execution of the workshop, and the ACL conference organizers, especially Aoife Cahill and Qun Liu (workshops), and Roberto Navigli and Jing-Shin Chang (publications) for their significant contributions to the overall management of the workshop and their direction in preparing the publication of the proceedings.

  • 15.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Dependency Structures and Lexicalized Grammars: An Algebraic Approach2010Book (Other academic)
  • 16.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, The Institute of Technology.
    Linköping: Cubic-Time Graph Parsing with a Simple Scoring Scheme2014In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014), Association for Computational Linguistics, 2014, p. 395-399Conference 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).

  • 17.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Mildly Non-Projective Dependency Grammar2013In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 39, no 2, p. 355-387Article in journal (Refereed)
    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.

  • 18.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Gómez-Rodríguez, Carlos
    Universidade da Coruña, A Coruña, Spain.
    Satta, Giorgio
    University of Padua; Padua, Italy.
    Dynamic Programming Algorithms for Transition-Based Dependency Parsers2011In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, Stroudsburg, PA, USA: Association for Computational Linguistics, 2011, p. 673-682Conference paper (Other academic)
    Abstract [en]

    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.

     

  • 19.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Parsing to Noncrossing Dependency Graphs2015In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 3, p. 559-570Article in journal (Refereed)
    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.

  • 20.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Kanazawa, MakotoNational Institute of Informatics, Japan.Kobele, GregoryUniversity of Chicago, USA.
    MoL 2015: the 14th meeting on the Mathematics of language. Proceedings, July 25-26, Chicago, USA2015Conference 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.

  • 21.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Koller, Alexander
    University of Potsdam, Germany.
    Satta, Giorgio
    University of Padua, Italy.
    Lexicalization and Generative Power in CCG2015In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 41, no 2, p. 215-247Article in journal (Refereed)
    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.

  • 22.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Koller, Alexander
    Cluster of Excellence, Saarland University, Saarbrücken, Germany.
    Satta, Giorgio
    Dept. of Information Engineering, University of Padua, Padua, Italy.
    The Importance of Rule Restrictions in CCG2010In: Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Stroudsburg, PA, USA: Association for Computational Linguistics, 2010, p. 534-543Conference paper (Other academic)
    Abstract [en]

    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.

  • 23.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Niehren, Joachim
    INRIA Lille, France.
    Logics and Automata for Totally Ordered Trees2008In: Rewriting Techniques and Applications, Proceedings / [ed] Voronkov, A, Springer Berlin/Heidelberg, 2008, p. 217-231Conference paper (Refereed)
    Abstract [en]

    A totally ordered tree is a tree equipped with an additional total order on its nodes. It provides a formal model for data that comes with both a hierarchical and a sequential structure; one example for such data are natural language sentences, where a sequential structure is given by word order, and a hierarchical structure is given by grammatical relations between words. In this paper, we study monadic second-order logic (MSO) for totally ordered terms. We show that the MSO satisfiability problem of unrestricted structures is undecidable, but give a decision procedure for practically relevant sub-classes, based on tree automata.

  • 24.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Nivre, Joakim
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Transition-Based Techniques for Non-Projective Dependency Parsing2010In: Northern European Journal of Language Technology (NEJLT), ISSN 2000-1533, Vol. 2, no 1, p. 1-19Article in journal (Refereed)
    Abstract [en]

    We present an empirical evaluation of three methods for the treatment of non-projective structures in transition-based dependency parsing: pseudo-projective parsing, non-adjacent arc transitions, and online reordering. We compare both the theoretical coverage and the empirical performance of these methods using data from Czech, English and German. The results show that although online reordering is the only method with complete theoretical coverage, all three techniques exhibit high precision but somewhat lower recall on non-projective dependencies and can all improve overall parsing accuracy provided that non-projective dependencies are frequent enough. We also find that the use of non-adjacent arc transitions may lead to a drop in accuracy on projective dependencies in the presence of long-distance non-projective dependencies, an effect that is not found for the two other techniques.

  • 25.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Oepen, Stephan
    Department of Informatics, University of Oslo.
    Towards a Catalogue of Linguistic Graph Banks2016In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 42, no 4, p. 819-827Article in journal (Refereed)
    Abstract [en]

    Graphs exceeding the formal complexity of rooted trees are of growing relevance to much NLP research. Although formally well understood in graph theory, there is substantial variation in the types of linguistic graphs, as well as in the interpretation of various structural properties. To provide a common terminology and transparent statistics across different collections of graphs in NLP, we propose to establish a shared community resource with an open-source reference implementation for common statistics.

  • 26.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, The Institute of Technology.
    Satta, Giorgio
    University of Padua.
    A New Parsing Algorithm for Combinatory Categorial Grammar2014In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 2, no 2014, p. 405-418Article in journal (Refereed)
    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.

  • 27.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Satta, Giorgio
    University of Padua, Padua, Italy.
    Tree-Adjoining Grammars are not Closed Under Strong Lexicalization2012In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 38, no 3, p. 617-629Article in journal (Refereed)
    Abstract [en]

    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.

  • 28.
    Kuhlmann, Marco
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Satta, Giorgio
    Department of Information Engineering, University of Padua, Padua, Italy.
    Treebank Grammar Techniques for Non-Projective Dependency Parsing2009In: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, Stroudsburg, PA, USA: Association for Computational Linguistics, 2009, p. 478-486Conference paper (Refereed)
    Abstract [en]

    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.

  • 29.
    Kuhlmann, Marco
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Satta, Giorgio
    Univ Padua, Italy.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    On the Complexity of CCG Parsing2018In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, no 3, p. 447-482Article in journal (Refereed)
    Abstract [en]

    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.

  • 30.
    Kurtz, Robin
    et al.
    Linköping University, Department of Computer and Information Science, Human-Centered systems.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems.
    Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs2017In: Proceedings of the 15th International Conference on Parsing Technologies, 2017Conference paper (Refereed)
    Abstract [en]

    Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint-crossing (1ec) graphs, which has high coverage on standard data sets. Our main contribution is a characterization of 1ec graphs as a subclass of the graphs with pagenumber at most 3. Building on this we show how to extend an existing parsing algorithm for 1-endpoint-crossing trees to the full class. While the runtime complexity of the extended algorithm is polynomial in the length of the input sentence, it features a large constant, which poses a challenge for practical implementations.

  • 31.
    Nivre, Joakim
    et al.
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Hall, Johan
    Uppsala universitet, Institutionen för lingvistik och filologi.
    An Improved Oracle for Dependency Parsing with Online Reordering2009In: Proceedings of the 11th International Conference on Parsing Technologies (IWPT), Stroudsburg, PA, USA: Association for Computational Linguistics, 2009, p. 73-76Conference paper (Refereed)
    Abstract [en]

    We present an improved training strategyfor dependency parsers that use online re-ordering to handle non-projective trees.The new strategy improves both efficiency and accuracy by reducing the number of swap operations performed on non-projective trees by up to 80%. We present state-of-the-art results for five languages with the best ever reported results for Czech.

  • 32.
    Oepen, Stephan
    et al.
    University of Oslo, Department of Informatics.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Miyao, Yusuke
    National Institute of Informatics, Tokyo.
    Zeman, Daniel
    Charles University in Prague, Faculty of Mathematics and Physics, Institute of Formal and Applied Linguistics.
    Cinková, Silvie
    Charles University in Prague, Faculty of Mathematics and Physics, Institute of Formal and Applied Linguistics.
    Flickinger, Dan
    Stanford University, Center for the Study of Language and Information.
    Hajič, Jan
    Charles University in Prague, Faculty of Mathematics and Physics, Institute of Formal and Applied Linguistics.
    Ivanova, Angelina
    University of Oslo, Department of Informatics.
    Urešová, Zdeňka
    Charles University in Prague, Faculty of Mathematics and Physics, Institute of Formal and Applied Linguistics.
    Towards Comparability of Linguistic Graph Banks for Semantic Parsing2016In: Proceedings of the 10th International Conference on Language Resources and Evaluation (LREC), 2016, p. 3991-3995Conference paper (Refereed)
    Abstract [en]

    We announce a new language resource for research on semantic parsing, a large, carefully curated collection of semantic dependency graphs representing multiple linguistic traditions. This resource is called SDP 2016 and provides an update and extension to previous versions used as Semantic Dependency Parsing target representations in the 2014 and 2015 Semantic Evaluation Exercises (SemEval). For a common core of English text, this third edition comprises semantic dependency graphs from four distinct frameworks, packaged in a unified abstract format and aligned at the sentence and token levels. SDP 2016 is the first general release of this resource and available for licensing from the Linguistic Data Consortium from May 2016. The data is accompanied by an open-source SDP utility toolkit and system results from previous contrastive parsing evaluations against these target representations.

  • 33.
    Oepen, Stephan
    et al.
    University of Oslo.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.
    Miyao, Yusuke
    National Institute of Informatics, Tokyo.
    Zeman, Daniel
    Charles University in Prague.
    Cinková, Silvie
    Charles University in Prague.
    Flickinger, Dan
    Stanford University.
    Hajič, Jan
    Charles University in Prague.
    Urešová, Zdeňka
    Charles University in Prague.
    SemEval 2015 Task 18: Broad-Coverage Semantic Dependency Parsing2015In: Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015), Association for Computational Linguistics, 2015, p. 915-926Conference 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. 

  • 34.
    Oepen, Stephan
    et al.
    University of Oslo.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, The Institute of Technology.
    Miyao, Yusuke
    National Institute of Informatics, Tokyo.
    Zeman, Daniel
    Charles University in Prague.
    Flickinger, Dan
    Stanford University.
    Hajič, Jan
    Charles University in Prague.
    Ivanova, Angelina
    University of Oslo.
    Zhang, Yi
    Nuance Communications Aachen GmbH.
    SemEval 2014 Task 8: Broad-Coverage Semantic Dependency Parsing2014In: Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014), Association for Computational Linguistics, 2014, p. 63-72Conference 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.

  • 35.
    Satta, Giorgio
    et al.
    Dept. of Information Engineering, University of Padua, Padua, Italy.
    Kuhlmann, Marco
    Uppsala universitet, Institutionen för lingvistik och filologi.
    Efficient Parsing for Head-Split Dependency Trees2013In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 1, no July, p. 267-278Article in journal (Other academic)
    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.

  • 36.
    Seddah, Djamé
    et al.
    U. Paris-Sorbonne/INRIA.
    Tsarfaty, Reut
    Weizman Institute.
    Kübler, Sandra
    Indiana U..
    Candito, Marie
    U. Paris-Diderot/INRIA.
    Choi, Jinho D.
    IPsoft Inc.,.
    Farkas, Richárd
    U. of Szeged.
    Foster, Jennifer
    Dublin City U.,.
    Goenaga, Iakes
    U. of the Basque Country.
    Galletebeitia, Koldo Gojenola
    U. of the Basque Country.
    Goldberg, Yoav
    Bar Ilan U.
    Green, Spence
    Stanford U.,.
    Habash, Nizar
    Nizar Habashl.
    Kuhlmann, Marco
    Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, The Institute of Technology. Uppsala U..
    Maier, Wolfgang
    Düsseldorf U.,.
    Nivre, Joakim
    Uppsala U.
    Przepiórkowski, Adam
    Polish Academy of Sciences.
    Roth, Ryan
    Columbia U..
    Seeker, Wolfgang
    Stuttgart U..
    Versley, Yannick
    Heidelberg U..
    Vincze, Veronika
    U. of Szeged.
    Woliński, Marcin
    Polish Academy of Sciences.
    Wróblewska, Alina
    Polish Academy of Sciences.
    Villemonte de la Clérgeriew, Eric
    INRIA.
    Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages2013In: Proceedings of the Fourth Workshop on Statistical Parsing of Morphologically Rich Languages, Association for Computational Linguistics, 2013, p. 146-182Conference paper (Other academic)
    Abstract [en]

    This paper reports on the first shared task on statistical parsing of morphologically rich languages (MRLs). The task features data sets from nine languages, each available both in constituency and dependency annotation. We report on the preparation of the data sets, on the proposed parsing scenarios, and on the evaluation metrics for parsing MRLs given different representation types. We present and analyze parsing results obtained by the task participants, and then provide an analysis and comparison of the parsers across languages and frameworks, reported for gold input as well as more realistic parsing scenarios.

  • 37.
    Seddah, Djamé
    et al.
    University Paris-Sorbonne/INRIA, France.
    Tsarfaty, Reut
    Weizman Institute, Israel.
    Kübler, Sandra
    Indiana University, USA.
    Candito, Marie
    University Paris-Diderot/INRIA, France.
    Choi, Jinho D.
    IPsoft Inc., USA.
    Farkas, Richárd
    University of Szeged, Hungary.
    Foster, Jennifer
    Dublin City University, Ireland.
    Goenaga, Iakes
    University of the Basque Country, Spain.
    Gojenola, Koldo
    University of the Basque Country, Spain.
    Goldberg, Yoav
    Bar-Ilan University, Israel.
    Green, Spence
    Stanford University, USA.
    Habash, Nizar
    Columbia University, USA.
    Kuhlmann, Marco
    Uppsala University, Sweden.
    Maier, Wolfgang
    Düsseldorf University, Germany.
    Nivre, Joakim
    Uppsala University, Sweden.
    Przepiórkowski, Adam
    Polish Academy of Sciences, Poland.
    Roth, Ryan
    Columbia University, USA.
    Seeker, Wolfgang
    Stuttgart University, Germany.
    Versley, Yannick
    Heidelberg University, Germany.
    Vincze, Veronika
    University of Szeged, Hungary.
    Woli´nski, Marcin
    Polish Academy of Sciences, Poland.
    Wróblewska, Alina
    Polish Academy of Sciences, Poland.
    Villemonte de la Clérgeriew, Eric
    INRIA, France.
    Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages2013In: Proceedings of the Fourth Workshop on Statistical Parsing of Morphologically Rich Languages, 2013, p. 146-182Conference paper (Refereed)
    Abstract [en]

    This paper reports on the first shared task on statistical parsing of morphologically rich languages (MRLs). The task features data sets from nine languages, each available both in constituency and dependency annotation. We report on the preparation of the data sets, on the proposed parsing scenarios, and on the evaluation metrics for parsing MRLs given different representation types. We present and analyze parsing results obtained by the task participants, and then provide an analysis and comparison of the parsers across languages and frameworks, reported for gold input as well as more realistic parsing scenarios.

1 - 37 of 37
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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