Locality of order-invariant first-order formulas
Locality of order-invariant first-order formulas
复制标题
阶不变一阶公式的局部性
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
T. Schwentick
中科院分区：
文献类型：
--
作者：
Martin Grohe;T. Schwentick
如果结构中的元组是否满足该查询的决定仅取决于元组的小邻域，则查询是<italic>局部的</italic>。我们证明了所有的查询表示的<italic>顺序不变的</italic>一阶公式是本地的。
A query is <italic>local</italic> if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by <italic>order-invariant</italic> first-order formulas are local.