Search

We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a family of recently-discovered decidable logics involving "Presburger quantifiers". We show how to use these logics to measure the expressiveness of classes of GNNs, in some cases getting exact correspondences between the expressiveness of logics and GNNs. We also employ the logics, and the techniques used to analyze them, to obtain decision procedures for verification problems over GNNs. We complement this with undecidability results for static analysis problems involving the logics, as well as for GNN verification problems.

We present an alternative proof of the NEXP-hardness of the satisfiability of {\em Dependency Quantified Boolean Formulas} (DQBF). Besides being simple, our proof also gives us a general method to reduce NEXP-complete problems to DQBF. We demonstrate its utility by presenting explicit reductions from a wide variety of NEXP-complete problems to DQBF such as (succinctly represented) 3-colorability, Hamiltonian cycle, set packing and subset-sum as well as NEXP-complete logics such as the Bernays-Sch\"onfinkel-Ramsey class, the two-variable logic and the monadic class. Our results show the vast applications of DQBF solvers which recently have gathered a lot of attention among researchers., Comment: To appear in the proceedings of FMCAD 2022

We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of incoming blue edges plus twice the number of outgoing red edges is at most three times the number of incoming green edges" and captures various description logics with counting, but without constant symbols. We show that the satisfiability problem for this logic is EXP-complete. While the lower bound already holds for the standard two-variable guarded fragment logic, the upper bound is established by a novel, yet simple deterministic graph-based algorithm.

During the last decades, a lot of effort was put into identifying decidable fragments of first-order logic. Such efforts gave birth, among the others, to the two-variable fragment and the guarded fragment, depending on the type of restriction imposed on formulae from the language. Despite the success of the mentioned logics in areas like formal verification and knowledge representation, such first-order fragments are too weak to express even the simplest statistical constraints, required for modelling of influence networks or in statistical reasoning. In this work we investigate the extensions of these classical decidable logics with percentage quantifiers, specifying how frequently a formula is satisfied in the indented model. We show, surprisingly, that all the mentioned decidable fragments become undecidable under such extension, sharpening the existing results in the literature. Our negative results are supplemented by decidability of the two-variable guarded fragment with even more expressive counting, namely Presburger constraints. Our results can be applied to infer decidability of various modal and description logics, e.g. Presburger Modal Logics with Converse or ALCI, with expressive cardinality constraints., Comment: To appear in FSTTCS 2021

We revisit the satisfiability problem for two-variable logic, denoted by SAT(FO2), which is known to be NEXP-complete. The upper bound is usually derived from its well known Exponential Size Model (ESM) property. Whether it can be determinized efficiently is still an open question. In this paper we present a different approach by reducing it to a novel graph-theoretic problem that we call Conditional Independent Set (CIS). We show that CIS is NP-complete and present two simple algorithms for it with run time O(1.4423^n) and O(1.6181^n), where n is the number of vertices in the graph. We also show that unless the "Strong Exponential Time Hypothesis" (SETH) fails, there is no algorithm for CIS with run time O(1.4141^n). We show that without the equality predicate SAT(FO2) is in fact equivalent to CIS in succinct representation. This yields two algorithms for SAT(FO2) without the equality predicate with run time O(1.4423^{2^n}) and O(1.6181^{2^n}), where n is the number of predicates. To the best of our knowledge, these are the first exact algorithms for an NEXP-complete decidable logic with run time significantly lower than O(2^{2^n}). We also identify a few lower complexity fragments of FO2 which correspond to the tractable fragments of CIS. Similar to CIS, unless SETH fails, there is no algorithm for SAT(FO2) with run time O(1.4141^{2^n}). For the fragment with the equality predicate, we present a linear time many-one reduction to the fragment without the equality predicate. The reduction yields equi-satisfiable formulas with a small constant blow-up in the number of predicates. Finally, we also perform some small experiments which show that our approach is indeed more promising than the existing method (based on the ESM property). The experiments also show that although theoretically it has the worse run time, the second algorithm in general performs better than the first one.

We consider the extension of two variable logic with quantifiers that state that the number of elements where a formula holds should belong to a given ultimately periodic set. We show that both satisfiability and finite satisfiability of the logic are decidable. We also show that the spectrum of any sentence is definable in Presburger arithmetic. In the process we present several refinements to the ``biregular graph method''. In this method, decidability issues concerning two-variable logics are reduced to questions about Presburger definability of integer vectors associated with partitioned graphs, where nodes in a partition satisfy certain constraints on their in- and out-degrees.

