Layered Transducing Term Rewriting System and Its Recognizability Preserving Property
Layered Transducing Term Rewriting System and Its Recognizability Preserving Property
复制标题
分层转义术语重写系统及其可识别性保持特性
DOI：
10.1007/3-540-45610-4_8
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Y. Kaji
中科院分区：
文献类型：
--
作者：
H. Seki;Toshinori Takai;Youhei Fujinaka;Y. Kaji
有效保持可识别性的项重写系统（EPR-TRS）具有良好的数学性质。本文定义了一个新的TRS子类--分层转换TRS（LT-TRS），并讨论了它的可识别性保持性质。LT-TRS类包含一些EPR-TRS，例如，{f(x)<cd0222a.gif>f（g（x））}，它们不属于EPR-TRS的任何已知的可判定子类。自底向上线性树变换器是LT-TRS的一个特例，是树语言理论中的一种著名计算模型。本文给出了LT-TRS是EPR-TRS的一个充分条件。此外，可达性和可连接性被证明是可判定的LT-TRS。
A term rewriting system which effectively preserves recognizability (EPR-TRS) has good mathematical properties. In this paper, a new subclass of TRSs, layered transducing TRSs (LT-TRSs) is defined and its recognizability preserving property is discussed. The class of LT-TRSs contains some EPR-TRSs, e.g., {f(x)<cd0222a.gif>f(g(x))} which do not belong to any of the known decidable subclasses of EPR-TRSs. Bottom-up linear tree transducer, which is a well-known computation model in the tree language theory, is a special case of LT-TRS. We present a sufficient condition for an LT-TRS to be an EPR-TRS. Also reachability and joinability are shown to be decidable for LT-TRSs.
左线性增长术语重写系统的可判定性
DOI：
--
发表时间：
2002
期刊：
Information and Computation 178
影响因子：
--
作者：
K.Kageyama;S.Kadowaki;Takahito Nagaya
通讯作者：
Takahito Nagaya