自底向上确定性树翻译何时是自顶向下确定性的?
《Theoretical Computer Science》:When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
【字体:
大
中
小
】
时间:2026年09月24日
来源:Theoretical Computer Science 1.1
编辑推荐:
• 我们证明:判断均匀复制确定性自顶向下转换器的前瞻翻译是否可以由同一类中无前瞻但带检查的转换器实现,这是可判定的。
• 我们证明:判断均匀复制确定性自顶向下转换器(无前瞻但带检查)的翻译是否可以由同一类中无检查的转换器实现,这是可判定的。
• 请提供3到5个亮点。
引言
• 我们证明:判断均匀复制确定性自顶向下转换器的前瞻翻译是否可以由同一类中无前瞻但带检查的转换器实现,这是可判定的。
• 我们证明:判断均匀复制确定性自顶向下转换器(无前瞻但带检查)的翻译是否可以由同一类中无检查的转换器实现,这是可判定的。
• 请提供3到5个亮点。
引言
尽管自顶向下和自底向上的树转换器是自20世纪70年代以来就已被深入研究的正式形式(分别由Rounds [1] 和 Thatcher [2] 独立提出,以及由 Thatcher [3] 提出),一些基本问题至今仍悬而未决。这类问题的一个突出例子是:给定一个确定性自底向上树转换器,我们能否判断其翻译是否可以由自顶向下树转换器实现?我们对这一问题给出了肯定回答,但在所考虑的自顶向下树转换器上做了一个轻微限制:它们必须是均匀复制的。这意味着同一输入子树的所有副本必须由同一状态处理。
众所周知,对于每个确定性自底向上树转换器,都可以构造一个等价的确定性自顶向下树转换器,但后者利用了正则前瞻 [7]。该转换器确实具有均匀复制性。因此我们提出的问题是:均匀复制转换器中的正则前瞻能否被消除?我们证明这是可以实现的:给定一个带前瞻的均匀复制(或线性)自顶向下树转换器,判断其是否可以由无前瞻的均匀复制(或线性)自顶向下树转换器实现,这是可判定的。注意,众所周知,所有这些确定性树转换器的等价性是可判定的 [8]。因此,一旦确认等价转换器存在,就可以(通过穷举法)在目标类中找到一个等价转换器。对于我们在更大类中判定某一类转换器的每种情况,我们都提供了更直接的构造方法(但不详细分析构造的运行时间复杂度)。
为了回答这一问题,我们为带前瞻和不带前瞻的均匀复制(以及线性)确定性自顶向下转换器提供了最小最早归一化形式。我们证明,如果一个最早转换器A可以被一个无前瞻(但带输入检查)的转换器A′实现,那么A必须是同步的、配对的和擦除的。要理解同步性质,考虑一个带前瞻的转换器,它将输入树 a(b(f(t?,t?))) 翻译为树 ?a,b?(f(t?,t?)),其中 ?a, b? 是二元输出符号。显然,这种翻译可以由一个无前瞻的转换器完成:它在根节点输出空,将节点标签保存在状态中,并在其子节点输出相应的二元符号。现在考虑 a(b(f(g(t?,t?),t?))) 被翻译为 ?a,b,g?(f(g(t?,t?),t?)) 的情况,其中a可以是b(反之亦然),f可以是g(反之亦然)。这种翻译无法由无前瞻的转换器实现。关于g节点的信息无法在f节点处"同步",因为它在必须产生输出之后才出现(这与输出节点的起源顺序相矛盾 [9],另见 [10],[11])。
配对性质与字符串情况类似 [4](另见 [5],[6]),但现在是针对路径的。要理解擦除性质,考虑一个具有以下规则的转换器:
q?(a(x?:he))→a(a(e))
qid(a(x?:hf))→a(qid(x?))
q?(a(x?:hf))→a(qid(x?))
qid(f)→f
q?(f)→f
这里输入树的形式为 a(?a(e)?) 或 a(?a(f)?)。前瞻自动机有两个状态 he 和 hf,分别表示输入树是第一形式(e叶)还是第二形式(f叶)。该转换器将第一形式的输入树翻译为固定树 a(a(e)),并在第二形式的树上实现恒等映射。这种翻译无法由无前瞻的转换器实现。擦除性质要求:如果某条输入路径依赖于两个不同的前瞻状态 h?、h?,且对于 h? 产生的是常量输出树(即树 a(a(e))),那么对于 h? 在任何循环中不得产生输出。
给定一个同步的、配对的且擦除的带前瞻均匀复制转换器A,我们构造一个等价的带检查的均匀复制转换器(如果存在),即一个均匀复制转换器,其定义域由某个自顶向下确定性树自动机单独给出。
我们贡献的第三个亮点是一个去除检查(如果可以的话)的过程。这里的思路与到目前为止讨论的不同。让我们考虑一个例子。定义域自动机接受形式为 f(t?, t?) 的树,其中 t? 是任意二元树(内部节点标记为 f,叶标记为 a 或 b),t? 是一棵最左叶标记为 a 且最右叶标记为 b 的树。转换器有以下规则:q?(f(x?,x?))→f(f(b,b),qid(x?)),其中状态 qid 实现恒等映射。是否存在一个等价的无检查的自顶向下树转换器?事实证明答案是"是"。其思想是输出子树 f(b,b) 可以用来模拟检查!等价无检查转换器的规则如下:
我们证明,对于给定的自顶向下确定性树语言,判断它能否在给定输出树上被模拟,这是可判定的。现在的挑战在于,可能需要延迟输出某些输出子树,直到遇到需要这些输出树来满足其检查需求的规则。与之前类似,这种延迟只能沿输入路径进行,且当输入节点的两个输入子树被处理时就必须停止。通过使用检查需求的精确抽象解释,我们能够确定是否能提供足够大的输出子树以满足所有所需的检查需求。我们此处概述的方法与之前依赖差分约束的前瞻去除方法 [12] 有很大不同,后者依赖不同前瞻状态之间翻译的差异。然而,为了获得有效的构造,迄今为止引入了一系列技术性限制——这意味着即使是线性确定性自顶向下树转换器,前瞻去除仍然是一个未解决的问题。据我们所知,本文是首次为自顶向下树转换器的自然已知子类提出前瞻去除的论文。
我们的结果是一个可定义性问题的例子,即:给定转换类X、Y,对于每个y∈Y,判断是否存在x∈X使得x等价于y,这是否可判定。过去已考虑过许多此类问题。例如,X和Y可以是语言类,如正则语言和上下文无关语言。在这种情况下,根据Greibach定理 [13],相应的可定义性问题是不可判定的。有趣的是,如果将Y缩减为确定性上下文无关语言(即由确定性下推自动机识别的语言),那么可定义性确实是可判定的 [14]。就树语言而言,这类可判定的可定义性结果是稀少的。一个例子是:给定树同态h和正则树语言R,判断h(R)是否可由正则树语言定义,这是可判定的 [15]。后来该结果被推广到加权设置 [16]。
转换比语言更具刚性,因此更适合可判定的可定义性问题。就字符串转换而言,最近识别出了一个重要的可判定可定义性问题:对于给定的功能双向转换器,判断是否存在等价的一向转换器,这是可判定的 [17]、[18]。就树转换器而言,该结果已被扩展到具有单合输出的属性树转换器 [19]。最近正则字符串转换受到了广泛关注,参见 [20] 等。已证明对于给定的正则字符串转换器,判断其翻译是否具有O(n?)的大小编增长率(对任意给定的k),这是可判定的 [21]。就树转换器而言,已知判断给定确定性宏树转换器的复合是否具有线性大小编增长率 [22];注意在肯定情况下,翻译确实可由MSO转换器(单合二阶逻辑)定义。最近也证明了对于给定宏树转换器,线性高度增加和线性大小对高度增加的可判定性 [23]。
本文是 [24] 的扩展版本,该版本已在ICALP'2020上发表。
摘要片段
基础部分
设Σ表示带排名的字母表。则Σ?是Σ中所有排名为k的符号集合。按照惯例,我们将Σ上所有(有限)树的集合T_Σ定义为所有形如t=f(t?,…,t?)的字符串的集合,其中f∈Σ?(对某个k≥0),且t?,…,t?∈T_Σ。为了方便,当f的排名为0时,我们也将f写作f()。具有该形式的子树也称为叶。设X={x?|i∈N}表示一个与任何其他出现的带排名字母表(无论是输入还是输出字母表)不相交的互异变量无限集合。
uc-转换器建议的最小最早归一化形式
本节我们给出了带建议的uc-转换器和线性转换器的最早归一化形式的构造。以下我们固定某个修剪的无歧义TA B作为建议。对于自顶向下确定性定义域自动机B的最早确定性自顶向下转换器构造已在 [12] 中提供,对于自底向上确定性B已在 [26] 中提供。这里,我们稍微放宽了限制,允许无歧义的B来推广这两种情况。[12]、[26]中的构造对
如何去除前瞻
以下我们假设给定一个带正则前瞻的uc-(或线性)转换器A,即自底向上确定性建议自动机B。根据定理1,我们可以假设A是最小最早的。按照惯例,我们假设A由(Q, B, ι, R, α)给出,其中B=(H,Σ,δ,F)。我们的目标是判断A的翻译是否可以由无前瞻但可能带检查的uc-(或线性)转换器实现。后者的一个必要条件是定义域
如何检查自顶向下确定性语言
现在考虑一个DTuci A,其底层自顶向下确定性自动机B被假设为最小最早的。以下我们用?表示B中具有dom_B(h)=T_Σ的唯一状态h(如果存在这样的状态)。DTuci(DTlini)A没有检查(分别记为DTuc和DTlin)的条件是:对于A的每一条规则q(f(x?:h?,…,x?:h?))→T,每当x?不出现在T中时,h?=?。特别是,当A是非删除的(即A的每条规则的右端都包含所有变量)时,情况就是这样。
如何满足检查需求
以下我们考虑一个任意的DTuci转换器A,其底层自顶向下确定性TA B作为检查自动机。我们回顾,由于B只有一个接受状态,A仅提供一条公理。考虑A中形如q(f(x?:h?,…,x?:h?))→T的规则τ。对于T中不出现的每个x?,必须验证输入中相应的子树包含在dom_B(h?)中。如果h?=?(即dom_B(h?)=T_Σ),则不需要这种验证。相应地,令J_τ表示集
结论
我们证明了对于确定性自顶向下树转换器的两个自然子类(即线性和均匀复制的),如何去除(自底向上确定性)前瞻并在可能的情况下将其替换为(自顶向下确定性)检查。然后我们也证明了对于给定类如何去除检查(如果可能的话)。这些构造在技术上很复杂,但关键在于所研究转换器的最小最早归一化形式。作为推论,我们得到对于a
CRediT作者贡献声明
Sebastian Maneth:写作–审阅与编辑,写作–原始草稿。Helmut Seidl:写作–审阅与编辑,写作–原始草稿。
利益冲突声明
作者声明没有已知的竞争性经济利益或个人关系可能会影响本文报告的工作。
Sebastian Maneth | Helmut Seidl
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号