We present another proof for the well-known {\em small model property} of two-variable logic. As far as we know, existing proofs of this property rely heavily on model theoretic concepts. In contrast, ours is purely combinatorial and uses only a very simple counting argument, which we find rather intuitive and elegant.

The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, there is a sentence $\Phi'$ that uses the same number of variables, but only one symmetric binary relation, such that its spectrum is linearly proportional to the spectrum of $\Phi$. Moreover, the models of $\Phi'$ are all bipartite graphs. As a corollary, we obtain that to settle Asser's conjecture, i.e., whether the class of spectra is closed under complement, it is sufficient to consider only sentences using only three variables whose models are restricted to undirected bipartite graphs.

We propose a novel automata model over the alphabet of rational numbers, which we call register automata over the rationals (RA-Q). It reads a sequence of rational numbers and outputs another rational number. RA-Q is an extension of the well-known register automata (RA) over infinite alphabets, which are finite automata equipped with a finite number of registers/variables for storing values. Like in the standard RA, the RA-Q model allows both equality and ordering tests between values. It, moreover, allows to perform linear arithmetic between certain variables. The model is quite expressive: in addition to the standard RA, it also generalizes other well-known models such as affine programs and arithmetic circuits. The main feature of RA-Q is that despite the use of linear arithmetic, the so-called invariant problem---a generalization of the standard non-emptiness problem---is decidable. We also investigate other natural decision problems, namely, commutativity, equivalence, and reachability. For deterministic RA-Q, commutativity and equivalence are polynomial-time inter-reducible with the invariant problem.

The purpose of this study was to examine hidden prejudice in two groups of adult students, international and American, against black compared to white teachers. Social desirability in the minds of participants may affect the result of a study involving racial bias (Mullins, 1982). For this reason, the researchers created a computer protocol using the standard Implicit Association Test (IAT) to measure the implicit attitudes of participants. The IAT relies on the idea of automatic information process within the mind that is not impacted by social desirability. A clear concern in education is that the racial bias toward minority students will let those implicit biases affect the way they teach those students, creating a self-fulfilling prophesy of poor student performance. But the implicit bias can work both ways and can impact a teacher's effectiveness. Traditional racial prejudice theories usually looked at white's attitudes toward blacks and other groups. This study had a significant directional shift by focusing on the international students' racial attitudes toward black and white teachers. The implicit racial attitudes of international students were also compared to those of American students. The result and evaluation of this study may be a valuable tool to improve student services and teacher professional development in higher education. Suggestions for future research are also provided.[For full proceedings, see ED570489.]

While services such as Amazon AWS make computing power abundantly available, adding more computing nodes can incur high costs in, for instance, pay-as-you-go plans while not always significantly improving the net running time (aka wall-clock time) of queries. In this work, we provide algorithms for parallel evaluation of SGF queries in MapReduce that optimize total time, while retaining low net time. Not only can SGF queries specify all semi-join reducers, but also more expressive queries involving disjunction and negation. Since SGF queries can be seen as Boolean combinations of (potentially nested) semi-joins, we introduce a novel multi-semi-join (MSJ) MapReduce operator that enables the evaluation of a set of semi-joins in one job. We use this operator to obtain parallel query plans for SGF queries that outvalue sequential plans w.r.t. net time and provide additional optimizations aimed at minimizing total time without severely affecting net time. Even though the latter optimizations are NP-hard, we present effective greedy algorithms. Our experiments, conducted using our own implementation Gumbo on top of Hadoop, confirm the usefulness of parallel query plans, and the effectiveness and scalability of our optimizations, all with a significant improvement over Pig and Hive., Comment: added Gumbo code reference, added Subset Sum reference, adjusted alignment in Figure 1, adjusted Figure 5 (remove redundant units, larger font), removed capitals in Table 2, boxes for environment ends, clarified proof in appendix, reference cleanup (pages, capitalization), uncapitalized "REQUEST" and "ASSERT" when used in text, small rewordings (no results affected)

