主题
Search

归约系统


在一个系统中,根据有限的重写规则,形式语言的词语(表达式)可以被转换,这样的系统被称为归约系统。虽然归约系统也称为字符串重写系统项重写系统,但术语“归约系统”更通用。

Lambda 演算是一个归约系统的例子,其中lambda 转换规则构成了其重写规则。

如果归约系统的任何重写规则都不适用于表达式 E,则称 E 对于该归约系统处于范式。

如果表达式对 (x,y) 中的 xy 都可以通过零个或多个归约步骤(即,重写规则的应用)归约到相同的表达式,则称该表达式对是可连接的。

如果 x 在一步中归约到 y,则表示为 x->y。如果 x 在零个或多个步骤中归约到 y,则表示为 x->_*y。如果存在一个序列 {a_0,...,a_n} 使得 a_0=xa_n=y,并且对于每一对 (a_i,a_(i+1)),要么 a_i->a_(i+1) 要么 a_(i+1)->a_i,则使用符号 x<->_*y


另请参阅

Church-Rosser 属性, 合流, 临界对, 有限终止, 形式语言, Knuth-Bendix 完成算法, Lambda 演算, 多向系统, 归约顺序, 字符串重写系统

此条目由 Alex Sakharov 贡献 (作者链接)

使用 探索

参考文献

Baader, F. and Nipkow, T. 项重写及其相关内容。 Cambridge, England: Cambridge University Press, 1999.

在 中被引用

归约系统

请这样引用

萨哈罗夫,亚历克斯. "归约系统." 来自 Web 资源,由 Eric W. Weisstein 创建。 https://mathworld.net.cn/ReductionSystem.html

主题分类