本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
具有頂點標籤 t (v) 和集值邊標籤 λ (e) 的有根樹 T 透過設定 δ (x, y) = q（如果 x 和 y 的最後一個共同祖先 lca (x, y) 被標記為 q (x, y) = q（如果 x 和 y 的最後一個共同祖先 lca (x, y) 被標記為 q）來定義 T 的葉子對上的映射 δ 和 ε，並且如果 ∈ ε 到m ∈ ε (x, y)。我們表明，當且僅當存在解釋 δ 的（唯一）最難解析頂點標記樹（Tδ，tδ ）和解釋 ε 的（唯一）最難解析邊標記樹（Tε，λε）（假設兩棵樹都存在）時，一對映射（δ，ε）源自樹（T，t，λ）。如果禁止在關聯頂點和邊上使用某些標籤組合，則此結果仍然成立。