Towards a Characterization of Order-Invariant Queries over Tame Structures
Towards a Characterization of Order-Invariant Queries over Tame Structures
复制标题
面向驯服结构的顺序不变查询的表征
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
L. Segoufin
中科院分区：
文献类型：
--
作者：
Michael Benedikt;L. Segoufin
这项工作涉及逻辑在有限结构上的表达能力，并可以访问额外的“任意”线性顺序。可以用这种方式表示的查询是逻辑的顺序不变查询。对于计算机科学中使用的标准逻辑，例如一阶逻辑，已知对任意线性阶的访问增加了逻辑的表达性。然而，当我们观察分离的例子时，我们发现它们具有令人满意的模型，其Gaifman图是复杂的-在价和树宽上无界。因此，我们探索的表达顺序不变的查询图理论上表现良好的结构。我们证明了一阶顺序不变的查询字符串和树有没有额外的表现力超过一阶逻辑的原始签名。我们还证明了新的上界有界树宽和有界价图的顺序不变查询。我们的结果利用一种新的技术的独立利益：应用代数特征的可定义性，以显示崩溃的结果。
This work deals with the expressive power of logics on finite structures with access to an additional “arbitrary” linear order. The queries that can be expressed this way are the order-invariant queries for the logic. For the standard logics used in computer science, such as first-order logic, it is known that access to an arbitrary linear order increases the expressiveness of the logic. However, when we look at the separating examples, we find that they have satisfying models whose Gaifman Graph is complex – unbounded in valence and in treewidth. We thus explore the expressiveness of order-invariant queries over graph-theoretically well-behaved structures. We prove that first-order order-invariant queries over strings and trees have no additional expressiveness over first-order logic in the original signature. We also prove new upper bounds on order-invariant queries over bounded treewidth and bounded valence graphs. Our results make use of a new technique of independent interest: the application of algebraic characterizations of definability to show collapse results.