On is an n-MCFL

Kilian Gebhardt; Frédéric Meunier; Sylvain Salvati

doi:10.1016/j.jcss.2022.02.003

O_n is an n-MCFL

Kilian Gebhardt
, Frédéric Meunier
, Sylvain Salvati

Research output: Contribution to journal › Article › peer-review

Abstract

Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language O_n, the language that contains the same number of letters a_i and a¯_i with 1⩽i⩽n, in the known classes of formal languages. It has recently been shown that O_n is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that O_n is an MCFL of dimension n was left open. We prove this conjecture using tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.

Original language	English
Pages (from-to)	41-52
Number of pages	12
Journal	Journal of Computer and System Sciences
Volume	127
DOIs	https://doi.org/10.1016/j.jcss.2022.02.003
Publication status	Published - 1 Aug 2022

Keywords

Commutative Languages
Formal Languages
Multiple Context Free Languages
Necklace splitting theorem
Tucker Lemma
Word problem in groups

Access to Document

10.1016/j.jcss.2022.02.003

Cite this

@article{16a4ba7478d5402e96f425d18b28f73d,

title = "On is an n-MCFL",

abstract = "Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language On, the language that contains the same number of letters ai and a¯i with 1⩽i⩽n, in the known classes of formal languages. It has recently been shown that On is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that On is an MCFL of dimension n was left open. We prove this conjecture using tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.",

keywords = "Commutative Languages, Formal Languages, Multiple Context Free Languages, Necklace splitting theorem, Tucker Lemma, Word problem in groups",

author = "Kilian Gebhardt and Fr{\'e}d{\'e}ric Meunier and Sylvain Salvati",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = aug,

day = "1",

doi = "10.1016/j.jcss.2022.02.003",

language = "English",

volume = "127",

pages = "41--52",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

}

TY - JOUR

T1 - On is an n-MCFL

AU - Gebhardt, Kilian

AU - Meunier, Frédéric

AU - Salvati, Sylvain

PY - 2022/8/1

Y1 - 2022/8/1

N2 - Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language On, the language that contains the same number of letters ai and a¯i with 1⩽i⩽n, in the known classes of formal languages. It has recently been shown that On is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that On is an MCFL of dimension n was left open. We prove this conjecture using tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.

AB - Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language On, the language that contains the same number of letters ai and a¯i with 1⩽i⩽n, in the known classes of formal languages. It has recently been shown that On is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that On is an MCFL of dimension n was left open. We prove this conjecture using tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.

KW - Commutative Languages

KW - Formal Languages

KW - Multiple Context Free Languages

KW - Necklace splitting theorem

KW - Tucker Lemma

KW - Word problem in groups

UR - https://www.scopus.com/pages/publications/85125506260

U2 - 10.1016/j.jcss.2022.02.003

DO - 10.1016/j.jcss.2022.02.003

M3 - Article

AN - SCOPUS:85125506260

SN - 0022-0000

VL - 127

SP - 41

EP - 52

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

O_n is an n-MCFL

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this