MIX is a 2-MCFL and the word problem in Z2 is captured by the IO and the OI hierarchies
MIX is a 2-MCFL and the word problem in Z2 is captured by the IO and the OI hierarchies
复制标题
DOI：
10.1016/j.jcss.2015.03.004
复制
发表时间：
2015-11-01
影响因子：
1.1
通讯作者：
Salvati, Sylvain
中科院分区：
文献类型：
--
作者：
Salvati, Sylvain
在这项工作中，我们确定语言 MIX = {w 是 {a; 的一个元素；乙； c}* 竖条 竖条 w 竖条(a) = 竖条 w 竖条(b) = 竖条 w 竖条(c)} 且语言 O-2 = {w 是 {a; 的元素； (a) 过杆；乙； (b) 竖条} 竖条 竖条 w 竖条(a) = 竖条 w 竖条((a) 横条) Lambda 竖条 w 竖条(b) = 竖条 w 竖条((b) 横条)} 是 2-MCFL。由于 2-MCFL5 形成一类包含在 IO 和 OI 层次结构中的语言，并且由于 O-2 是 Z(2) 简单表示的群语言，因此我们在这里展示了第一个，据我们所知，由 IO 和 OI 层次结构捕获的非虚拟自由群语言（即非上下文无关群语言）。此外，MIX 是否是一种轻度上下文敏感语言是一个长期悬而未决的问题，并且推测它不是，所以我们通过给出否定答案来结束这个猜想。 (C) 2015 Elsevier Inc. 保留所有权利。
In this work we establish that the language MIX = {w is an element of {a; b; c}* vertical bar vertical bar w vertical bar(a) = vertical bar w vertical bar(b) = vertical bar w vertical bar(c)} and the language O-2 = {w is an element of {a; (a) over bar; b; (b) over bar} vertical bar vertical bar w vertical bar(a) = vertical bar w vertical bar((a) over bar) Lambda vertical bar w vertical bar(b) = vertical bar w vertical bar((b) over bar)} are 2-MCFLs. As 2-MCFL5 form a class of languages that is included in both the IO and OI hierarchies, and as O-2 is the group language of a simple presentation of Z(2) we exhibit here the first, to our knowledge, non-virtually-free group language (i.e. non-context-free group language) that is captured by the IO and OI hierarchies. Moreover, it was a long-standing open problem whether MIX was a mildly context sensitive language or not, and it was conjectured that it was not, so we close this conjecture by giving it a negative answer. (C) 2015 Elsevier Inc. All rights reserved.