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. 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

  2. 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 journalArticle

  3. A probabilistic model of Ancient Egyptian writing

    Nederhof, M. J. & Rahman, F., 1 Jul 2017, In : Journal of Language Modelling. 5, 1, p. 131-163

    Research output: Contribution to journalArticle

  4. A derivational model of discontinuous parsing

    Nederhof, M. J. & Yli-Jyra, A., 2017, Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Drewes, F., Martin-Vide, C. & Truthe, B. (eds.). Cham: Springer, p. 299-310 (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10168).

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

ID: 243243685

Top