Bottom-Up Rewriting Is Inverse Recognizability Preserving
Bottom-Up Rewriting Is Inverse Recognizability Preserving
复制标题
自下而上的重写是逆向可识别性保留
DOI：
10.1007/978-3-540-73449-9_10
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Géraud Sénizergues
中科院分区：
文献类型：
--
作者：
I. Durand;Géraud Sénizergues
对于整类线性项重写系统，我们定义了自下而上重写，这是对通常重写概念的限制。我们证明了自底向上重写有效地保持了可识别性，并分析了底层结构的复杂性。根据定义，自底向上(Bottom-UpClass，BU)是一组线性系统，其每一个导数都可以被自底向上的导数取代。BU的成员资格被证明是不可确定的；因此，我们被引导定义更多的受限类：严格自下而上(K)系统的类SBU(K)，k∈ ℕ，我们证明了对于这些类，成员资格是可确定的。我们用sBu = ∪k∈ ℕsBu(K)定义了严格自底向上系统类。给出了系统在SBU中的一个多项式充分条件。SBU类包含(严格地)几类已知逆保持可识别性的系统。
For the whole class of linear term rewriting systems, we definebottom-up rewritingwhich is a restriction of the usual notion of rewriting. We show that bottom-up rewriting effectively inverse-preserves recognizability and analyze the complexity of the underlying construction. TheBottom-Upclass (BU) is, by definition, the set of linear systems for which every derivation can be replaced by a bottom-up derivation. Membership to BU turns out to be undecidable; we are thus lead to define more restricted classes: the classes SBU(k),k∈ ℕ ofStrongly Bottom-Up(k) systems for which we show that membership is decidable. We define the class ofStrongly Bottom-Upsystems by SBU = ∪k∈ ℕSBU(k). We give a polynomial sufficient condition for a system to be in SBU. The class SBU contains (strictly) several classes of systems which were already known to inverse preserve recognizability.
左线性增长术语重写系统的可判定性
DOI：
--
发表时间：
2002
期刊：
Information and Computation 178
影响因子：
--
作者：
K.Kageyama;S.Kadowaki;Takahito Nagaya
通讯作者：
Takahito Nagaya