带无序连接和数值约束的正则表达式成员问题研究

### 带无序连接和数值约束的正则表达式成员问题研究 #### 1. 引言 在标准通用标记语言（SGML）的ISO标准中，“&”运算符用于表示无序连接，即语言可以以任意顺序连接。例如，&(ya, basta) 表示 {yabasta, bastaya}。无序连接与交错（interleaving）在表面上相似，但交错用于建模过程理论中的并行组合，且没有明显的方法将交错的算法和复杂度结果转换到无序连接上。 数值约束允许指定子表达式必须匹配的次数范围，例如 (a + b)2..3 表示由 a 和 b 组成的长度为 2 或 3 的单词。数值约束在 XML Schema 和文本搜索应用（如 GNU grep）中都有应用。 本文的研究有理论和实际两方面的动机。理论上，是对无序连接特性的好奇，特别是与数值约束结合使用时。实际中，无序连接在自然语言文本搜索和定义中似乎很有用。对于强 1 - 无歧义的带无序连接和数值约束的正则表达式，成员问题是可处理的。 接下来，我们将研究带无序连接和数值约束的正则表达式及其成员问题。首先给出这些表达式及其语言的定义，然后证明在没有数值约束的情况下，成员问题已经是 NP 完全的。成员问题的算法基于带计数器的有限自动机的构造，其中正则表达式项树中的位置起着核心作用。 #### 2. 带无序连接和数值约束的正则表达式 固定字母表 Σ，假设 a, b, c 是 Σ 的成员，l, l1, l2, ... 作为 Σ 成员的变量。设 N = {1, 2, ...}，N1 = {2, 3, 4, ...} ∪ {∞}，N0 = {0, 1, 2, ...}。 **定义 1**：给定字母表 Σ，RΣ 是带无序连接和数值约束的正则表达式集合，由以下语法定义： RΣ ::= RΣ + RΣ | RΣ · RΣ | RN..N1 Σ |&(RΣ, ... , RΣ) | Σ | ϵ 我们只允许 n ≤ u 时的 rn..u。数值约束优先级最高，其次是连接、选择，无序连接优先级最低。必要时使用括号来分组子表达式。我们用 r, r1, r2, ... 作为正则表达式的变量，连接符号 · 通常省略。 我们使用一些简写：rn.. 表示 rn..∞，r0..n 表示 r1..n + ϵ，r+ 表示 r1..∞，r∗ 表示 r0..，rn 表示 rn..n。用 sym(r) 表示 r 中出现的 Σ 中的字母集合。 无序连接运算符不是二元中缀的，因为它不满足结合律。无星号的带无序连接的正则表达式是 RΣ 中没有数值约束的子集。 我们将单词的连接扩展到单词集合，对于 L1, L2 ⊆ Σ∗，L1 · L2 = {w1 · w2 | w1 ∈ L1 ∧ w2 ∈ L2}。ϵ 表示长度为 0 的空单词。对于 L ⊆ Σ∗，Ln = Ln−1 · L（n > 0）且 L0 = {ϵ}。无序连接的语义通过排列来定义。 **定义 2（语言）**：正则表达式 r ∈ RΣ 表示的语言 ∥r∥ 按以下归纳方式定义： - ∥r1 + r2∥ = ∥r1∥ ∪ ∥r2∥ - ∥r1 · r2∥ = ∥r1∥ · ∥r2∥ - ∥&(r1, ... , rn)∥ = ⋃ σ∈Perm({1,...,n})∥rσ1∥ · · · ∥rσn∥ - ∥rl..u∥ = ⋃ l≤i≤u∥r∥i - 对于 a ∈ Σ ∪ {ϵ}，∥a∥ = {a} 例如，∥&(ab, c)∥ = {abc, cab}，∥&(a, b, c)∥ = {abc, bac, acb, bca, cab, cba}，∥(a + b)1..2∥ = {a, b, aa, ab, ba, bb}。注意无序连接不满足结合律，例如 ∥&(&(a, b), c)∥ ≠ ∥&(a, &(b, c))∥。 #### 3. 无序连接下成员问题的复杂度 成员问题是给定带无序连接的正则表达式 r ∈ RΣ 和单词 w ∈ Σ∗，判断 w 是否属于 ∥r∥，也称为匹配。对于带数值约束（无无序连接）的正则表达式，成员问题已知在 P 中。正则表达式带交错的成员问题的 NP 难性已被证明，但该证明不易修改以适用于无序连接的情况。 不难证明带数值约束和无序连接的正则表达式的成员问题在 NP 中。问题实例的证书包括在正则表达式中做出所有必要的选择，使得可以看出单词在语言中。证书的大小与单词和正则表达式的长度成多项式关系。 为了证明成员问题是 NP 难的，我们从命题公式的可满足性问题进行归约。假设公式有 c 个子句和 v 个变量，我们构造一个正则表达式 r，它是 c + v 个表达式的无序连接。前 c 个表达式每个代表一个子句，正文字面量由自身表示，负文字面量由相应字母重复 c + 1 次表示。最后 v 个表达式，对于每个变量 x，形式为 ((x + ϵ)cxc2) + (xc+1 + ϵ)c。要检查成员资格的单词 w 是 x1c2+c · · · xvc2+c。 **示例 3**：对于公式 (x1 ∨ ¬x2 ∨ ¬x3 ∨ x4) ∧ (x3 ∨ ¬x5 ∨ x6) ∧ (x3 ∨ ¬x6)，v = 6，c = 3，Σ = {x1, x2, x3, x4, x5, x6}。正则表达式为 &((x1 + x4 2 + x4 3 + x4), (x3 + x4 5 + x6), (x3 + x4 6), r1, r2, r3, r4, r5, r6)，其中每个 ri 是 ((xi + ϵ)3x9 i ) + (x4 i + ϵ)3。要检查成员资格的单词是 x12 1 · · · x612。 需要证明成员问题实例仅比命题公式大多项式倍，并且单词在正则表达式的语言中当且仅当命题公式是可满足的。 #### 4. 项树、位置和下标 给定正则表达式 r，我们定义其项树为根节点标记为主运算符（选择、连接或星号），子树为子表达式项树的树。如果 a ∈ Σ ∪ {ϵ}，项树是一个以 a 为标签的单根节点。 我们用 ⟨n1, ... , nk⟩ 表示项树中的位置，p, q 等作为这些位置的变量。根的位置是