We consider expressions built up from binary relation names using the operators union, composition, and set difference. We show that it is undecidable to test whether a given such expression $e$ is finitely satisfiable, i.e., whether there exist finite binary relations that can be substituted for the relation names so that $e$ evaluates to a nonempty result. This result already holds in restriction to expressions that mention just a single relation name, and where the difference operator can be nested at most once.

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variable. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations., Comment: 13 pages

The {\em spectrum} of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using only two variables, but allowing counting quantifiers, the spectra of first-order logic sentences are semilinear and hence, closed under complement. At the heart of our proof are semilinear characterisations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices. Our proof also provides a simple characterisation of models of two-variable logic with counting -- that is, up to renaming and extending the relation names, they are simply a collection of regular and biregular graphs., Comment: 30 pages

Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction model for reasoning tasks on {XML} and verification. However, most existing approaches consider the case where only equality test can be performed on the data values. In this paper we study data trees in which the data values come from a linearly ordered domain, and in addition to equality test, we can test whether the data value in a node is greater than the one in another node. We introduce an automata model for them which we call ordered-data tree automata (ODTA), provide its logical characterisation, and prove that its non-emptiness problem is decidable in 3-NEXPTIME. We also show that the two-variable logic on unranked trees, studied by Bojanczyk, Muscholl, Schwentick and Segoufin in 2009, corresponds precisely to a special subclass of this automata model. Then we define a slightly weaker version of ODTA, which we call weak ODTA, and provide its logical characterisation. The complexity of the non-emptiness problem drops to NP. However, a number of existing formalisms and models studied in the literature can be captured already by weak ODTA. We also show that the definition of ODTA can be easily modified, to the case where the data values come from a tree-like partially ordered domain, such as strings.

Let D denote an infinite alphabet -- a set that consists of infinitely many symbols. A word w = a_0 b_0 a_1 b_1 ... a_n b_n of even length over D can be viewed as a directed graph G_w whose vertices are the symbols that appear in w, and the edges are (a_0,b_0),(a_1,b_1),...,(a_n,b_n). For a positive integer m, define a language R_m such that a word w = a_0 b_0 ... a_n b_n is in R_m if and only if there is a path in the graph G_w of length <= m from the vertex a_0 to the vertex b_n. We establish the following hierarchy theorem for pebble automata over infinite alphabet. For every positive integer k, (i) there exists a k-pebble automaton that accepts the language R_{2^k-1}; (ii) there is no k-pebble automaton that accepts the language R_{2^{k+1} - 2}. Based on this result, we establish a number of previously unknown relations among some classes of languages over infinite alphabets.

We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (semantically) a restriction of data automata, introduced by Bojanczyk, et. al. in 2006, therefore it is called weak data automata. It is strictly less expressive than data automata and the expressive power is incomparable with register automata. The expressive power of weak data automata corresponds exactly to existential monadic second order logic with successor +1 and data value equality \sim, EMSO2(+1,\sim). It follows from previous work, David, et. al. in 2010, that the nonemptiness problem for weak data automata can be decided in 2-NEXPTIME. Furthermore, we study weak B\"uchi automata on data omega-strings. They can be characterized by the extension of EMSO2(+1,\sim) with existential quantifiers for infinite sets. Finally, the same complexity bound for its nonemptiness problem is established by a nondeterministic polynomial time reduction to the nonemptiness problem of weak data automata., Comment: 21 pages

Recently data trees and data words have received considerable amount of attention in connection with XML reasoning and system verification. These are trees or words that, in addition to labels from a finite alphabet, carry data values from an infinite alphabet (data). In general it is rather hard to obtain logics for data words and trees that are sufficiently expressive, but still have reasonable complexity for the satisfiability problem. In this paper we extend and study the notion of B\"uchi automata for omega-words with data. We prove that the emptiness problem for such extension is decidable in elementary complexity. We then apply our result to show the decidability of two kinds of logics for omega-words with data: the two-variable fragment of first-order logic and some extensions of classical linear temporal logic for omega-words with data.

In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is decidable. We also show that it is robust: alternating, nondeterministic and deterministic top view weak PA have the same recognition power. Moreover, this model is strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier., Comment: An extended abstract of this work has been published in the proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2009}, Springer, Lecture Notes in Computer Science 5734, pages 712-723