A short proof that O2 is an MCFL

Mark Jan Nederhof

A short proof that O₂ is an MCFL

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a new proof that O₂ 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.

Original language	English
Title of host publication	54th Annual meeting of the Association for Computational Linguistics
Subtitle of host publication	Proceedings of the Conference
Place of Publication	Berlin
Publisher	Association for Computational Linguistics
Number of pages	10
Publication status	Published - 7 Aug 2016
Event	54th Annual meeting of the Association for Computational Linguistics - Berlin, Germany Duration: 7 Aug 2016 → 12 Aug 2016 http://www.acl2016.org/

Conference

Conference	54th Annual meeting of the Association for Computational Linguistics
Country/Territory	Germany
City	Berlin
Period	7/08/16 → 12/08/16
Internet address	http://www.acl2016.org/

Keywords

Computational linguistics
Formal language theory

Access to Document

Nederhof_2016_AShortProof_ACL_AAM
© 2016, the Author(s). This work is made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at http://aclweb.org/anthology/
Accepted author manuscript, 241 KB

Cite this

@inproceedings{fe9b625cd10e45a78ee6a25dd3fa04c8,

title = "A short proof that O2 is an MCFL",

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

keywords = "Computational linguistics, Formal language theory",

author = "Nederhof, {Mark Jan}",

year = "2016",

month = aug,

day = "7",

language = "English",

booktitle = "54th Annual meeting of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics",

note = "54th Annual meeting of the Association for Computational Linguistics ; Conference date: 07-08-2016 Through 12-08-2016",

url = "http://www.acl2016.org/",

}

TY - GEN

T1 - A short proof that O2 is an MCFL

AU - Nederhof, Mark Jan

PY - 2016/8/7

Y1 - 2016/8/7

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

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

KW - Computational linguistics

KW - Formal language theory

M3 - Conference contribution

BT - 54th Annual meeting of the Association for Computational Linguistics

PB - Association for Computational Linguistics

CY - Berlin

T2 - 54th Annual meeting of the Association for Computational Linguistics

Y2 - 7 August 2016 through 12 August 2016

ER -