1,721,133 research outputs found
Topological elementary equivalence of regular semi-algebraic sets in three-dimensional space
No full textWe consider semi-algebraic sets and properties of these sets that are expressible by sentences in first-order logic over the reals. We are interested in first-order properties that are invariant under topological transformations of the ambient space. Two semi-algebraic sets are called topologically elementarily equivalent if they cannot be distinguished by such topological first-order sentences. So far, only semi-algebraic sets in one and two-dimensional space have been considered in this context. Our contribution is a natural characterisation of topological elementary equivalence of regular closed semi-algebraic sets in three-dimensional space, extending a known characterisation for the two-dimensional case. Our characterisation is based on the local topological behaviour of semi-algebraic sets and the key observation that topologically elementarily equivalent sets can be transformed into each other by means of geometric transformations, each of them mapping a set to a first-order indistinguishable one
Topological elementary equivalence of regular semi-algebraic sets in three-dimensional space
No full textWe consider semi-algebraic sets and properties of these sets that are expressible by sentences in first-order logic over the reals. We are interested in first-order properties that are invariant under topological transformations of the ambient space. Two semi-algebraic sets are called topologically elementarily equivalent if they cannot be distinguished by such topological first-order sentences. So far, only semi-algebraic sets in one and two-dimensional space have been considered in this context. Our contribution is a natural characterisation of topological elementary equivalence of regular closed semi-algebraic sets in three-dimensional space, extending a known characterisation for the two-dimensional case. Our characterisation is based on the local topological behaviour of semi-algebraic sets and the key observation that topologically elementarily equivalent sets can be transformed into each other by means of geometric transformations, each of them mapping a set to a first-order indistinguishable one
On the Expressive Power of Query Languages for Matrices
No full textWe investigate the expressive power of MATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation inv for inverting a matrix. In MATLANG + inv we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation eigen for diagonalizing a matrix. It is defined such that for each eigenvalue a set of mutually orthogonal eigenvectors is returned that span the eigenspace of that eigenvalue. We show that inv can be expressed in MATLANG + eigen. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in MATLANG + eigen but not in MATLANG + inv. Finally, the evaluation problem for MATLANG + eigen is shown to be complete for the complexity class ∃R
Relational Completeness of Query Languages for Annotated Databases
No full textAnnotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal with the annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra.Floris Geerts is a postdoctoral researcher of the FWO Vlaanderen and is supported in part by EPSRC GR/S63205/01
On the expressive power of message-passing neural networks as global feature map transformers
No full textWe investigate the power of message-passing neural networks (MPNNs) in their
capacity to transform the numerical features stored in the nodes of their input
graphs. Our focus is on global expressive power, uniformly over all input
graphs, or over graphs of bounded degree with features from a bounded domain.
Accordingly, we introduce the notion of a global feature map transformer
(GFMT). As a yardstick for expressiveness, we use a basic language for GFMTs,
which we call MPLang. Every MPNN can be expressed in MPLang, and our results
clarify to which extent the converse inclusion holds. We consider exact versus
approximate expressiveness; the use of arbitrary activation functions; and the
case where only the ReLU activation function is allowed.Comment: 17 pages, 1 figur
Matrix Query Languages
No full textDue to the importance of linear algebra and matrix operations in data analytics, there has been a renewed interest in developing query languages that combine both standard relational operations and linear algebra operations. We survey aspects of the matrix query language MATLANG and extensions thereof, and connect matrix query languages to classical query languages and arithmetic circuits
Matrix Query Languages
No full textDue to the importance of linear algebra and matrix operations in data analytics, there has been a renewed interest in developing query languages that combine both standard relational operations and linear algebra operations. We survey aspects of the matrix query language MATLANG and extensions thereof, and connect matrix query languages to classical query languages and arithmetic circuits
Making Queries Tractable on Big Data with Preprocessing
Full text linkA query class is traditionally considered tractable if there exists a polynomial-time (PTIME) algorithm to answer its queries. When it comes to big data, however, PTIME algorithms often become infeasible in practice. A traditionaland effective approach to coping with this is to preprocess data off-line, so that queries in the class can be subsequently evaluated on the data efficiently. This paper aims to provide a formal foundation for this approach in terms of computational complexity. (1) We propose a set of -tractable queries, denoted by T0 Q, to characterize classes of queries that can be answered in parallel poly-logarithmic time (NC) after PTIME preprocessing. (2) We show that several natural query classes are -tractable and are feasible on big data. (3) We also study a set TQ of query classes that can be effectively converted to -tractable queries by re-factorizing its data and queries for preprocessing. We introduce a form of NC reductions to characterize such conversions. (4) We show that a natural query class is complete for TQ. (5) We also show that T0 Q ⊂ P unless P = NC, i.e., the set T0 Q of all -tractable queries is properly contained in the set P of all PTIME queries. Nonetheless, TQ = P, i.e., all PTIME query classes can be made -tractable via proper refactorizations. This work is a step towards understanding the tractability of queries in the context of big data
- …
