摘要
arXiv:2410.07708v2 类别替换
摘要:解释为什么一棵树 \(t\) 在结构上不同于另一棵树 \(t^\star\),这是一个在计算机科学中经常遇到的问题,包括在理解树形结构数据(如XML或JSON数据)时。在本文中,我们探讨了如何从样本数据中学习解释树之间的结构差异的方法:假设我们给定了一个由树对 \(\{(t_1, t_1^\star), \dots, (t_n, t_n^\star)\}\) 组成的集合;是否存在一组简单的规则可以解释所有树对 \((t_i, t_i^\star)\) 之间的结构差异?这一问题提出了两个研究方向:(i)在这种情况下,“规则”的良好定义是什么?;和(ii)如何通过算法学习能够解释数据集的规则集?
我们从数据库理论的角度来探索这些问题,具体包括:(1)引入一种基于模式的规范语言来描述树的转换;(2)探讨上述算法问题变种的计算复杂性,例如显示具有高度限制条件的变种为NP难问题;以及(3)讨论如何使用SAT求解器来解决来自计算机科学教育研究的数据问题。