严格导数极小主义下的最简主义语法研究

网址：http://www.elsevier.nl/locate/entcs/volume53.html18页观察严格导数极小主义延斯·米凯利斯大学？波茨坦研究所？r语言学，PF 601553，14415波茨坦，德国摘要Stabler[13]从[12]最初提出的定义出发，在最近一些关于转换句法的最简主义方法的建议的启发下，引入了一种（修订的）最简主义语法（MG）以及一种严格的最简主义语法（SMG）。这两种类型可以用来确定同一类可派生的字符串语言。1引言在[12]中引入的最低限度语法（MG）类型提供了一种在转换生成语法的语言框架内对当今所采用的观点进行严格形式化的尝试如[4]所示，这种类型的MG构成线性上下文无关重写系统（LCFRS）的弱等价子类[14，15]。 最近，哈克马[2]”[7]而《古兰经》也是这样说的因此，MG如[12]中所定义的，除了LCFRS之外，还加入到一系列轻度上下文敏感的形式主义类中，其中例如有多分量树邻接文法（MCTAG）类，其在其允许的Adjunc- tion的集合局部变体中（参见[15])所有这些都生成同一类字符串语言，这被称为替换封闭全AFL。[1]主要受[3]中提出的语言学工作的启发，[13]中提出了一种修改的MG类型，其与[12]中的版本的偏离可以被视为两方面的：修改的MG类型既不使用任何类型的头部运动，也不使用内隐短语运动，并且对移动算子施加了额外的限制，即最大投影可以公开移动。与文[12]最初定义的操作move不同，一个成分必须属于补语关系的传递闭包或成为这种传递闭包的一个特例一个组成部分，以便能够移动。与一些更进一步的？ 这项工作由DFG资助STA 519/1-1资助。1 对于一些此类发电设备的列表，除了MCTAG，参见例如。[9]的文件。c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2nn2INnGn2IN0n1nn2L0（A），用于每个终端A！2R，and2Lk+1（A）if2Lk（A），orr在[3]的建议下，[13]中也引入了某种严格最简文法（SMG）。这种MG类型只允许属于补语关系的传递闭包的成分的移动。但与第一类型不同的是，触发被许可者特征可以位于移动成分的特定关系的自反传递闭包内的任何成分的头标签。此外，由于SMG的词项的一般性定义，SMG不允许在派生过程中创建多个speci ers。本文回答了[13]中明确留下的一些重要问题：MG和SMG的各自类型被证明可以确定同一类可导出的字符串语言。这是通过证明这两种形式主义类型是弱等价于同一子类的LCFRS。相应的类生成的字符串语言也构成了一个替代封闭的全AFL。它是否与所有LCFRS可实现的字符串语言的类一致仍然是一个悬而未决的问题。2多上下文无关文法LCFRS形成了多上下文无关文法（MCFG）的一个适当子类[11]，而MCFG又是广义上下文无关文法的一个子类型[8]。但是LCFRS和MCFG是同一类可派生的字符串语言定义2.1 [8]广义上下文无关文法（GCFG）是一种元组G = h N; O; F; R; Si，其中N是非终结符的nite非空集，O是（语言）对象的集合。F是Sn2INFnnf;g的有限子集，F是从hOini n到O的部分函数的集合。2 R是一组（重写）规则，即 S（F\F）hNin+1的子集。S是一位杰出的系统工程师从N开始，开始符号。Anr=hf;hA; A; ：; Aii2（F\F）hNin+1，对于某个n2IN，记为0分！ f（A1; ：;An），也是A0！ f（;）如果n=0。 当n=0时，i. e.如果f是O中的常数，r是终止的，否则r是非终止的。对于每个A2N和k2IN，Lk（A）O通过以下方式递归地给出：G G G如果有A！f（A;：：;A）2R和2L k（A），1我n使得1n iGiH;：; i 2 Dom（f）和f（;：;）=. 第三集L(A) =SLk（A）1n1nGk2ING是可从A（被G）导出的语言。LG（S），也记为yL（G），是可由G.定义2.2 [11]多重上下文无关文法（MCFG）是GCFGG=hN;O;F;R;Si，其中O=Shin+1，并且满足（M1）和（M2），2 IN是所有非负整数的集合。 对于n2 IN和任何集合M ;：;M，QM是1 ni=1i n所有n个元组hm1; ： ;mni集合，其中第i个元组为ntmi2Mi，其中Qi=1Mi：=f;g对于n=0。我们把Q写成hMini=1Mi 如果对于某个集合M，M=M代表1我，3 对于从集合M到集合M0的每个部分函数g，Dom（g）M是g的定义域。n3i=1哈哈哈G1in（f）存在，使得f是来自Qn（f）hidi（f）的（全）函数哪里是一组终端，\N= ;。4（M1）F或eachf2F，一些n（f）2IN，'（f）2INnf0g和di（f）2INnf0 g，其中h（f1）和（f2）成立。（f 1）设Xf=fxijj 1in（f）;1jdi（ f）g是一组两两不同的变量，对于1in（f），设xi=hxi1; ：;xidi（f）i，对于1h'（f），设fh是f的第h个分量，即从Dom（f）到对于所有2个Do m（f），su chf（）=hf（）; ：; f （）i。那么对于1'（f）eachh1h'（f）有一个l（f）2IN，a（f）2 对于0ll（f），对1 l l h（f）有z（fh l）2×f，使得fh由y（cfh）表示. （c、f、h）fh（x1; ：;xn（f ））=（fh0）z（fh1）（fh1）z（fh lh（f））（fhlh（f））（f2）在（cf1）（cf'（f））的所有钻机及侧边最多出现一次即对于集合I Dom（f）= fhi; j ij1我n（f）; 1Jdi（ f）g和设IRange（f ）=f h h ;lij 1h'（f）;1lllh（f）g，二元关系gfIdom（f ）IRange（f）满足hhi;ji;hh;lli2gfixij=z（fhl）是n到IRange（f） 的一个内射 偏函数.（M2）存在从N到IN的函数d G，其中d G（S）= 1，使得如果A0！ f（A1; ： ：;An）2R，对某个n2IN，则'（f）=dG（A0）和di（f）=dG（Ai），对1in.G的秩，记为rank（G），是数maxf n（f）jf2Fg。可由G导出的语言，即集合L（G），称为多上下文无关语言（MCFL）。注意L（G），因为d（S）= 1。定义2.3 [14，15]在定义2.2的意义上的MCFGG，使得对于每个f2，除了（f1）和（f2）之外，F条件（f3）也成立，这就是所谓的线性上下文无关重写系统（LCFRS）。在这种情况下，L（G）是线性上下文无关重写语言（LCFRL）。（f3）Ea chxij2Xf必须出现在（cf1）（cf'（f））的其中一条边中，即来自（f2）的函数gf是全的，因此是双射。所有MCFL的类别和所有LCFRL的类别已知是相同的（参见图10）。[11，引理2.2]）。因此，[9]中的定理11导致：推论2.4F或每个MC FGG，re是一个rank（G0）2的弱等价LCFRS G 0.定义2.5MCFG1;2 （LCFRS1;2）是在定义2.2（定义2.3）的意义上的MC FG（LCFRS）G，使得秩（G）2，并且使得对于n（f）= 2的每个f2 F，di （f）=1 。 在 这 种 情 况 下 ， 可 由 yG 导 出 的 语 言 是 MCF L1;24（LCFRL1;2）。4 对于每个集合M，M是M的Kleene闭包，包括空字符串。M表示集合M[ fg]。5FF1; 21;2对于f1; ：; d（f）g，则对于1j;j0 d（f），j;]如果为1 <0。定义4.3 [13]最简语法（MG）是一个形式为h的ve元组：Sy n;Syn;Lex;;ci，其中Lex是一个lexi con（overFea t），即 一组简单的表达式在Feat上，每个表达式的形式为h N;/<;labe li，其中N = f g和labe l（）2（Select [Licensors] Base Licenses Phon Sem），其中是由结构构建函数merge和move定义的w.r.t.如下面的（me）和（mo）。（ 我 ）merge 是 Exp （ Feat ）的 部分映 射Exp （Feat ）转 换为Exp（Feat）。一对h;i透过;2Exp（Feat）属于Dom（合并），如果对于一些x2基本条件（i）和（ii）被填充：(i) 选择器= 得双曲正弦值.9 注意，通过（E4），对于每个= hN;/;;<; labeli 2Exp（Feat）at2 IN和a10树域N与N =TN 确实存在11<>>(ii) 有X类。然后，（me.1）merge（;）= [0的整数;0 ] 如果简单且（me.2）merge（;）= [0的整数;0]如果是复杂的，哪里0 和0 分别通过删除相应头部标签开始的特征实例而(mo)move是从Exp（Feat）到Exp（Feat）的部分映射。表达式2 Exp（Feat）在Dom（move）中，如果对于某些-x2许可证持有人条件（i）（iii）为真：(i) 具有许可方功能+X，(ii) 只有一个2 MaxProj（）具有feature-x，(iii) 存在一个2Com p+（），其中=或2S pec（）。然后，move（） =[>;]，0 0其中02 Exp（Feat）是通过取消的实例+X的头标签开始，而子树被替换为一个单一的节点标记。02 Exp（Feat）由删除实例而产生-x的头部标签开始。定义4.4 [13]严格最小文法（SMG）是形式h：Syn; Syn; Lex; ;ci的ve元组，其中Lex是Feat上的表达式的集合，每个形式h N;/<;labe li，其中N=fg，并且labe l（）在Select（Select[Licensors] Base LicensesPhon Sem中，并且其中是由结构构建函数merege和move es定义的操作器集合。如上（me），下（smo）。（smo）movees 是从Ex p（Fea t）in到Ex p（Fea t）的部分映射。表达式2 Exp（Feat）在Dom（move）中，如果对于某些-x2被许可方条件（i）（iii）为真：(i) 具有许可方功能+X，(ii) 只有一个2 MaxProj（）具有feature-x，(iii) 存在一个2Com p+ （）和2S pec （）。 10然后，moves（） = [0;0]，其中02 Exp（Feat）是通过取消的实例+X的头标签开始，而子树被替换为一个单一的节点标记。02 Exp（Feat）源于通过删除-x的实例，head标签的开头是。10 注意，su cha2Com p+（）是唯一的。12k2IN;F或eachh（S）MGG=h：Syn;Syn;Lexi;;ci是G的闭包，CL（G）是集合SCLK（G），其中CL0（G）= Lex，且对k2IN，CLk+1（G）Exp（Feat）被递归地定义为CLk（G）[fmerge（;）jh;i2 Dom（merge）\CLk（G）CLk（G）g[fmove0（）j2Dom（move0）\CLk（G） g，其中移动02n fm egg。 L（G）表示可由G导出的（字符串）语言，即集合fYPhon（）j2CL（G）和完备集g.定义4.5一个集合L是一个（严格）最简语言（（S）ML），如果存在一个（S）MGG，其中L=L（G）。5（S）MLs作为MCFL在[4]中提出了将如[12]中所定义的MG转换为MCFG的方法如在[5]中所证明的，该 方法可以适于将如在[13] 中所定义的（S ） MG 变换成MCFG1;2。但请注意，这种适应并不是微不足道的，因为在原始MG定义中，移动被定义为上面的（mo），但没有条件（iii），即最大投影可以完全独立于其在表达式中的位置而移动。此外，通过重写规则和函数的可导出元组的处理必须被相当显著地改变，以便如所期望的那样达到MCFG。116MCFL作为（S）ML在整个本节中，G = h N; 0; F; R; Si表示在定义2.5的意义上的MCFG1;2。为了设计一个MGGMG =h：Syn;Syn;Lex;;ci在定义4.3的意义上，如果L（GMG）=L（G），则我们满足w.l.o.g.G为MFF中的LCFRS 1;2（参见提案3.2）。当然，在[2]和[7]中分别给出了如何为任意MCFG构造最初在[12]中给出的类型的弱等价MG的方法从MCFG1;2开始，w.r.t.两种方法中的每一种，所得到的MG的词典甚至可以被解释为定义4.3意义上的MG的词典，而不会导致在结构构建函数下的词典的封闭性的改变12然而，如果根据[7]的构造产生的MG的词典被解释为11 [5]中的各个考虑甚至比我们在这里关注的必要性更复杂：在那里，给出了w.r.t.一种类型的（S）MG，与[13]中的定义相反，仍然允许（明显）头部运动和隐蔽短语运动发生。在[6]中考虑了将[13]中的适当意义上的MG变换为MC F G12的普通情况。12 就[2]中提出的方法而言，原来的建筑是需要的。13h=1h hGChf;'（f）+1;0ihf;h;lihf;'（f）+1;0ihf;h;lih=c a;HSMG的词典，即 如果操作者move被y操作者move替换，则为了构建相应的闭包。13这是不可能的w.r.t. MGGMG这是因为它满足了命题6.5的（a）和（b），这意味着由GMG派生的语言也是SML（推论6.4）。这个结果得到了一个有趣的结论，即ML类和SML类是相同的，从而证实了[13]中相应的猜想.激发下面的结构，让A！f（A1;：;An（f）） 2R和pi2LG（Ai）对于1in（f），因此，p=f（p1; ：;pn（f ））2LG（A）：我们的目的是定义一个GMG因此，有一些CL（GMG）可从某些表达式1; ：;n（f）导出2CL（GMG），成功地计算了在n（f） +3'（f） +P'（f）2l（f）步中的'（f）元组p。14Each表达，我对于1in（f），将与Ai和pi相关，并且以特定的方式得到A和p的定义6.1）。粗略地说，对于，对于每个 1hdG （A），有一个h2MaxProj（），它有一个特定的被许可人，直到从h中可能提取的适当子树的语音产量，p的分量ph是h的语音产量.让Phon=且Sem=;。F或1hm和0n1设-lhh;ni为被许可方，+Lhh;ni为匹配的许可方，使得被许可方和许可方都具有基数2m。15对 于 每个A2N引入新的，成对不同的基本范畴？和a以及相应的选择器=？并且对于1h d（A）= a。 每一个A！f（A1;：; An（f））2 R引入新的两两不同的基本范畴a和a以及相应的选择子=a并且=a，其中1h′（f）和0ll（f）。最后，假设c2基地与Base中的所有其他元素不同。接 下 来 ，我们定义一个Lex Exp（：Syn[Syn]）。16第一件被确定属于莱克斯的物品是==sc，其中2Base是从S2N产生的相应范畴。形式Lex中所有其他项的值取决于R中的规则。我们区分三种情况。案例1. A！f（B; C）2 R对某些A，B，C2N和f2F.在这种情况下，（f）=dG（A），n（f）=2，d1（f）=dG（B）=1和d2（f）=dG（C）。以下元素属于Lex：=hA;f;B;Ci1hf;'（f）+1;0i13 注意，多个规范的使用在Harkema [2]的方法中具有相当大的构成性，导致特别是根据他的构造从MC F G12产生的MG词典通常不符合SMG定义。14 回想一下，（f）=dG（A）by（M3）。15 这里，m= maxfdG（A） jA 2N g。16 因为它是一个有词根的中心词，我们用它的（唯一的）标签来识别一个词项。14案例2和案例3=aa-l（f）.=a a-l（f）b a（f） if z（ f）= x=Hhf;h;lihl hl11>a+La（f）否则，=b aH=aa-l（f）.hf; h +1;0ihj;1ihf; h;lh（f）ihlh（ f）=F或each1h'（f），其中lh（f）=0，=hA;f;h;0ihf;h+1;0ihf;h;0ihh;0ih0F或each1h'（f），其中lh（f）>0，=hA;f;h;0ihf;h;1ihf;h;0ihh;0ih0= ahf;h+1;0i为hf; h; l（f）ihl（f）hl（f）11hA;f;h;l（f）i =>ahf;h;l+1i=ba（f）ifz（ f）=xhA;f;h;li 为=hf;h;l+1ihj;1ihf;h;lihl其中1jd2（f），其中z（fhl（f））=x2j17案例2. A！ f（B），B2N，f2F. 在这种情况下，n（f）=dG（A），n（f）= 1，d1（f）= dG（B）。然 后 ，下面的元素属于Lex：=hA;f;B;i1hf;'（f）+1;0i案例3. A！ f（）对A2N和f2F. 则f（f） =dG（A）且n（f）=0。对于1 h '（f），lh（f） =0，即 f（） =h（f1 0）; ：;（f'（f）0）i，因为f是hi'（f）中的常数。以下是我在此尝试的内容：hA;f;;i =ahf;'（f）+1;0i，也有下列项在Lex中：F或each1h'（f），其中lh（f）=0，我们只需添加=hA;f;h;0ihf;h+1;0ihf;h;0ihh;0ih0F或each1h'（f），其中lh（f）>0，815hA;f;h;0i ==ahf;h;1iahf;h;0i-lhh;0i（fh0）hA;f;h;lh（f）i ==ahf;h+1;0i+Lhj;1iahf;h;lh（f）i（fhlh（f）），其中1jd1（f）使得z（fhlh（f））=x1j。17 由于d1（f）= 1，这样的j存在且唯一。16=a +L a（f），=a+La-1，=a+La-1，GGh0的事实。这个证明是从k2 IN上的一个归纳得出的，其中k+1K.18MG名爵MGMGFMG如果k+1 =K（我们的归纳法的基本情况），则0必然是最后对于某个k2IN，其中k + 1 K考虑2CL k+1（G ）nCLk（G ）例如，具有类别A1或？一些A2N。通过Lex的定义，推导出了GMG的表达式 在以下意义上是决定性的：有一些r =A！f（A1;：;An（f））2R，一些 k02IN，k=k+13'（f）P'（f）2l（一）一些2CLk0（G），使得0小时=1小时0毫克0服务于GMG中的衍生物。0具有范畴特征ahf;'（f）+1;0i，并且是一个有三种形式取决于r：案例1. 有一个r=A！f（B;C）2R，对于某个k0k1k，存在某个分别具有类别特征和c1，并且0=me rg e（hA;f;B;Ci;）。更明确地说，k1可以由下式指定：1 0Ph1（）下一页K= k+ 2l+1 + h+h0=02l'fh0（f）对0h<'（f）和0l

下载后可阅读完整内容，剩余1页未读，立即下载