高效计算半稳定扩展的AASExts算法解析

### 高效计算半稳定扩展的AASExts算法解析 #### 1. 命题编码与逻辑约束 在计算半稳定扩展的过程中，涉及到多种命题编码和逻辑约束。以下是一些关键的编码和约束表达式： - **编码表达式**： - \(\{a|a\neq H\}\left(\{b|b\to a\}\neg Ib \vee Oa\right)\) (5) - \(\{a|a\neq H\}\left(Oa \vee \left(\{b|b\to a\}Ib\right)\right)\) (6) - \(\{a|a\neq H\}\left(\{c|c\to a\}\left(Ua \vee \neg Uc \vee \left(\{b|b\to a\}Ib\right)\right)\right)\) (7) - \(\{a|a\neq H\}\left(\left(\{b|b\to a\}(\neg Ua \vee \neg Ib)\right)\wedge \left(\neg Ua \vee \left(\{b|b\to a\}Ub\right)\right)\right)\) (8) - **逻辑约束对应关系**： - \(C1: (1) \wedge (2) \wedge (3) \wedge (4) \wedge (5) \wedge (6) \wedge (7) \wedge (8)\) 对应 \(C^{\varnothing}_{in} \wedge C^{\varnothing}_{out} \wedge C^{\varnothing}_{undec}\) - \(C^{a}_{1}: (1) \wedge (2) \wedge (3) \wedge (4) \wedge (5) \wedge (6)\) 对应 \(C^{\varnothing}_{in} \wedge C^{\varnothing}_{out}\) - \(C^{b}_{1}: (1) \wedge (2) \wedge (5) \wedge (6) \wedge (7) \wedge (8)\) 对应 \(C^{\varnothing}_{out} \wedge C^{\varnothing}_{undec}\) - \(C^{c}_{1}: (1) \wedge (2) \wedge (3) \wedge (4) \wedge (7) \wedge (8)\) 对应 \(C^{\varnothing}_{in} \wedge C^{\varnothing}_{undec}\) - \(C2: (1) \wedge (2) \wedge (4) \wedge (6) \wedge (8)\) 对应 \(C^{\to}_{in} \wedge C^{\to}_{out} \wedge C^{\to}_{undec}\) - \(C3: (1) \wedge (2) \wedge (3) \wedge (5) \wedge (7)\) 对应 \(C^{\leftarrow}_{in} \wedge C^{\leftarrow}_{out} \wedge C^{\leftarrow}_{undec}\) 这里，\(\Pi_{\Gamma}\) 表示给定论证框架 \(\Gamma\) 的任意一种上述编码。对于满足 \(\Pi_{\Gamma}\) 的变量赋值 \(c\)，对应的标签记为 \(Lab_{c} = \langle\{a : Ia \text{ 为真}\}, \{b : Ob \text{ 为真}\}, \{c : Uc \text{ 为真}\}\rangle\)。 #### 2. AASExts算法概述 AASExts 是用于计算半稳定扩展的算法，它基于一些中间理论结果。 - **扩展范围与标签转换**：为了严格扩展完整扩展的范围，即最小化给定完整标签 \(Lab\) 中的未决参数集，需要将一个标签从“未决”转换为“入”或“出”。同时，对于 \(Lab\) 中标记为“入”或“出”的参数，不施加任何约束，这些参数可以自由更改标签，但不能变为“未决”。 - **引理1**：设 \(\Gamma = \langle A, R\rangle\) 是一个论证框架，\(Lab \in L(\Gamma)\) 是一个标签。对于任意 \(Lab' \in L(\Gamma)\)，\(undec(Lab') \subset undec(Lab)\) 当且仅当存在 \(a \in A\) 使得 \(Lab(a) = undec\) 且 \(Lab'(a) \in \{in, out\}\)，并且存在 \(b \in A\) 使得 \(Lab(b) \neq undec\) 且 \(Lab'(b) = undec\)。 - **引理2**：设 \(\Gamma = \langle A, R\rangle\) 是一个论证框架，\(Lab \in L(\Gamma)\) 是一个半稳定标签。那么 \(\{Lab'|Lab' \text{ 是半稳定的且 } undec(Lab') = undec(Lab)\} = \{Lab'|Lab' \text{ 是完整的且 } undec(Lab') = undec(Lab)\}\)。 #### 3. 相关算法实现 - **STExts算法**：用于计算稳定扩展，其伪代码如下： ```plaintext Algorithm 1. STExts Input: Γ = ⟨A, R⟩ Output: Est = EST(Γ) ⊆ 2^A 1: Est := ∅ 2: for each st ∈ ALLSS(ΠΓ ∧ ⋀_{a∈A}¬Ua) do 3: Est := Est ∪ {I A(st)} 4: end for 5: return Est ``` - **AASExts算法**：其伪代码如下： ```plaintext Algorithm 2. AASExts Input: Γ = ⟨A, R⟩ Output: Esem = ESST(Γ) ⊆ 2^A 1: Esem := STExts(⟨A, R⟩) 2: if Esem ```