《Information and Computation》：Relativized codes, finite decodability, and bounded languages
编辑推荐：
一个语言C是相对于L的码（code relative to L），如果L中的每个词都有关于C中词的唯一分解；这是码（code）概念的一个推广。研究人员将此概念推广到d-可解码性（d-decodability，d≥1）以及有限可解码性（finite-decoda
一个语言C是相对于L的码（code relative to L），如果L中的每个词都有关于C中词的唯一分解；这是码（code）概念的一个推广。研究人员将此概念推广到d-可解码性（d-decodability，d≥1）以及有限可解码性（finite-decodability），前者指L中每个词至多有d个关于C中词的分解，后者指每个词至多有有限个这样的分解。研究人员研究了在不同机器模型（分别对应文法模型）接受（生成）的语言上检验该性质的可判定性。随后，研究人员研究了有限可解码性在关于有界语言（bounded languages）的一个新概念——C-有界性（C-boundedness）——中的应用，并由此得到了若干新的、一般的可判定性结果。这些结果蕴含：在任何全三元组（full trio，即对同态、逆同态以及与正则语言交运算有效封闭的语言族）中，判定有限性（finiteness）与判定字母有界性（letter-boundedness）是等价的。最后，研究人员证明了：若C和C′均为有限语言，且L属于某个半线性全三元组（semilinear full trio）并且是C-有界的，则能够判定L是否为C′-有界的。因此，在每个半线性全三元组中，有界性问题的可判定性蕴含对任意有限C的C-有界性问题的可判定性。由此，研究人员得到了对许多语言族（包括带逆转有界计数器的一向非确定下推自动机（one-way pushdown automata augmented with reversal-bounded counters））的C-有界性（C有限）的可判定性。
相对化码、有限可解码性与有界语言：一项统一判定性框架研究
一、研究背景与问题动机
在形式语言与自动机理论中，码（code）是一类具有唯一分解性质的语言：C?中每个词都有且仅有一个关于C的分解。码在信息传输与编码理论中具有基础性地位，其不同变体（如前缀码、中缀码、后缀码）已被广泛研究。然而，经典码的定义要求所有可能消息均具有唯一分解，这一条件在许多实际场景中过于严格。为此，已有两条推广路径：其一，允许每个词至多有d个分解，即d-可解码性（d-decodability）与有限可解码性（finite-decodability）；其二，将唯一分解的要求限制在某个给定语言L上，即相对化码（code relative to L）。本文首次将这两条路径结合，系统研究相对化d-可解码性与相对化有限可解码性的判定问题。
与此同时，有界语言（bounded languages）是形式语言理论中一类重要的语言族，其与包含问题的可判定性存在深刻联系。Hopcroft曾证明：对上下文无关语言L?，判定“给定上下文无关语言L是否满足L??L”可判定当且仅当L?有界。有界性判定问题（boundedness problem）与字母有界性判定问题（letter-boundedness problem）在多种模型上已被研究，但以往结果多依赖针对各模型的特殊技巧。本文引入C-有界性（C-boundedness）概念，将经典有界性（即Σ?-有界性）与字母有界性（即Σ-有界性）统一起来，并建立C-有界性判定与经典有界性判定之间的通用蕴含关系。
二、研究内容与主要结论
本文首先研究相对化d-可解码性的判定问题。研究人员证明：若语言族L对逆同态和与正则语言交运算有效封闭，且具有可判定的空性问题，则给定正则语言C、L∈L及d≥1，判定C是否相对于L为d-可解码是可判定的。这直接蕴含相对化码的判定可判定性。该结果适用于几乎所有具有可判定空性问题的标准机器模型。
其次，研究人员引入C-有界性概念：语言L是C-有界的，若L?w??w?，其中w?,…,w?∈C。经典有界性即Σ?-有界性，字母有界性即Σ-有界性。研究人员证明：在具有可判定有限性问题的全三元组（full trio）中，给定有限语言C和L∈L且C相对于L为码，判定L是否为C-有界是可判定的；同时，给定L∈L和l≥1，判定L是否为Σ^{≤l}-有界也是可判定的。后者可视为有界性问题的有限模拟。
更为重要的是，研究人员证明了如下通用等价关系：在任何全三元组中，判定有限性与判定字母有界性是等价的。这一结果使得矩阵语言（matrix languages）、OI层级（OI hierarchy）等此前需用特殊技巧证明字母有界性可判定的语言族，现在仅需利用闭包性质和有限性判定即可自动获得结论。
最后，研究人员建立了C-有界性与经典有界性之间的判定蕴含关系：若语言族L为半线性全三元组（semilinear full trio）且具有可判定的有界性问题，则对任意有限C，C-有界性问题可判定。进一步，若L∈L是C-有界的（C有限），则对任意给定有限C′，判定L是否为C′-有界也是可判定的。该结果覆盖了上下文无关文法、带逆转有界计数器的一向非确定多计数器机（NCM）以及一向有限转向图灵机等广泛模型。
三、关键技术方法
研究人员采用抽象语言族（Abstract Families of Languages）理论作为统一框架，通过全三元组（对同态、逆同态、与正则语言交运算封闭）的闭包性质进行构造。关键方法包括：构造C^(≥d)与C^(d)正则语言以刻画至少d个分解与恰好d个分解的词；利用非确定广义序列机（gsm）计算count_C(L)（即L中每个词关于C的分解中相邻不同码字个数的集合）；通过Parikh映像与半线性集（semilinear sets）理论处理有界性判定；利用Ginsburg映射将有界语言与半线性集对应。
四、研究结果详解
相对化码的判定性（第3节）
研究人员定义了相对化d-可解码性与相对化有限可解码性，并构造了正则语言C^(≥d)与C^(d)。通过逆同态与正则交运算，将“C是否相对于L为d-可解码”转化为某语言的空性判定。该结果适用于几乎所有具有可判定空性问题的标准模型。值得注意的是，相对化有限可解码性（即d未知时）的判定问题仍是开放的，即使C为有限语言。
C-有界性的基本性质（第4节）
研究人员建立了C-有界性的若干基本性质：C-有界语言对并、连接运算封闭；L是C-有界的当且仅当存在有限D?C使得L?D且mincount_D(L)有限。当C有限时，L是C-有界的当且仅当L?C且mincount_C(L)有限。研究人员通过gsm构造证明：在全三元组中，count_C(L)仍属于该族，从而可利用有限性判定检验count_C(L)是否有限。
特殊情形下的可判定性
研究人员证明：当C相对于L为码时，L是C-有界的当且仅当L?C*且count_C(L)有限，由此获得可判定性。然而，当C仅为2-可解码时，count_C(L)有限不再是充分条件——研究人员构造了C有限、L正则且L是C-有界、C相对于L为2-可解码但count_C(L)无限的例子。这说明了问题的复杂性。随后，研究人员引入e-C-有界性（每个词可用至多e个C中词生成），证明L是e-C-有界的对某个e成立当且仅当L是C-有界的；给定e时，e-C-有界性可判定。
字母有界性与有限性的等价
研究人员证明：在任何全三元组中，判定有限性与判定字母有界性等价。这为矩阵语言、OI层级等语言族提供了字母有界性可判定的统一证明。
半线性全三元组中的C-有界性
研究人员证明：若L为半线性全三元组且具有可判定的有界性问题，则对任意有限C，C-有界性可判定。进一步，若L∈L是C-有界的（C有限），则对任意给定有限C′，判定L是否为C′-有界可判定。这覆盖了NCM、NPCM、k-flip NPDA、有限转向图灵机等模型。
五、讨论与结论
研究人员指出，相对化有限可解码性的判定问题在一般情形下仍是开放的，并建议通过限制L的歧义度来推进。对于C-有界性的一般判定问题（C有限、L属于具有可判定有限性问题的全三元组），当count_C(L)无限时尚无通用判定程序，但本文给出了三个可判定的特殊情形。本文的核心贡献在于建立了C-有界性与经典有界性之间的通用判定蕴含关系：在半线性全三元组中，有界性问题的可判定性自动蕴含任意有限C的C-有界性可判定性。这一统一框架消除了以往针对各模型分别设计特殊证明的必要性，为更广泛语言族的有界性研究提供了通用工具。
