A pumping lemma for DLI-languages
A pumping lemma for DLI-languages
复制标题
DOI：
10.1016/s0012-365x(02)00265-0
复制
发表时间：
2002-12-06
影响因子：
0.8
通讯作者：
K치szonyi, L
中科院分区：
文献类型：
--
作者：
K치szonyi, L
分层线性集在Ginsburg（The Mathematical Theory of Context-Free Languages，McGraw-Hill，纽约，1966）提出的有界上下文无关语言理论中起着核心作用。“触发器引理”（Pure Math.Appl.Ser.A6（2）（1995）203）指出，向量集{（e（0），...，e（m-1））是N（m）\delta（0）e（0）+（...）+的元素。delta（m-1）e（m-1）不等于0}，其中delta（i）是{-1，0，1}的元素，对于i = 0，...，m - 1，N表示非负整数的集合，是分层半线性集合，即，分层线性集合的有限并集。在本文中，我们推广了引理的陈述，给出了DLI-集的一个充分必要条件（即，对于由线性不等式定义的向量集）是分层半线性的。(C)2002 Elsevier Science B. V.保留所有权利。
Stratified linear sets play a central role in the theory of bounded context-free languages, developed by Ginsburg (The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966). The "Flip-Flop Lemma," (Pure Math. Appl. Ser. A 6(2) (1995) 203), states, that the vector-set{(e(0),...,e(m-1)) is an element ofN(m) \delta(0)e(0) +(...)+ delta(m-1)e(m-1) not equal 0}where delta(i)is an element of {-1,0, 1}, for i = 0,...,m - 1, and N denotes the set of non-negative integers, is a stratified semilinear set, i.e., a finite union of stratified linear sets. In this paper, we generalize the statement of the lemma giving a necessary and sufficient condition for a DLI-set (i.e., for a vector-set Defined by Linear Inequalities) to be stratified semilinear. (C) 2002 Elsevier Science B.V. All rights reserved.