Skip to content

Research at St Andrews

A short proof that O2 is an MCFL

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Author(s)

School/Research organisations

Abstract

We present a new proof that O2 is a multiple context-free language. It contrasts with a recent proof by Salvati (2015) in its avoidance of concepts that seem specific to two-dimensional geometry, such as the complex exponential function. Our simple proof creates realistic prospects of widening the results to higher dimensions. This finding is of central importance to the relation between extreme free word order and classes of grammars used to describe the syntax of natural language.
Close

Details

Original languageEnglish
Title of host publication54th Annual meeting of the Association for Computational Linguistics
Subtitle of host publicationProceedings of the Conference
Place of PublicationBerlin
PublisherAssociation for Computational Linguistics
Number of pages10
Publication statusPublished - 7 Aug 2016
Event54th Annual meeting of the Association for Computational Linguistics - Berlin, Germany
Duration: 7 Aug 201612 Aug 2016
http://www.acl2016.org/

Conference

Conference54th Annual meeting of the Association for Computational Linguistics
CountryGermany
CityBerlin
Period7/08/1612/08/16
Internet address

    Research areas

  • Computational linguistics, Formal language theory

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Calculating the optimal step of arc-eager parsing for non-projective trees

    Nederhof, M. J., 19 Apr 2021, Proceedings of the 16th Conference of the European Chapter of the Association of Computational Linguistics (EACL 2021). Association for Computational Linguistics, p. 2273–2283

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. A derivational model of discontinuous parsing

    Nederhof, M-J. & Yli-Jyrä, A., 10 Aug 2020, In: Information and Computation. In press, 104619.

    Research output: Contribution to journalArticlepeer-review

  3. Regular transductions with MCFG input syntax

    Nederhof, M. J. & Vogler, H., 23 Sep 2019, Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. Maletti, A. & Vogler, H. (eds.). Dresden: Association for Computational Linguistics, p. 56-64 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Hybrid grammars for parsing of discontinuous phrase structures and non-projective dependency structures

    Gebhardt, K., Nederhof, M. J. & Vogler, H., Sep 2017, In: Computational Linguistics. 43, 3, p. 465-520 56 p.

    Research output: Contribution to journalArticlepeer-review

ID: 243243685

Top