逐步树篱自动机的子树篱投影

### 逐步树篱自动机的子树篱投影 在处理单词、树、树篱或嵌套单词时，投影是一种高效运行自动机的关键技术，它能避免对输入结构中无关部分的评估。尤其在 XML 处理中，投影的重要性更为凸显。本文将深入探讨逐步树篱自动机（SHAs）的子树篱投影技术，介绍相关概念、算法及其实验结果。 #### 1. 引言 投影在自动机处理中起着至关重要的作用，它能帮助我们高效地处理输入结构，避免对无关部分的评估。在 XML 处理领域，投影的重要性已经得到了广泛的认可。许多现有的算法基于嵌套单词自动机（NWAs），并且已经存在高效的投影算法。 然而，近年来的研究发现，逐步树篱自动机（SHAs）在确定性和最早查询回答方面具有重要优势。SHAs 是标准树篱自动机的一种变体，它结合了标准树自动机的自底向上处理和有限单词自动机的从左到右处理。与 NWAs 相比，SHAs 不支持自顶向下处理，也没有显式的栈。 尽管基于确定性 SHAs 的最早查询回答在实践中变得可行，但实验结果表明，它仍然比一些非最早的方法慢。我们认为这是由于缺少用于 SHA 评估的投影算法。因此，本文的目标是开发具有子树篱投影的 SHAs 评估器。 #### 2. 预备知识 在深入探讨 SHAs 之前，我们需要了解一些基本的概念和定义。 - **二元关系**：设 A 和 B 是集合，r ⊆ A × B 是一个二元关系。r 的定义域是 dom(r) = {a ∈ A | ∃b ∈ B. (a, b) ∈ r}。如果 dom(r) = A，则称 r 是全关系。 - **部分函数和全函数**：部分函数 f : A ⇀ B 是一个函数关系 f ⊆ A × B。全函数 f : A → B 是一个部分函数，且是全关系。 - **单词**：设 N 是包括 0 的自然数集合，字母表 Σ 是一个集合。Σ 上的单词集合是 Σ∗ = ∪n∈N Σn。一个长度为 n 的单词 (a1, ..., an) 可以写成 a1 ... an。长度为 0 的空单词用 ε ∈ Σ0 表示，两个单词 v1, v2 ∈ Σ∗ 的连接用 v1 · v2 ∈ Σ∗ 表示。 - **树篱**：树篱是字母和树 ⟨h⟩ 的序列，其中 h 是一个树篱。形式上，树篱 h ∈ HΣ 具有以下抽象语法： ```plaintext h, h′ ∈ HΣ ::= ε | a | ⟨h⟩ | h · h′ ``` 其中 a ∈ Σ。我们假设 ε · h = h · ε = h 且 (h · h1) · h2 = h · (h1 · h2)。因此，任何 Σ∗ 中的单词都可以看作是 HΣ 中的树篱。 - **嵌套单词**：树篱可以与嵌套单词进行识别，即字母表 ˆΣ = Σ ∪ {⟨, ⟩} 上的单词，其中所有括号都是正确嵌套的。这可以通过函数 nw(h) : HΣ → (Σ ∪ {⟨, ⟩})∗ 来实现，具体定义如下： - nw(ε) = ε - nw(⟨h⟩) = ⟨ · nw(h) · ⟩ - nw(a) = a - nw(h · h′) = nw(h) · nw(h′) #### 3. 逐步树篱自动机（SHAs） 逐步树篱自动机（SHAs）是一种用于处理树篱的自动机，它结合了标准树自动机的自底向上处理和有限单词自动机的从左到右处理。 ##### 3.1 定义 一个逐步树篱自动机（SHA）是一个元组 A = (Σ, Q, Δ, I, F)，其中： - Σ 和 Q 是有限集合。 - I, F ⊆ Q 分别是初始状态集和最终状态集。 - Δ = ((aΔ)a∈Σ, ⟨⟩Δ, @Δ) 是转移规则集合，具体如下： - aΔ ⊆ Q × Q 是字母转移规则。 - ⟨⟩Δ ⊆ Q 是树初始规则。 - @Δ : (Q × Q) × Q 是应用规则。 如果 I 和 ⟨⟩Δ 最多包含一个元素，并且所有关系 (aΔ)a∈Σ 和 @Δ 都是部分函数，则称 SHA 是确定性的（dSHA）。 ##### 3.2 转移规则 转移规则有三种形式： - **字母规则**：如果 (q, q′) ∈ aΔ，则写作 q $\xrightarrow{a}$ q′ in Δ。 - **应用规则**：如果 (q, p, q′) ∈ @Δ，则写作 q@p → q′ in Δ。 - **树初始规则**：如果 q ∈ ⟨⟩Δ，则写作 $\xrightarrow{\langle\rangle}$ q in Δ。 对于任何树篱 h ∈ HΣ，我们定义转移关系 $\xrightarrow{h}$ wrt Δ，具体如下： ```plaintext true q $\xrightarrow{\varepsilon}$ q wrt Δ q $\xrightarrow{a}$ q′ in Δ q $\xrightarrow{a}$ q′ wrt Δ q $\xrightarrow{h}$ q′ wrt Δ q′ $\xrightarrow{h′}$ q′′ wrt Δ q $\xrightarrow{h·h′}$ q′′ wrt Δ $\xrightarrow{\langle\rangle}$ q′ in Δ q′ $\xrightarrow{h}$ p q@p → q′′ in Δ q $\xrightarrow{\langle h\rangle}$ q′′ wrt Δ ``` ##### 3.3 接受语言 一个树篱被接受，如果它从某个初始状态开始的转移能够到达某个最终状态。自动机 A 的语言 L(A) 是所有被接受的树篱的集合： ```plaintext L(A) = {h ∈ HΣ | q $\xrightarrow{h}$ q′ wrt Δ, q ∈ I, q′ ∈ F} ``` 对于任何子集 Q ⊆ Q 和树篱 h ∈ HΣ，我们定义内存评估： ```plaintext ⟦h⟧(Q) = {q′ | q $\xrightarrow{h}$ q′ wrt Δ, q ∈ Q} ``` 一个用于判断 h ∈ L(A) 的内存成员测试器可以通过递归应用转移关系计算 ⟦h⟧(I)，并测试其是否包含 F 中的某个最终状态来实现。 #### 4. 向下逐步树篱自动机（SHA↓s） SHAs 仅支持自底向上和从左到右的信息处理。为了实现子树篱投影，我们引入了向下逐步树篱自动机（SHA↓s），它能够自顶向下传递有限状态信息。 ##### 4.1 定义 一个向下逐步树篱自动机（SHA↓）是一个