Deleting string rewriting systems preserve regularity
Deleting string rewriting systems preserve regularity
复制标题
删除字符串重写系统保留规律性
DOI：
10.1016/j.tcs.2004.04.009
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Johannes Waldmann
中科院分区：
文献类型：
--
作者：
D. Hofbauer;Johannes Waldmann
一个字符串重写系统被称为删除，如果在它的字母表上存在一个偏序，使得规则右边的每个字母都小于相应左边的某个字母。我们表明，重写关系引起的删除系统可以表示为一个有限的替代（到一个扩展的字母表），重写关系的逆上下文无关系统（在扩展的字母表），和限制（到原来的字母表）的组成。这里，如果任何规则的右手边的长度不超过1，则系统被称为逆上下文无关。分解结果直接表明删除系统保持正则性，而逆删除系统保持上下文无关性。后一个结果已经由Hibbard（J. ACM 21（3）（1974）446-453）得到。
A string rewriting system is called deleting if there exists a partial ordering on its alphabet such that each letter in the right-hand side of a rule is less than some letter in the corresponding left-hand side. We show that the rewrite relation induced by a deleting system can be represented as the composition of a finite substitution (into an extended alphabet), a rewrite relation of an inverse context-free system (over the extended alphabet), and a restriction (to the original alphabet). Here, a system is called inverse context-free if the length of the right-hand side of any rule does not exceed one. The decomposition result directly implies that deleting systems preserve regularity, and that inverse deleting systems preserve context-freeness. The latter result was already obtained by Hibbard (J. ACM 21(3) (1974) 446–453).