betaFeedback

WorksComputer Science

On Counting Graphs for Modal Logic with Counting

Abstract

In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.

Introduction

Validity problems in modal logic is relevant in many reasoning tasks: verification of systems, epistemic planning. However, validity problem is rigid in this sense: a formula is valid if it holds in all models. In this paper, we relax the validity problem to model counting and we study the probabilistic validity problem: Is a formula true in a large proportion of models? Is a formula asymptotically true for large models? What is the proportion of models in which a formula holds? First, let us give motivation from a verification problem of graph neural networks (GNNs).

Recently, an exact correspondence between modal logic with counting verifying GNNs has been settled and applied for verifying properties on GNNs ([19], [18], [5]). In this paper, the only thing the reader must know is that each GNN from a large class of GNNs, namely with an eventually constant activation function or let say with truncated ReLU, is equivalent to a formula φGNN\varphi_{\mathrm{GNN}} from a logic called K#K^{\#}, which is a natural extension of graded modal logic with linear arithmetic inequations (see [19], [18], [5]). The notion of equivalence is: a pointed graph G,uG,u is classified positively by the GNN iff φGNN\varphi_{\mathrm{GNN}} holds in G,uG,u.

An example of K#K^{\#}-formula is #p≥#q+2\#p \ge\#q + 2 which means that there are more pp-successors than qq-successors plus two. For instance, the formula #p≥#q+2\#p \ge\#q + 2 is true in the pointed

Figure 1.

graph pp pp pp qq since 3≥1+23 \ge1 + 2.

Verifying GNNs is important in order to understand how they classify data. For instance, we could verify that a GNN recommends a person whenever that person has at least 3 violinist friends, meaning that for all pointed graphs (G,u)(G,u), if the current vertex has at least 3 violinist successors then the GNN classifies (G,u)(G,u) positively. This kind of verification tasks were addressed in [18], and on quantized GNNs in [21] and [8].

However, it is unlikely that a property holds for all GNNs. For instance, it is unlikely that a GNN recommends a person whenever that person has at least 3 violinist friends. The reason is because the concept of recommended persons is a vague concept that is difficult to explain and does not completely match a property as precise as "having at least 3 violinist friends" (written #violinist≥3\#violinist \ge3). The second reason is that there are approximations due to learning process itself, making unlikely that the obtained GNN exactly corresponds to a given property.

However, it is possible that a property like "having at least 3 violinist friends" is a probable explanation of the classification of the GNN. That is why, instead of checking that φ→φGNN\varphi\to\varphi_{\mathrm{GNN}} is valid, we want to compute the probability that φ→φGNN\varphi\to\varphi_{\mathrm{GNN}} holds where φGNN\varphi_{\mathrm{GNN}} is a formula that is true when the GNN recommends the current model, and φ\varphi is a property, e.g. “the person has at least 3 violinist friends", #violinist≥3\#violinist \ge3. We may then conclude that the probability that φ→φGNN\varphi\to\varphi_{\mathrm{GNN}} holds in graph of size 42 is more than 0.8.

Our paper is related to 0-1 law that first-order logic has: any FO-sentence φ\varphi is asymptotically true in large models or false in large models. While specific classes of GNNs have 0-1 law ([2], [1]), this is clearly false for logic K#K^{\#}. Indeed, the limit of the truth of #p≥#q\#p \ge\#q is 1/21/2. This justify the study of computing the probability of a formula φ\varphi given the size of the graph, or counting the number of φ\varphi-models of size nn. As many modal logics have the tree-model property, we also focus on trees and counting the number of trees satisfying φ\varphi given a branching factor.

  • Counting models. We study the complexity of counting φ\varphi-trees/graphs, given formula φ\varphi from logic K#K^{\#} (see Figure 1).

Complexity results about counting trees or graphs

Figure 1 (PDF p. 3). Complexity results about counting trees (nn is the branching factor) or graphs (nn is then the number of vertices).

Convergence. We show that the proportion of φ\varphi-trees does not converge for some φ\varphi. We propose an artificial trick to make it converge.

Outline. In Section 2 we discuss the related work. In Section 3, we recall the formal definition of logic K#K^\#. In Section 4, we define the counting problems we are studying. In Section 5, we provide our complexity results. We also have an implementation using Montecarlo method that samples arbitrary large graphs and trees and gives out the proportion of satisfiability1. In Section 6, we exemplify non-convergence in trees and provide a patch for having convergence. In Section 7, we conclude.

Some parts of the proof of Theorem 28 were obtained by AI, although the authors have come up with the general approach by themselves.

Related Work

The study of convergence of properties when the size of the models goes to infinity goes back to 0-1 law of first-order logic [12], [9]. It means that the proportion of models satisfying a first-order property φ\varphi converges to 0 or 1 when the size nn of the model goes to infinity. In this work, the notion of random graph is given by the Erdős–Rényi random graph model.

Later, Granjean proved that deciding whether the limit is 1 for a given FO property is PSPACE-complete [14]. As modal logic is a syntactic fragment of first-order logic, it also has 0-1 law. But, the computation of the limit of a modal formula is Δ2p\Delta_2^p-complete when the formula is represented by a DAG, and Δ2p,log⁡n\Delta_2^{p,\log n}-complete if represented by a tree (see Theorem 4.6 in [15]), where Δ2p=PNP\Delta_2^p=\mathrm{P}^{\mathrm{NP}} is the class of problems decided in poly-time with an NP oracle, and Δ2p,log⁡n\Delta_2^{p,\log n} is the class of problems decided in poly-time with at most O(log⁡n)O(\log n) queries to some NP oracle.

First-order logic when there are function symbols does not have the 0-1 law but still the proportion of models converges when the size of the model goes to infinity [17].

In literature, there are many logical frameworks developed that deal with boolean combinations of linear inequalities. In [10], the authors have developed a logical framework that expresses probabilities of combination of events in real numbers. In order to do that, they use a boolean combination of linear inequalities to reason. Although they have axiomatised the framework, the underlying model they use is a usual First Order logic model of domains of real numbers.

Counting models has been a major part of modal logic literature. A related work can be [22], where the authors consider Linear Temporal Logics. The paper gives decision versions of counting models: whether a formula has models upto an input bound. The paper proposes procedures for counting word and tree models, each one for when the bound is unary and one for when bound is in binary..

In [23], the authors investigate zero-one law on various coloring and edge probability (proportion) conditions on Markov Logic Networks. They define “regimes” that describe the global structure of the coloring and edge assignment, for example, most vertices are colored using same, etc. They showed results on whether zero-one laws and convergence laws hold depending on such regimes.

In [2], the authors proved 0-1 law for some graph neural networks but with strong assumptions. First, they focus on graph properties while we focus on node properties. But their stronger assumption is that they restrict to classifier that are non-splitting, meaning that the property is not on a limit case (see details in their paper). For instance \\#p \\ge\\#q is a limit case and its probability converges to 1/21/2 while the probability (1+\\epsilon)\\#p \\ge\\#q converges to 1 when the number of successors goes to infinity, when epsilon>0\\epsilon> 0. Compared to them, we consider any K^{\\#}-formula, without non-splitting assumption. However, we also consider truncated ReLU or eventually constant activation functions; setting which corresponds K^{\\#}.

In [1], the authors investigate convergence laws of some classes of GNNs. They prove convergence by sampling large graphs from probabilistic graph models like Erdős–Rényi graphs. However, the GNN architecture they consider do not use summation in message passing, but mean.

Background and Preliminaries

We present a modal logic of counting denoted by K^{\\#}, that was introduced in [18], but also in [4] and and [5] with a first-order syntax. Logic K^{\\#} has the same expressivity than graph neural networks with truncated ReLU as an activation function ([18], [5]).

Kripke model

We recall that a Kripke model is a directed graph like structures with each node having some propositional valuations over a countable set of propositions mathcalP\\mathcal{P}.

Definition 1. A Kripke model is a tuple mathcalM=langleW,R,Vrangle\\mathcal{M}=\\langle W,R,V\\rangle where WW is a finite countable set of worlds, RsubseteqWtimesWR\\subseteq W\\times W is the accessible relation, and V:Wto2mathcalPV:W\\to2^{\\mathcal{P}} is the valuation function. A pointed graph/model mathcalM,s\\mathcal{M},s is a Kripke model and a vertex ss in WW.

Syntax

Fix a countable set of propositions mathcalP\\mathcal{P}. The set of K^{\\#}-formulas varphi\\varphi is defined by the grammar:

\\begin{aligned} \\varphi,\\psi,\\ldots&::= p \\mid\\neg\\psi\\mid\\varphi\\lor\\psi\\mid\\xi\\ge0 \\\\ \\xi,\\xi_1,\\xi_2,\\ldots&::= c \\mid1_{\\varphi} \\mid\\#\\varphi\\mid\\xi_1+\\xi_2 \\mid c\\times\\xi_1 \\end{aligned}

where pinmathcalPp\\in\\mathcal{P}, cc is an integer constant. The non-terminal xi\\xi is for arithmetic expressions. The construction 1varphi1_{\\varphi} is an indicator representing whether varphi\\varphi is true in the current state. The construction \\#\\varphi is the number of varphi\\varphi-successors. We write mathcalP(varphi)\\mathcal{P}(\\varphi) for the set of propositions appearing in varphi\\varphi.

Example 2. Here is a well-formed K^{\\#}-formula: \\varphi=(\\#p\\ge3\\#(\\#r\\ge2))\\land r.

Truth Conditions

The truth conditions M,s⊨φ\mathcal{M},s \models\varphi (formula φ\varphi is true at vertex M,s\mathcal{M},s) is defined as follows.

Definition 3. Given a K#K^{\#}-formula φ\varphi and a Kripke model M=⟨W,R,V⟩\mathcal{M}=\langle W,R,V\rangle, M,s⊨φ\mathcal{M},s\models\varphi is defined by induction on φ\varphi by:

M,s⊨p iff p∈V(s)M,s⊨¬ψ iff M,s⊭ψM,s⊨φ∨ψ iff M,s⊨φ or M,s⊨ψM,s⊨ξ≥0 iff ⟦ξ⟧M,s≥0\begin{aligned} \mathcal{M},s &\models p \text{ iff } p\in V(s)\\ \mathcal{M},s &\models\neg\psi\text{ iff } \mathcal{M},s\not\models\psi\\ \mathcal{M},s &\models\varphi\lor\psi\text{ iff } \mathcal{M},s\models\varphi\text{ or }\mathcal{M},s\models\psi\\ \mathcal{M},s &\models\xi\geq0 \text{ iff } \llbracket\xi\rrbracket_{\mathcal{M},s}\geq0 \end{aligned}
⟦c⟧M,s=c\llbracket c\rrbracket_{\mathcal{M},s}=c
⟦1φ⟧M,s={1if M,s⊨φ,0otherwise\llbracket1_\varphi\rrbracket_{\mathcal{M},s}= \begin{cases} 1 & \text{if }\mathcal{M},s\models\varphi,\\ 0 & \text{otherwise} \end{cases}
⟦#φ⟧M,s=∑t:(s,t)∈R⟦1φ⟧M,t\llbracket\#\varphi\rrbracket_{\mathcal{M},s} = \sum_{t:(s,t)\in R}\llbracket1_\varphi\rrbracket_{\mathcal{M},t}
⟦ξ1+ξ2⟧M,s=⟦ξ1⟧M,s+⟦ξ2⟧M,s\llbracket\xi_1+\xi_2\rrbracket_{\mathcal{M},s} = \llbracket\xi_1\rrbracket_{\mathcal{M},s} + \llbracket\xi_2\rrbracket_{\mathcal{M},s}
⟦c×ξ⟧M,s=c×⟦ξ⟧M,s\llbracket c\times\xi\rrbracket_{\mathcal{M},s} = c\times\llbracket\xi\rrbracket_{\mathcal{M},s}

Figure 1 (PDF p. 5).

Example 4. Consider the following Kripke model and the formula φ\varphi in Example 2 evaluated from the top node pointed with an arrow. Formula φ\varphi holds true in this model from the root node. The root node has rr true in it. Now consider the #p≥3#(#r≥2)\#p\geq3\#(\#r\geq2) part of the formula. Note that, #p=3\#p=3 (s, t and u). Also, consider the successor node where only pp is true (the node t). tt has two successors where rr holds (nodes u and v). Hence #r≥2\#r\geq2 holds in tt. Note that tt is the only successor of root that holds #≥2\#\geq2. Hence #(#r≥2)=1\#(\#r\geq2)=1 at the root. Hence #p≥3#(#r≥2)\#p\geq3\#(\#r\geq2) also holds true at root.

Definition 5 (Modal Depth). The modal depth md(φ)md(\varphi) of formula φ\varphi is defined as:

md(p)=0,md(¬ψ)=md(ψ),md(φ∨ψ)=max⁡(md(φ),md(ψ)),md(ξ≥0)=md(ξ)md(c)=0,md(1φ)=md(φ),md(#φ)=md(φ)+1,md(ξ1+ξ2)=max⁡(md(ξ1),md(ξ2)),md(c×ξ1)=md(ξ1)\begin{aligned} md(p)&=0,\quad md(\neg\psi)=md(\psi),\quad md(\varphi\lor\psi)=\max(md(\varphi),md(\psi)),\quad md(\xi\geq0)=md(\xi)\\ md(c)&=0,\quad md(1_\varphi)=md(\varphi),\quad md(\#\varphi)=md(\varphi)+1,\quad md(\xi_1+\xi_2)=\max(md(\xi_1),md(\xi_2)),\\ md(c\times\xi_1)&=md(\xi_1) \end{aligned}

Intuitively, modal depth is the length of the longest nesting of the modality operator #\#.

Example 6. We have md((#(#p≥#q)≥0)∧(#p≥#q))=2md((\#(\#p\geq\#q)\geq0)\land(\#p\geq\#q))=2. This is because (#(#p≥#q)≥0)(\#(\#p\geq\#q)\geq0) has the maximum modal depth, which is 2.

A subformula of a K#K^{\#}-formula is direct when it does lie under the scope of exactly one #\#-modality. The concept of direct formula is important because we count the number of successors satisfying these direct subformulas to evaluate a formula in the current node. We write Dsf(φ)Dsf(\varphi) for the set of direct subformulas.

Example 7. In the formula φ=(#(#p≥#q)≥0)∧(#r≥#s)\varphi=(\#(\#p\geq\#q)\geq0)\land(\#r\geq\#s), subformulas #p≥#q\#p\geq\#q, rr and ss are direct while pp and qq are not. We have Dsf(φ)={#p≥#q,r,s}Dsf(\varphi)=\{\#p\geq\#q,r,s\}.

Formally Dsf(φ)Dsf(\varphi) is defined as follows.

Definition 8 (Direct Sub formulas). Given a K#K^{\#} formula φ\varphi, the set of direct subformulas Dsf(φ)Dsf(\varphi) is defined by induction on φ\varphi as:

Dsf(p)=∅Dsf(¬ψ)=Dsf(ψ)Dsf(ψ1∨ψ2)=Dsf(ψ1)∪Dsf(ψ2)Dsf(ξ≥0)=S′(ξ)S′(c)=∅S′(1φ)=Dsf(φ)S′(#φ)={φ}S′(ξ1+ξ2)=S′(ξ1)∪S′(ξ2)S′(c×ξ)=S′(ξ)\begin{aligned} Dsf(p)&=\varnothing\\ Dsf(\neg\psi)&=Dsf(\psi)\\ Dsf(\psi_1\lor\psi_2)&=Dsf(\psi_1)\cup Dsf(\psi_2)\\ Dsf(\xi\geq0)&=S'(\xi) \end{aligned} \qquad \begin{aligned} S'(c)&=\varnothing\\ S'(1_\varphi)&=Dsf(\varphi)\\ S'(\#\varphi)&=\{\varphi\}\\ S'(\xi_1+\xi_2)&=S'(\xi_1)\cup S'(\xi_2)\\ S'(c\times\xi)&=S'(\xi) \end{aligned}

Link with other logics

Note that standard modal logic can be expressed in K#K^{\#}: ◊φ\Diamond\varphi is a shorthand for #φ≥1\#\varphi\ge1 (there exists a φ\varphi-successor), while □φ\Box\varphi is a shorthand for ¬◊¬φ\neg\Diamond\neg\varphi. Graded modal logic can also be expressed in K#K^{\#}: ◊≥kφ\Diamond_{\geq k}\varphi is a shorthand for #φ≥k\#\varphi\geq k (there exists at least kk φ\varphi-successor).

Counting models

In this section, we define our counting problems. To do that, we suppose that P\mathcal{P} is finite (otherwise there is already an infinite number of 1-vertex models!).

Counting graphs

We write Gn\mathcal{G}_n for the set of pointed graphs whose domain of size nn. More precisely, we fix the domain to be {s1,…,sn}\{s_1,\ldots,s_n\} and the pointed state is s1s_1, i.e.

Gn:={(M,s1)∣M=(W,R,V) with W={s1,…,sn}}.\mathcal{G}_n := \{(\mathcal{M},s_1) \mid\mathcal{M}=(W,R,V)\text{ with }W=\{s_1,\ldots,s_n\}\}.

We define Gnφ\mathcal{G}_n^\varphi to be the subset pointed graphs in Gn\mathcal{G}_n satisfying formula φ\varphi. When not explicitly said otherwise, we suppose then that P=P(φ)\mathcal{P}=\mathcal{P}(\varphi) i.e. that the set of propositions contains exactly the propositions appearing in φ\varphi.

Example 9. The number of pointed graphs of size 2 on the proposition set {p}\{p\} is 2×2×4×42\times2\times4\times4 (self-loop on 1, self-loop on 2, type of edges between 1 and 2, valuations). There are 4 pointed graphs of size 2 satisfying p∧◊¬p∧□¬pp\land\Diamond\neg p\land\Box\neg p:

Said differently, when we consider P={p}\mathcal{P}=\{p\}, ∣Gnp∧◊¬p∧□¬p∣=4|\mathcal{G}_n^{p\land\Diamond\neg p\land\Box\neg p}|=4.

Then the proportion of pointed graphs of size nn satisfying φ\varphi is defined by:

μn(φ):=∣Gnφ∣∣Gn∣.\mu_n(\varphi):=\frac{|\mathcal{G}_n^\varphi|}{|\mathcal{G}_n|}.

Note that the definition of μn(φ)\mu_n(\varphi) does not depend on P\mathcal{P}, as long as P\mathcal{P} contains the propositions appearing in φ\varphi. As presented in [9], a logical framework L\mathcal{L} is defined to have zero-one law if for any formula φ∈L\varphi\in\mathcal{L}, lim⁡n→∞μn(φ)∈{0,1}\lim_{n\to\infty}\mu_n(\varphi)\in\{0,1\}. As discussed in the introduction, logic K#K^{\#} does not have zero-one law.

Note that ∣Gn∣=2n2+∣P∣×n|\mathcal{G}_n|=2^{n^2+|\mathcal{P}|\times n} (choosing the set of edges and the valuations at each vertex). Thus, computing μn(φ)\mu_n(\varphi) reduces to compute ∣Gnφ∣|\mathcal{G}_n^\varphi|.

Counting trees

Many modal logics have the tree-like model property: if a formula is satisfiable, then it is satisfiable in a pointed tree. That is why it is natural to count the number of trees satisfying a property wrt to the branching factor (i.e. outgoing arity). We define Tn,d\mathcal{T}_{n,d} to be the set of pointed trees of depth dd and branching factor nn. Similarly than for graphs, we define Tn,dφ\mathcal{T}_{n,d}^\varphi to be the subset of pointed trees in Tn,d\mathcal{T}_{n,d} satisfying φ\varphi.

Example 10. Here are the 4 pointed trees of depth 1 with branching factor 2 on the proposition set {p}\{p\} satisfying ◊p∧¬□p\Diamond p\land\neg\Box p: Said differently, when we consider P={p}\mathcal{P}=\{p\}, ∣Tn,1◊p∧¬□p∣=4|\mathcal{T}^{\Diamond p\wedge\neg\Box p}_{n,1}|=4.

We define the proportion of pointed trees of branching factor nn satisfying φ\varphi as follows:

μnτ(φ):=∣Tn,md(φ)φ∣∣Tn,md(φ)∣.\mu_n^{\tau}(\varphi) := \frac{|\mathcal{T}^{\varphi}_{n,md(\varphi)}|}{|\mathcal{T}_{n,md(\varphi)}|}.

In the definition of μnτ(φ)\mu_n^{\tau}(\varphi), we consider trees of depth md(φ)md(\varphi). Note that every vertices after depth md(φ)md(\varphi) is not relevant when evaluating φ\varphi. Again, for computing μnτ(φ)\mu_n^{\tau}(\varphi), it is sufficient to compute Tn,md(φ)φ\mathcal{T}^{\varphi}_{n,md(\varphi)} since ∣Tn,md(φ)∣=2P×(2md(φ)+1−1)|\mathcal{T}_{n,md(\varphi)}|=2^{\mathcal{P}\times(2^{md(\varphi)+1}-1)} (choosing the valuation for each of the 2md(φ)+1−12^{md(\varphi)+1}-1 vertices).

Complexity of Counting models

In this section, we investigate the problem of computing μnτ(φ)\mu_n^{\tau}(\varphi) and μn(φ)\mu_n(\varphi), that is computing ∣Tn,md(φ)φ∣|\mathcal{T}^{\varphi}_{n,md(\varphi)}| and ∣Gnφ∣|\mathcal{G}^{\varphi}_n|.

Complexity of Counting Tree Models

We investigate on calculating the number of trees ∣Tn,md(φ)φ∣|\mathcal{T}^{\varphi}_{n,md(\varphi)}| satisfying some K#K^{\#}-formula φ\varphi.

Definition 11. The Counting-Tree problem is defined as:

  • input: a K#K^{\#}-formula φ\varphi, a number nn (branching factor)

  • output: ∣Tn,md(φ)φ∣|\mathcal{T}^{\varphi}_{n,md(\varphi)}|, the number of pointed tree models (M,s)(\mathcal{M},s), with branching factor nn and depth md(φ)md(\varphi) such that M,s⊨φ\mathcal{M},s\models\varphi.

In this subsection, we prove the following theorem.

Theorem 12. Counting-Tree is in #Pspace, if nn is in binary (and also in unary).

Consider a formula φ\varphi. We now define the notion of local consistency of φ\varphi at a given vertex in a tree. The only information we need is the propositional valuation ν\nu and the number of successors in which each subformula in Dsf⁡(φ)\operatorname{Dsf}(\varphi) is true. That last information is modeled by a function counter⁡:Dsf⁡(φ)→N\operatorname{counter}:\operatorname{Dsf}(\varphi)\to\mathbb{N} that assigns to each subformula ψ∈Dsf⁡(φ)\psi\in\operatorname{Dsf}(\varphi) by the number of successors in which ψ\psi hold. We now define formally local-consistency of φ\varphi, denoted by (ν,counter⁡)⊨Lφ(\nu,\operatorname{counter})\models_L\varphi.

Definition 13 (Local Consistency ⊨L\models_L). Consider a formula φ\varphi, a propositional valuation ν\nu over the propositions of φ\varphi, and a function counter⁡:Dsf⁡(φ)→N\operatorname{counter}:\operatorname{Dsf}(\varphi)\to\mathbb{N}. Formula φ\varphi is said to be local-consistent with (ν,counter⁡)(\nu,\operatorname{counter}), denoted by (ν,counter⁡)⊨Lφ(\nu,\operatorname{counter})\models_L\varphi, if φ\varphi holds true after applying the following steps in order:

  1. For each ψ∈Dsf⁡(φ)\psi\in\operatorname{Dsf}(\varphi), replace each non-#\#-nested occurrence #ψ\#\psi in φ\varphi by counter⁡(ψ)\operatorname{counter}(\psi).

  2. Replace each proposition pp left by ν(p)\nu(p).

Example 14. Consider φ:=q∧(#p≥3#(#r≥2))\varphi:=q\wedge(\#p\ge3\#(\#r\ge2)). If ν[q]=1\nu[q]=1, counter⁡(p)=3\operatorname{counter}(p)=3 and counter⁡(r≥2)=1\operatorname{counter}(r\ge2)=1, then φ\varphi is local consistent with (ν,counter⁡)(\nu,\operatorname{counter}) since qq is true (since ν[q]=1\nu[q]=1), #p\#p is replaced by 33, and #(#r≥2)\#(\#r\ge2) is replaced by 11, and 3≥3×13\ge3\times1.

A Dsf(φ\varphi)-valuation VV is a function V:Dsf⁡(φ)→{0,1}V : \operatorname{Dsf}(\varphi) \to\{0,1\}. Furthermore, given a Dsf(φ\varphi)-valuation VV, we define

descr⁡(V)=⋀ψ∣V[ψ]=1ψ∧⋀ψ∣V[ψ]=0¬ψ\operatorname{descr}(V)=\bigwedge_{\psi\mid V[\psi]=1}\psi\land\bigwedge_{\psi\mid V[\psi]=0}\neg\psi

For instance, V(p)=1V(p)=1, V(#r≥2)=0V(\#r\ge2)=0, then descr⁡(V)=p∧¬(#r≥2)\operatorname{descr}(V)=p\land\neg(\#r\ge2). We prove Theorem 12 using Algorithm 2 (guessTree). We prove it by the following facts.

Fact 15. The number of accepting executions of guessTree(φ,n\varphi,n) is ∣Tn,md⁡(φ)φ∣|T_{n,\operatorname{md}(\varphi)}^{\varphi}|.

Proof. Given a K#K^{\#} formula φ\varphi, the set P\mathcal{P} of propositions appearing in φ\varphi, and the branching factor nn, we show that there is a one-to-one correspondence between non-rejecting executions of exploreAllTrees(φ,P,n\varphi,\mathcal{P},n) and trees in Tn,md⁡(φ)φT_{n,\operatorname{md}(\varphi)}^{\varphi}. This sufficient because an accepting execution of guessTree(φ,n\varphi,n) corresponds to a non-rejecting execution of exploreAllTrees(φ,P,n\varphi,\mathcal{P},n).

For that we first formally define, by induction on the modal depth of φ\varphi, a function fφ:NonRejExec⁡exploreAllTrees⁡(φ,P,n)→Tn,md⁡(φ)φf_{\varphi}:\operatorname{NonRejExec}_{\operatorname{exploreAllTrees}(\varphi,\mathcal{P},n)}\to T_{n,\operatorname{md}(\varphi)}^{\varphi} where NonRejExec⁡exploreAllTrees⁡(φ,P,n)\operatorname{NonRejExec}_{\operatorname{exploreAllTrees}(\varphi,\mathcal{P},n)} is the set of non-rejecting paths of exploreAllTrees(φ,P,n\varphi,\mathcal{P},n).

The base case is when φ\varphi is Boolean. By written πν\pi_{\nu} the execution that guessed valuation ν\nu at Line 2, we set fφ(πν)f_{\varphi}(\pi_{\nu}) to the single pointed vertex tagged with the valuation ν\nu. In picture:

fφ(πν)=⟶νf_{\varphi}(\pi_{\nu})=\longrightarrow\nu

Induction case for a formula φ\varphi. In that case, the execution starts by guessing a valuation ν\nu, guess a valuation V1V_{1} over Dsf(φ\varphi), perform an execution π1\pi_{1} at line 11 with descr⁡(V1)\operatorname{descr}(V_{1}), guess a valuation V2V_{2} over Dsf(φ\varphi), perform an execution π2\pi_{2} at line 11 with descr⁡(V2)\operatorname{descr}(V_{2}), etc. Said, differently, the execution is parameterized by (ν,V1,π1,…,Vn,πn)(\nu,V_{1},\pi_{1},\ldots,V_{n},\pi_{n}) and we write π(ν,V1,π1,…,Vn,πn)\pi_{(\nu,V_{1},\pi_{1},\ldots,V_{n},\pi_{n})}. The tree fφ(π(ν,V1,π1,…,Vn,πn))f_{\varphi}(\pi_{(\nu,V_{1},\pi_{1},\ldots,V_{n},\pi_{n})}) is then a root tagged with valuation ν\nu with children corresponding to the sub-executions π1,…,πn\pi_{1},\ldots,\pi_{n}. The child for πi\pi_{i} is obtained via fdescr⁡(Vi)(πi)f_{\operatorname{descr}(V_{i})}(\pi_{i}).

fφ(π(ν,V1,π1,…,Vn,πn))=ν↗↓⋯↘fdescr⁡(V1)(π1)fdescr⁡(V2)(π2)⋯fdescr⁡(Vn)(πn)f_{\varphi}\left(\pi_{(\nu,V_{1},\pi_{1},\ldots,V_{n},\pi_{n})}\right)= \begin{array}{c} \nu\\[-2pt] \nearrow\quad\downarrow\quad\cdots\quad\searrow\\[-2pt] f_{\operatorname{descr}(V_{1})}(\pi_{1})\quad f_{\operatorname{descr}(V_{2})}(\pi_{2})\quad\cdots\quad f_{\operatorname{descr}(V_{n})}(\pi_{n}) \end{array}

Each accepting path corresponds to a satisfying model. In other words, we prove that function ff is a bijection. The proof goes by induction on the modal depth of φ\varphi. The base case, when φ\varphi is Boolean, is straightforward. Now for inductive step, we proceed as follows.

Surjection. Consider a pointed tree model τ∈Tn,md⁡(φ)φ\tau\in T_{n,\operatorname{md}(\varphi)}^{\varphi}. We construct an execution π\pi as follows. First, we guess the valuation ν\nu over P(φ)\mathcal{P}(\varphi) as in the root of τ\tau at Line 6. Now consider child ii among the nn many children of the root. Note that Dsf(φ\varphi) are exactly the sub-formulas of φ\varphi that have exactly one less #-modal depth. Hence, in our execution, we guess the valuation over Dsf(φ\varphi) making exactly the formulas in Dsf(φ\varphi) true in the ii-th child (Line 9 of the ii-th iteration of for loop in Line 8). Hence at that ii-child, desc⁡(V)\operatorname{desc}(V) holds. By induction hypothesis, there exists a non-rejecting execution πi\pi_i for the ii-th call at Line 11. The obtained execution π\pi is π(ν,V1,π1,…,Vn,πn)\pi_{(\nu,V_1,\pi_1,\ldots,V_n,\pi_n)}.

Injection. Take two non-rejecting executions P1≠P2P_1\ne P_2. Hence they differ on at least one of the nondeterministic choice. Just like the surjection proof, since the non-deterministic choices correspond to valuation of either propositions in the root or child nodes, they will correspond to different trees.

Fact 16. exploreAllTrees runs in poly-space.

Proof. The number of nested calls is bounded by the #-modal depth of the initial formula φ\varphi. Remember that the loop at Line 7 takes an exponential time in the size of nn (since nn is in binary), but the memory usage of each recursive call is cleaned after having been performed. The memory used at each call is polynomial in the size of the input: storing the valuation ν\nu and VV is in O(∣φ∣)O(|\varphi|) where φ\varphi is the initial formula. Also, for all ψ∈Dsf⁡(φ)\psi\in\operatorname{Dsf}(\varphi), counter⁡[ψ]≤n\operatorname{counter}[\psi] \le n. So counter⁡[ψ]\operatorname{counter}[\psi] can be represented with O(log⁡n)O(\log n) bits which is of polynomial size to the input.

Algorithm 1  exploreAllTrees
Input: K#-formula φ, P = P(φ) propositions of φ, branching factor n in binary
Output: reject or hand over
1  if φ is Boolean then
2      Guess a valuation ν over P;
3      if ν ⊭ φ then reject ;
4  else
5      Guess a valuation ν over P;
6      counter ← [0]Dsf(φ);
7      for i = 1 . . . n do
8          Guess a valuation V over Dsf(φ);
9          counter[ψ] ← counter[ψ] + 1 for each ψ ∈ Dsf(φ) such that V(ψ) = 1;
10         exploreAllTrees (descr(V), P, n);
11     if (ν, counter) ⊭L φ then reject ;
Algorithm 2  guessTree
Input: K#-formula φ, integer n in binary
Output: accept if exploreAllTrees hands over; reject otherwise
1  exploreAllTrees (φ, n);
2  accept ;

Theorem 17. Given φ\varphi, deciding that ∣T2φ∣≥1|T^{\varphi}_{2}| \ge1 is PSPACE-hard.

Proof. Reduction from the satisfiability problem of standard modal logic in a tree of branching 2 which is PSPACE-hard (this is folklore but stated formally in Lemma 14 of [21]).

Now counting is important. But usually we want to deal with proportions, for instance knowing that μnT(φ)≥1/2\mu^{T}_{n}(\varphi) \ge1/2. This problem reduces to know that ∣Tn,md⁡(φ)φ∣≥∣Tn,md⁡(φ)∣/2|T^{\varphi}_{n,\operatorname{md}(\varphi)}| \ge|T_{n,\operatorname{md}(\varphi)}|/2. More generally, we aim at knowing whether ∣Tn,md⁡(φ)φ∣≥κ|T^{\varphi}_{n,\operatorname{md}(\varphi)}| \ge\kappa. However, there is a trick in the representation of κ\kappa. Indeed, note that κ\kappa represented in binary is not sufficient since ∣Tn,md⁡(φ)∣/2|T_{n,\operatorname{md}(\varphi)}|/2 is 2P×(2md⁡(φ)+1−1)−12^{\mathcal{P} \times(2^{\operatorname{md}(\varphi)+1}-1)-1} which requires an exponential number of bits in ∣φ∣|\varphi| to written down. However, that number is easily represented by 10…0⏟P×(2md⁡(φ)+1−1)−1 numbers of 01\underbrace{0\ldots0}_{\mathcal{P} \times(2^{\operatorname{md}(\varphi)+1}-1)-1\text{ numbers of 0}}. And P×(2md⁡(φ)+1−1)−1\mathcal{P} \times(2^{\operatorname{md}(\varphi)+1}-1)-1 can be written down with a polynomial number of bits. In other words, we represent κ\kappa with a RLE (Run-length encoding) representation where each blocks of 0 and 1 are represented by the digit (0 or 1) and the number of occurrences of that digit.

Theorem 18. Given φ\varphi, nn, κ\kappa, deciding whether ∣T2φ∣≥κ\lvert\mathcal{T}^{\varphi}_{2} \rvert\ge\kappa is in PSPACE, when nn is in binary, and κ\kappa is in RLE compression representation.

Proof. First by Ladner theorem, we have that #PSPACE=FPSPACE\#\mathrm{PSPACE} = \mathrm{FPSPACE} [16]. It means there is a poly-space machine, given φ\varphi, nn, output on a write-only tape the number of trees with branching nn satisfying φ\varphi. Note that this number can have an exponential number of bits. Finally, we compare κ\kappa to that output number on-the-fly (comparing numbers with RLE compression representation can be performed in time O(N2)O(N^{2}) where NN is the size of the RLE compression representation, see [3]).

Complexity of Counting Graph Models

Unlike the previous sections, which deals with K#K^{\#} formulas being interpreted on pointed trees, we now generalise and look at pointed directed graphs. We call this problem as Counting-Graph problem. Formally,

Definition 19 (Counting-Graph). The Counting-Graph problem is defined as

Input: A K#K^{\#} formula φ\varphi, an integer nn

Output: ∣Gnφ∣\lvert\mathcal{G}^{\varphi}_{n} \rvert, the number of pointed nn-state Kripke models that satisfy φ\varphi, where the set of propositions is P=P(φ)\mathcal{P} = \mathcal{P}(\varphi).

In the previous definition, remember that the domain of a Kripke model of size nn is {1,…,n}\{1,\ldots,n\} and that the designated point ss is always 1. We also suppose that the set of propositions is implicitly given by the formula φ\varphi.

Algorithm 3 guessGraph

Input: K#K^{\#}-formula φ\varphi, integer nn in unary

Output: Guess a pointed Kripke model M,s\mathcal{M},s such that ∣M∣=n\lvert\mathcal{M}\rvert= n and accept if M,s⊨φ\mathcal{M},s \models\varphi or reject otherwise

  1. Non-deterministically guess a pointed graph (M,s)(\mathcal{M},s) of nn vertices and on set of propositions P=P(φ)\mathcal{P} = \mathcal{P}(\varphi);

  2. accept if M,s⊨φ\mathcal{M},s \models\varphi else reject ;

Theorem 20. Counting-Graph is #P\# P-complete when nn is given in unary.

Proof.

Upper Bound. Algorithm 3 gives a nondeterministic algorithm guessGraph taking as an input a formula φ\varphi, an integer nn in unary, it guesses an nn-state pointed Kripke model and checks if it satisfies φ\varphi. Each pointed graph (M,s)(\mathcal{M},s) of nn vertices can be represented by its adjacency matrix and a valuation at each vertex, we suppose here that the designated point ss is always the first one. So there are 2n2+n×∣P∣2^{n^{2}+n\times\lvert\mathcal{P}\rvert} possible models of size nn.

Fact 21. guessGraph(φ,n)(\varphi,n) runs in poly-time in ∣φ∣\lvert\varphi\rvert, and nn.

Proof. Let us analyze the algorithm.

  • Line 1. This step consists in guessing a binary word of length n2+n×∣P∣n^{2}+n\times\lvert\mathcal{P}\rvert in time n2+n×∣P∣n^{2}+n\times\lvert\mathcal{P}\rvert.

  • Line 2. Checking G,u⊨φG,u \models\varphi is in time poly⁡(∣φ∣,n)\operatorname{poly}(\lvert\varphi\rvert,n).

Fact 22 (correctness). ∣{(M,s)∣M,s⊨φ,∣M∣=n}∣\lvert\{(M,s)\mid M,s\models\varphi,\lvert M\rvert=n\}\rvert is exactly the number of accepting paths of guessGraph(φ,n)(\varphi,n).

Proof. One execution of guessGraph(φ,n)(\varphi,n) is guessing a distinct Kripke model (G,u)(G,u). So the number of accepting executions of of guessGraph(φ,n)(\varphi,n) is ∣Gφn∣\lvert G_\varphi^n\rvert.

Lower Bound. Recall the problem of #SAT of propositional logic is: given a propositional formula φ\varphi, compute the number of valuations that makes φ\varphi true. The problem #SAT is #P-complete [24].

We reduce #SAT problem in poly-time to Counting-Graph as follows. Given a formula φ\varphi, we build the Counting-Graph instance (φ,n=1)(\varphi,n=1). Note that the reduction is in poly-time. Finally, we have: #SAT(φ)=k(\varphi)=k iff ∣Gφ1∣=k\lvert G_\varphi^1\rvert=k.

The same Algorithm 3 gives an exponential blow-up in the upper bound when nn in binary.

Theorem 23. Counting-Graph(φ,n)(\varphi,n) is in #Exptime when nn is given in binary.

Theorem 24. Given φ,n\varphi,n, deciding whether ∣Gφn∣≥1\lvert G_\varphi^n\rvert\ge1 is Pspace-hard when nn is in binary.

Proof. By reduction from satisfiability problem of standard modal logic in a tree of branching 2 which is PSPACE-hard. Let φ\varphi be a formula of standard modal logic. Take nn to be the size of trees with branching 2 of depth d=md(φ)d=md(\varphi), i.e. n=2d−1n=2^d-1. Take a formula τ\tau that says that the model contains a tree of branching factor 2. Typically, τ\tau is the formula

⋀i=0d−1□i(¬ℓ0∧…∧¬ℓi−1∧ℓi∧¬ℓi+1∧…∧ℓd−1)∧(◊xi∧◊¬xi∧⋀j<i(xj→□xj)∧(¬xj→□xj))\bigwedge_{i=0}^{d-1}\Box^i(\neg\ell_0\land\ldots\land\neg\ell_{i-1}\land\ell_i\land\neg\ell_{i+1}\land\ldots\land\ell_{d-1})\land(\Diamond x_i\land\Diamond\neg x_i\land\bigwedge_{j<i}(x_j\to\Box x_j)\land(\neg x_j\to\Box x_j))

where ℓ0,…,ℓd−1,x0,…,xd−1\ell_0,\ldots,\ell_{d-1},x_0,\ldots,x_{d-1} are fresh propositions (see [7]). The idea of τ\tau is that there is a 2-branching over the Boolean value of xix_i while values of xjx_j with j<ij<i are propagated. Leaves correspond to all valuations over x0,…,xd−1x_0,\ldots,x_{d-1}. The proposition ℓi\ell_i means that we are at level ii. The reduction is tr(φ):=(φ∧τ,n)tr(\varphi):=(\varphi\land\tau,n). If φ\varphi is satisfiable in a tree of branching 2, then φ∧τ\varphi\land\tau is satisfiable in a tree of branching 2 which is a graph of size nn. Conversely, if φ∧τ\varphi\land\tau is true in a graph of size nn, then that graph must be a tree of branching 2.

Theoretical results at infinity

We now study the convergence of μnT(φ)\mu_n^T(\varphi) when the branching factor nn goes to infinity.

Counterexample for convergence

In this subsection, we come up with an example of a K#K^{\#} formula φ\varphi such that lim⁡n→∞μnT(φ)\lim_{n\to\infty}\mu_n^T(\varphi) does not exist. Our candidate formula φ\varphi is #φe≥#φo\#\varphi_e\ge\#\varphi_o where φe\varphi_e and φo\varphi_o are:

φe:=#⊤=2#pφo:=#⊤=2#p−1.\varphi_e:=\#\top=2\#p\qquad\varphi_o:=\#\top=2\#p-1.

Intuitively, φe\varphi_e is a formula that asserts that the number of children to the current tree-node should be exactly twice the number of children where pp holds. In other words, number of children where pp holds is equal to the number of children where it does not. Similarly, φo\varphi_o asserts that the number of children where pp holds is exactly 1 less than the number of children where it does not.

Unfortunately, μnT(#φe≥#φo)\mu_n^T(\#\varphi_e\ge\#\varphi_o) does not converge when nn goes to infinity: its value flips between 1 and numbers that are converging to 0; see Figure 2.

Values of $\mu_n^T(\#\varphi_e \ge \#\varphi_o)$ depending on the branching factor $n$

Figure 2. Values of μnT(#φe≥#φo)\mu_n^T(\#\varphi_e \ge\#\varphi_o) depending on the branching factor nn.

Proposition 25. lim⁡n→∞μnT(#φe≥#φo)\lim_{n\to\infty}\mu_n^T(\#\varphi_e\ge\#\varphi_o) does not exist.

Proof. We only consider trees with depth 2. This is because the formula has modal depth of 2, hence cannot evaluate nodes that lie deeper. We also treat the probability of a tree node holding pp true to be equally likely: a fair coin toss. Hence, each leaf node (depth 2) represents one independent fair coin toss. Each node in the level above (depth 1) represents an experiment that involves exactly nn many independent coin tosses. It is in this level where we evaluate the event space of the experiment based on φe\varphi_e or φo\varphi_o. Lastly, in the root (depth 0), we compare the count of the event spaces. Let us compute the probability of (#φe≥#φo)(\#\varphi_e \ge\#\varphi_o) depending on the parity of the branching factor.

  • Even branching. When the branching is even, φo\varphi_o is false. There, #φo\#\varphi_o is always 0. Thus, formula #φe≥#φo\#\varphi_e \ge\#\varphi_o is trivially true. Thus we have, μ2nT(#φe≥#φo)=1\mu^T_{2n}(\#\varphi_e \ge\#\varphi_o) = 1.

  • Odd branching. As #φe\#\varphi_e is zero when the branching is odd, by definition μ2n−1T(#φe≥#φo)\mu^T_{2n-1}(\#\varphi_e \ge\#\varphi_o) is the probability that #φo=0\#\varphi_o = 0. Now, the probability that φo\varphi_o holds in a node is ((2n−1n))/22n−1(\binom{2n-1}{n})/2^{2n-1} (the probability of nn among 2n−12n-1 trials). So the probability of #φo=0\#\varphi_o = 0 is the probability of having φo\varphi_o false 2n−12n-1 times. So

μ2n−1T(#φe≥#φo):=(1−(2n−1n)22n−1)2n−1\mu^T_{2n-1}(\#\varphi_e \ge\#\varphi_o) := \left(1-\frac{\binom{2n-1}{n}}{2^{2n-1}}\right)^{2n-1}

which tends to 0 when nn tends to +∞+\infty (see appendix § 7).

Alternative definition of the limit

The following theorem gives a limit result for the probability of a formula φ\varphi to be true when the number of successors nn goes to infinity. Computing the limit of μnT(φ)\mu^T_n(\varphi) directly causes technical issues that we will discuss after the following theorem.

The technical solution we propose to study a limit result works as follows. Instead of taking the limit of μnT(φ)\mu^T_n(\varphi) when nn goes to infinity, we propose nn going to infinity at each level in the tree, and define a new quantity denoted by μn′(φ)\mu'_n(\varphi). The base case is when φ\varphi is Boolean. In that case, μn′(φ):=μnT(φ)\mu'_n(\varphi) := \mu^T_n(\varphi) is constant and thus trivially lim⁡n→+∞μn′(φ)\lim_{n\to+\infty}\mu'_n(\varphi) exists. Now for the inductive case, we define μn′(φ)\mu'_n(\varphi) as the limit when the branching factor at the root goes to infinity, provided that a direct subformula ψ\psi is true with probability lim⁡n→+∞μn′(ψ)\lim_{n\to+\infty}\mu'_n(\psi) which exists by induction.

It turns out that we define μn′(φ)\mu'_n(\varphi) inside the following theorem because the existence lim⁡n→+∞μn′(ψ)\lim_{n\to+\infty}\mu'_n(\psi) for the direct subformulas ψ\psi is actually the conclusion of the theorem: lim⁡n→+∞μn′(φ)\lim_{n\to+\infty}\mu'_n(\varphi) exists.

Observe that for all formulas φ\varphi of modal depth 1, μn′(φ)=μnT(φ)\mu'_n(\varphi)=\mu^T_n(\varphi).

Definition 26. We define μn′(φ)\mu'_n(\varphi) by induction on φ\varphi to be the probability that a rooted tree of the form

Figure 1 (PDF p. 13).

such that for all ψ∈Dsf⁡(φ)\psi\in\operatorname{Dsf}(\varphi), the probability that some successor satisfies ψ\psi is lim⁡n→+∞μn′(ψ)\lim_{n \to+\infty} \mu'_n(\psi).

The previous definition is well-formed because of the following theorem, and we kept the definition apart from the theorem for better clarity. If the limit lim⁡n→+∞μn′(φ)\lim_{n \to+\infty} \mu'_n(\varphi) exists, then it is written μ∞′(φ)\mu'_\infty(\varphi).

Example 27. Following the counterexample given in § 6.1, note that μ∞′(#φe≥#φo)\mu'_\infty(\#\varphi_e \ge\#\varphi_o) exists. When the branching factor goes to infinity, the probability that φe\varphi_e holds at the root tends to 0 (it becomes less and less probable to have exactly half of the successors to satisfy pp). Similarly, the probability of φo\varphi_o also tends to 0. Therefore, μ∞′(φe)=μ∞′(φo)=0\mu'_\infty(\varphi_e) = \mu'_\infty(\varphi_o) = 0. Hence, μn′(#φe≥#φo)=1\mu'_n(\#\varphi_e \ge\#\varphi_o) = 1 for any nn. This implies μ∞′(#φe≥#φo)=1\mu'_\infty(\#\varphi_e \ge\#\varphi_o) = 1.

Theorem 28. For all K#K^\#-formulas φ\varphi, lim⁡n→+∞μn′(φ)\lim_{n \to+\infty} \mu'_n(\varphi) exists.

Proof. As per the syntax of K#K^\#, each formula is a boolean combination of literals and linear equations with #ψ\#\psi as variables. Hence, we can write a K#K^\# formula φ\varphi as a DNF:

φ∼⋁j(Sj∧βj)\varphi\sim\bigvee_j (S_j \land\beta_j)

where the SjS_j's are mutually exclusive systems (conjunctions) of inequalities and βj\beta_j is a Boolean formula. Note that βj\beta_j and SjS_j are independent because βj\beta_j is about the current vertex valuation and SjS_j is about the successors.

Example 29. φ:=(#p≥#q)∨(#p≥#r)∧(p∨¬q)\varphi:= (\#p \ge\#q) \lor(\#p \ge\#r) \land(p \lor\lnot q) is rewritten as

[(#p≥#q)∧(#p<#r)]∧(p∨¬q)∨\left[(\#p \ge\#q) \land(\#p < \#r)\right] \land(p \lor\lnot q) \lor
[(#p<#q)∧(#p≥#r)]∧(p∨¬q)∨\left[(\#p < \#q) \land(\#p \ge\#r)\right] \land(p \lor\lnot q) \lor
[(#p≥#q)∧(#p≥#r)]∧(p∨¬q)\left[(\#p \ge\#q) \land(\#p \ge\#r)\right] \land(p \lor\lnot q)

For the rest of the proof, we assume that the given formula φ\varphi is in DNF. The proof proceeds by induction on the #\#-modal depth. For #\#-modal depth 0, the formula is Boolean. Therefore μn′(φ)\mu'_n(\varphi) is constant and thus converges.

Now, we suppose the limits exist for a modal depth d−1d - 1. Consider the formula φ\varphi in DNF of modal depth dd.

Consider the formulas ψ1,ψ2,…ψm∈Dsf⁡(φ)\psi_1, \psi_2, \ldots\psi_m \in\operatorname{Dsf}(\varphi) such that they occur in φ\varphi as #ψi\#\psi_i for any i∈[1..m]i \in[1..m]. By induction, μn′(ψi)\mu'_n(\psi_i) converges to some μ∞′(ψi)\mu'_\infty(\psi_i) when nn goes to +∞+\infty.

We have to prove that μn′(φ)\mu'_n(\varphi) converges to some μ∞′(φ)\mu'_\infty(\varphi) when nn goes to +∞+\infty.

Since φ\varphi is in a DNF form, hence μn′(φ)=∑jμn′(Sj)×μn′(βj)\mu'_n(\varphi) = \sum_j \mu'_n(S_j) \times\mu'_n(\beta_j). As βj\beta_j are propositional, μn′(βj)\mu'_n(\beta_j) is constant. First we prove that if lim⁡n→+∞μn′(Sj)\lim_{n \to+\infty} \mu'_n(S_j) exists for all jj, then lim⁡n→+∞μn′(φ)\lim_{n \to+\infty} \mu'_n(\varphi) exists in the following fact. The rest of the proof becomes proving that lim⁡n→+∞μn′(Sj)\lim_{n \to+\infty} \mu'_n(S_j) exists for all jj.

Fact 30. Let SS be a system of inequalities. Then lim⁡n→+∞μn′(S)\lim_{n \to+\infty} \mu'_n(S) exists.

Proof. For a given nn, and i=1..ni=1..n, and ψ\psi be a (direct) subformula, let Xn,i,ψX_{n,i,\psi} be an indicator random variable such that

Xn,i,ψ={1,if there is a subtree at index i of n children satisfying ψ0,otherwiseX_{n,i,\psi} = \begin{cases} 1, & \text{if there is a subtree at index }i\text{ of }n\text{ children satisfying }\psi\\ 0, & \text{otherwise} \end{cases}

Therefore, P(Xn,i,ψ=1)=lim⁡n→+∞μn′(ψi)=μ∞′(ψi)\mathbb{P}(X_{n,i,\psi}=1)=\lim_{n\to+\infty}\mu'_n(\psi_i)=\mu'_\infty(\psi_i).

Let Nn,ψN_{n,\psi} be the number of successors satisfying ψ\psi among the at most nn successors. Formally, Nn,ψ=∑i=1..nXn,i,ψN_{n,\psi}=\sum_{i=1..n}X_{n,i,\psi}. We define the Dsf⁡(φ)\operatorname{Dsf}(\varphi)-vector Nn:=(⟨Nn,ψ⟩ψ∈Dsf⁡(φ))TN_n:=\left(\langle N_{n,\psi}\rangle_{\psi\in\operatorname{Dsf}(\varphi)}\right)^T, that is a column vector of Dsf⁡(φ)\operatorname{Dsf}(\varphi) dimension. Formally, it is defined by Nn:=∑i=1nXn,i,⋅N_n:=\sum_{i=1}^{n}X_{n,i,\cdot}.

Let kk be the number of inequations in SS. The system SS for branching nn is of the form

ANn≥b(1)AN_n \ge b \tag*{(1)}

where AA is k×Dsf⁡(φ)k\times\operatorname{Dsf}(\varphi)-matrix; bb is a kk dimension column vector. We use a version of Lindeberg-Feller Central Limit theorem [11] to prove the convergence/existence of the limit. Since we have vectors of sum of indicator random variable, we use the Cramer-Wold theorem and Multivariate CLT [6]. For that purpose, we need the covariance matrix of every pair of indicator random variable.

Given a ψ,ψ′∈Dsf⁡(φ)\psi,\psi'\in\operatorname{Dsf}(\varphi), the covariance between Xn,i,ψX_{n,i,\psi} and Xn,j,ψ′X_{n,j,\psi'} for any i,ji,j:

Σψ,ψ′:={P(Xn,i,ψ=1 and Xn,j,ψ′=1)−μ∞′(ψ)×μ∞′(ψ′),if ψ≠ψ′P(Xn,i,ψ=1)(P(Xn,i,ψ=1)),if ψ=ψ′={μ∞′(ψ∧ψ′)−μ∞′(ψ)×μ∞′(ψ′),if ψ≠ψ′μ∞′(ψ)(1−μ∞′(ψ)),if ψ=ψ′(2)\begin{aligned} \Sigma_{\psi,\psi'} &:= \begin{cases} \mathbb{P}(X_{n,i,\psi}=1\text{ and }X_{n,j,\psi'}=1)-\mu'_\infty(\psi)\times\mu'_\infty(\psi'), & \text{if }\psi\ne\psi'\\ \mathbb{P}(X_{n,i,\psi}=1)(\mathbb{P}(X_{n,i,\psi}=1)), & \text{if }\psi=\psi' \end{cases}\\ &= \begin{cases} \mu'_\infty(\psi\wedge\psi')-\mu'_\infty(\psi)\times\mu'_\infty(\psi'), & \text{if }\psi\ne\psi'\\ \mu'_\infty(\psi)(1-\mu'_\infty(\psi)), & \text{if }\psi=\psi' \end{cases} \tag*{(2)} \end{aligned}

Consider the covariance matrix Σ=[Σψ,ψ′]∣Dsf⁡(φ)∣×∣Dsf⁡(φ)∣\Sigma=[\Sigma_{\psi,\psi'}]_{|\operatorname{Dsf}(\varphi)|\times|\operatorname{Dsf}(\varphi)|}.

Since, the setup is a summation of indicator random variables, by applying Cramer-Wold theorem and then translating to Multivariate CLT [6] we get:

Zn:=Nn−nμ′n→n→+∞NDsf⁡(φ)(0,Σ)(3)Z_n:=\frac{N_n-n\mu'}{\sqrt{n}}\xrightarrow[n\to+\infty]{}\mathcal{N}_{\operatorname{Dsf}(\varphi)}(0,\Sigma) \tag*{(3)}

where Σ\Sigma is the covariance matrix whose entries are indexed by Dsf⁡(φ)×Dsf⁡(φ)\operatorname{Dsf}(\varphi)\times\operatorname{Dsf}(\varphi) and are given by (2). NDsf⁡(φ)(0,Σ)\mathcal{N}_{\operatorname{Dsf}(\varphi)}(0,\Sigma) denotes the Normal distribution of ∣Dsf⁡(φ)∣|\operatorname{Dsf}(\varphi)| dimension vectors, whose mean is at 0 and the variance along each of ∣Dsf⁡(φ)∣|\operatorname{Dsf}(\varphi)| dimensions is Σ\Sigma, the covariance matrix.

Since we have our system of inequalities as ANn≥bAN_n\ge b, we rewrite system in (3) as:

AZn≥b−nAμ′n=bn−nAμ′(4)AZ_n\ge\frac{b-nA\mu'}{\sqrt{n}}=\frac{b}{\sqrt{n}}-\sqrt{n}A\mu' \tag*{(4)}

Since as n→∞n\to\infty, the expression bn→0\frac{b}{\sqrt{n}}\to0. Hence the validity of the (4) depends only on Aμ′A\mu'.

Recall that Zn, μ′Z_n,\ \mu' are Dsf⁡(φ)\operatorname{Dsf}(\varphi)-vectors, AA is a k×Dsf⁡(φ)k\times\operatorname{Dsf}(\varphi)-matrix; bb is a kk-vector. Also, the (3) becomes:

AZn→n→+∞Nk(0,AΣAt)(5)AZ_n\xrightarrow[n\to+\infty]{}\mathcal{N}_k(0,A\Sigma A^t) \tag*{(5)}

Since each row in AA are the co-efficients of one inequality in the system, depending on how rows in Aμ′A\mu' (row ii denoted by [Aμ′]i[A\mu']_i) behaves, the convergence of the coordinates of cnc_n can be one of following cases:

  1. If at least for one ii, [Aμ′]i<0[A\mu']_i < 0, then cnc_n converges to +∞+\infty. So system SS is unsatisfiable at the limit. Therefore lim⁡n→∞μn′(S)=0\lim_{n\to\infty}\mu'_n(S)=0.

  1. If for all ii, [Aμ′]i>0[A\mu']_i > 0, cnc_n converges to −∞-\infty. Hence AZnAZ_n grows faster than the RHS in (4) as n→∞n \to\infty which implies lim⁡n→∞μn′(S)=1\lim_{n\to\infty}\mu'_n(S)=1

  1. If for every ii, [Aμ′]i=0[A\mu']_i = 0, then cnc_n converges to 00. We have μn′(S)=P(AZn≥bn)\mu'_n(S)=\mathbb{P}(AZ_n \ge\frac{b}{\sqrt{n}}). By Equation (5), AZn→n→+∞Z∼Nk(0,AΣAt)AZ_n \xrightarrow[n\to+\infty]{} Z \sim N_k(0,A\Sigma A^{t}) and since lim⁡n→∞bn=0\lim_{n\to\infty}\frac{b}{\sqrt{n}}=0, by Portmanteau theorem [6]:

μ∞′(S)=lim⁡n→∞P(ANn≥b)=lim⁡n→∞P(AZn≥bn)=P(AZ≥0),\begin{aligned} \mu'_{\infty}(S) &= \lim_{n\to\infty}\mathbb{P}(AN_n \ge b)\\ &= \lim_{n\to\infty}\mathbb{P}\left(AZ_n \ge\frac{b}{\sqrt{n}}\right)\\ &= \mathbb{P}(AZ \ge0), \end{aligned}

applying Portmanteau theorem

Example 31. With system #p≥5∧#q≥2\#p \ge5 \wedge\#q \ge2, we have matrix A=(1001)A=\begin{pmatrix}1&0\\0&1\end{pmatrix} and μ′=(1/21/2)\mu'=\begin{pmatrix}1/2\\1/2\end{pmatrix}. Thus we are in case 2 and all the constraints can be ignored. We are left with a matrix of "relevant" constraints of size 0×00\times0. Thus μ(φ)=1\mu(\varphi)=1.

Example 32. With system #p−#q≥5∧2#p−3#r≥2\#p-\#q \ge5\wedge2\#p-3\#r \ge2, we have matrix A=(1−123)A=\begin{pmatrix}1&-1\\2&3\end{pmatrix} and μ′=(1/21/2)\mu'=\begin{pmatrix}1/2\\1/2\end{pmatrix}, thus Aμ′=(0−1/2)A\mu'=\begin{pmatrix}0\\-1/2\end{pmatrix}. As the second coordinate of Aμ′A\mu' is negative, we are in point 1 and μ(φ)=0\mu(\varphi)=0.

Example 33. With system #p−#q≥5∧3#p−2#r≥2\#p-\#q \ge5\wedge3\#p-2\#r \ge2, we have matrix A=(1−132)A=\begin{pmatrix}1&-1\\3&2\end{pmatrix} and μ′=(1/21/2)\mu'=\begin{pmatrix}1/2\\1/2\end{pmatrix}, thus Aμ′=(01/2)A\mu'=\begin{pmatrix}0\\1/2\end{pmatrix}. As the second coordinate of Aμ′A\mu' is positive, so we can ignore the second constraint. At the limit, system #p−#q≥5∧3#p−2#r≥2\#p-\#q \ge5\wedge3\#p-2\#r \ge2 has the same probability to be true than system #p−#q≥5\#p-\#q \ge5. The limit probability is P(Z1−Z2≥0)\mathbb{P}(Z_1-Z_2 \ge0) where ZZ is a 2-dimensional normal distribution. Since Z1−Z2Z_1-Z_2 is a standard normal distribution, P(Z1−Z2≥0)=1/2\mathbb{P}(Z_1-Z_2 \ge0)=1/2.

Example 34. With system #p−#q≥5∧#p−#r≥2\#p-\#q \ge5\wedge\#p-\#r \ge2, we have matrix A=(1−1010−1)A=\begin{pmatrix}1&-1&0\\1&0&-1\end{pmatrix} and μ′=(1/21/21/2)\mu'=\begin{pmatrix}1/2\\1/2\\1/2\end{pmatrix}, thus Aμ′=(00)A\mu'=\begin{pmatrix}0\\0\end{pmatrix}.

Probability that are reached

In this section, we study the value of the limit probability μ∞T(φ)=lim⁡n→+∞μnT(φ)\mu^\mathsf{T}_{\infty}(\varphi)=\lim_{n\to+\infty}\mu^\mathsf{T}_{n}(\varphi) that exists and can be reached by some K#K^{\#}-formula φ\varphi. Let us recall Sheppard’s Formula.

Lemma 35 (Sheppard’s Formula [20]). Let Z1,Z2Z_1, Z_2 be standard 1-dimension Gaussian random variables with correlation E[Z1Z2]=ρ∈[−1,1]E[Z_1Z_2]=\rho\in[-1,1]. Then

Pr⁡[Z1≤0,Z2≤0]=12−12arccos⁡ρπ\Pr[Z_1 \le0, Z_2 \le0] = \frac{1}{2} - \frac{1}{2}\frac{\arccos\rho}{\pi}

Proposition 36. For all numbers x∈[0,1/2]x \in[0,1/2], there is a sequence of a K#K^{\#}-formula φ0,φ1,…\varphi_0,\varphi_1,\ldots that are systems with two inequalities such that μ∞T(φn)→x\mu^{\mathrm{T}}_{\infty}(\varphi_n) \to x.

Proof. Given a matrix AA with two rows A1A_1 and A2A_2 let us compute Pr⁡(AZ≥0)\Pr(AZ \ge0). According to Sheppard’s formula, Pr⁡(AZ≥0)=12−12arccos⁡ρπ\Pr(AZ \ge0)=\frac{1}{2}-\frac{1}{2}\frac{\arccos\rho}{\pi} where ρ=A1⋅A2∥A1∥∥A2∥\rho=\frac{A_1\cdot A_2}{\lVert A_1\rVert\lVert A_2\rVert}. We can make approximate all values for ρ\rho between [−1,1][-1,1] with arbitrary big matrices AA. Since arccos⁡ρ∈[0,π]\arccos\rho\in[0,\pi], all values of [0,1/2][0,1/2] can be approximated by Pr⁡(AZ≥0)\Pr(AZ \ge0).

The probability μ∞T(φ)\mu^{\mathrm{T}}_{\infty}(\varphi) over K#K^{\#}-formulas φ\varphi can get arbitrarily close to any number in [0,1][0,1] as stressed by the following proposition.

Proposition 37. For all x∈[0,1]x \in[0,1], for all ϵ>0\epsilon> 0, there is a K#K^{\#}-formula φ\varphi such that ∣μ∞T(φ)−x∣<ϵ|\mu^{\mathrm{T}}_{\infty}(\varphi)-x|<\epsilon.

Proof. We prove the statement using the fact that the set of dyadic rationals {k2m∣k∈N∪{0},m∈N,0≤k≤2m}\left\{\frac{k}{2^m}\mid k \in\mathbb{N}\cup\{0\},m \in\mathbb{N},0 \le k \le2^m\right\} is dense in [0,1][0,1]. So for all x∈[0,1]x \in[0,1], for all ϵ>0\epsilon> 0, there is m,km,k such that ∣x−k2m∣<ϵ\left|x-\frac{k}{2^m}\right|<\epsilon. We now give a formula φ\varphi with μ∞T(φ)=k2m\mu^{\mathrm{T}}_{\infty}(\varphi)=\frac{k}{2^m}. Consider

φ:=⋁j=1…k⋀i=1…m(#pi,j≤#qi,j)\varphi:= \bigvee_{j=1\ldots k}\bigwedge_{i=1\ldots m}(\#p_{i,j}\le\#q_{i,j})

where pi,jp_{i,j} and qi,jq_{i,j} are distinct propositional variables. Since each propositions are independent and μ∞T(#pi,j≥#qi,j)=1/2\mu^{\mathrm{T}}_{\infty}(\#p_{i,j}\ge\#q_{i,j})=1/2, the ANDs product the probabilities and the ORs adds the probabilities up.

Conjecture 38. lim⁡n→+∞μn′(φ)\lim_{n\to+\infty}\mu'_n(\varphi) is equal to some adherence point of (μnT(φ))n∈N(\mu^{\mathrm{T}}_n(\varphi))_{n\in\mathbb{N}}.

Open problems

This work opens the path of studying convergence on general graphs and not only trees, as done in § 6. We finish our work by listing some open problems.

  • How to decide when μn(φ)\mu_n(\varphi) converges? Is it decidable? What is the complexity of that decision problem? Are there some approximation algorithms? These questions are relevant to solve verification problems of GNNs for large graphs. In fact, we conjecture that a fragment, we call majority logic, with a boolean bias condition can have 0-1 law. (for more details, see Appendix)

  • How to put proportion information in the logic and construct a proof system for reasoning about proportions of models? The answer to this research question may provide a tool for giving justifications of some verification verdict.

  • How to compute conditioned proportion? For instance how to compute the proportion of φ\varphi-models among the ψ\psi-models? This is relevant for more involved verification tasks.

Convergence to 0 of μ2n−1(#φe≥#φo)\mu_{2n-1}(\#\varphi_e \ge\#\varphi_o)

Theorem 39.

lim⁡n→∞(1−(2n−1n)22n−1)2n−1=0\lim_{n \to\infty}\left(1-\frac{\binom{2n-1}{n}}{2^{2n-1}}\right)^{2n-1}=0

Proof. Note that:

(2n−1n)=(2n−1)!n!×(n−1)!=n2n(2n)!n!×n!=12(2nn)\begin{aligned} \binom{2n-1}{n}=\frac{(2n-1)!}{n!\times(n-1)!} \\ &=\frac{n}{2n}\frac{(2n)!}{n!\times n!} \\ &=\frac{1}{2}\binom{2n}{n} \end{aligned}

Hence the statement expression becomes

(1−(2n−1n)22n−1)2n−1=(1−(2nn)22n)2n−1\left(1-\frac{\binom{2n-1}{n}}{2^{2n-1}}\right)^{2n-1} = \left(1-\frac{\binom{2n}{n}}{2^{2n}}\right)^{2n-1}

Now we approximate the expression asymptotically. Note that by Stirling’s approximation [13], lim⁡n→∞n!∼2πn(ne)n\lim_{n\to\infty}n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n. Hence,

(2nn)=(2n)!(n!)2∼4πn(2ne)2n(2πn(ne)n)2=22nπn\binom{2n}{n}=\frac{(2n)!}{(n!)^2}\sim\frac{\sqrt{4\pi n}\left(\frac{2n}{e}\right)^{2n}}{\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)^2}=\frac{2^{2n}}{\sqrt{\pi n}}

Therefore, as n→∞n\to\infty:

(2nn)22n=1πn\frac{\binom{2n}{n}}{2^{2n}}=\frac{1}{\sqrt{\pi n}}

As n→∞n\to\infty, let

Ln=(1−(2nn)22n)2n−1=(1−1πn)2n−1L_n=\left(1-\frac{\binom{2n}{n}}{2^{2n}}\right)^{2n-1} =\left(1-\frac{1}{\sqrt{\pi n}}\right)^{2n-1}

Taking logarithms on both sides:

ln⁡Ln=(2n−1)ln⁡(1−1πn)\ln L_n=(2n-1)\ln\left(1-\frac{1}{\sqrt{\pi n}}\right)

As n→∞n\to\infty, 1πn→0\frac{1}{\sqrt{\pi n}}\to0. Also, as x→0x\to0, by Taylor expansion,

ln⁡(1−x)=−x+O(x2)\ln(1-x)=-x+O(x^2)

Hence,

lim⁡n→∞ln⁡Ln=lim⁡n→∞(2n−1)ln⁡(1−1πn)=lim⁡n→∞(2n−1)(−1πn+O(1n))∼lim⁡n→∞−2n−1πn∼lim⁡n→∞−2nπ∼−∞\begin{aligned} \lim_{n\to\infty}\ln L_n =\lim_{n\to\infty}(2n-1)\ln\left(1-\frac{1}{\sqrt{\pi n}}\right) \\ &=\lim_{n\to\infty}(2n-1)\left(-\frac{1}{\sqrt{\pi n}}+O\left(\frac{1}{n}\right)\right) \\ &\sim\lim_{n\to\infty}-\frac{2n-1}{\sqrt{\pi n}} \\ &\sim\lim_{n\to\infty}-\frac{2\sqrt{n}}{\sqrt{\pi}} \\ &\sim-\infty \end{aligned}

Therefore

lim⁡n→∞Ln=e−∞=0\lim_{n \to\infty} L_n = e^{-\infty} = 0

Computations

Computation of proportion of pointed graphs for #p≥#q\#p \ge\#q

The number of graphs of size nn is 4n×2n24^n \times2^{n^2}.

The number of configurations for the successors of a point to satisfy #p≥#q\#p \ge\#q is

∑S⊂{1,…,n}N≥(#S)\sum_{S \subset\{1,\ldots,n\}} N_{\ge}(\#S)

where N≥(m)N_{\ge}(m) is the number of ways to put subsets P,QP,Q in a set of size mm and with #P≥#Q\#P \ge\#Q.

Computation of proportion of pointed graphs for #p≥#q\#p \ge\#q

N≥(m)=4m+(2mm)2.N_{\ge}(m) = \frac{4^m + \binom{2m}{m}}{2}.

The number of configurations is:

∑m=0n(nm)4m+(2mm)2\sum_{m=0}^{n} \binom{n}{m} \frac{4^m + \binom{2m}{m}}{2}

We now also have to consider the choices elsewhere. So the number of models satisfying #p≥#q\#p \ge\#q is:

∑m=0n(nm)4m+(2mm)2×4n−m×2(n−1)n\sum_{m=0}^{n} \binom{n}{m} \frac{4^m + \binom{2m}{m}}{2} \times4^{n-m} \times2^{(n-1)n}

So the probability that #p≥#q\#p \ge\#q holds in a pointed graph of size nn is:

∑m=0n(nm)4m+(2mm)2×4n−m×2(n−1)n4n×2n2.\frac{\sum_{m=0}^{n} \binom{n}{m} \frac{4^m + \binom{2m}{m}}{2} \times4^{n-m} \times2^{(n-1)n}}{4^n \times2^{n^2}}.
∑m=0n(nm)4m+(2mm)4m×2n+1.\sum_{m=0}^{n} \binom{n}{m} \frac{4^m + \binom{2m}{m}}{4^m \times2^{n+1}}.

Computation of proportion of pointed trees for #p≥#q\#p \ge\#q

We compute the probability of satisfying #p≥#q\#p \ge\#q in tree model from the root with number of branching at most BB.

Also, since truth depends on modal depth, we do not care about depth.

Number of trees of at most BB branching with two propositions:

4×∑b=0B(4b)4 \times\sum_{b=0}^{B} (4^b)

From the current node, we just count that given number of branches bb, how many ways can there be valuations such that number of positive #p\#p is at least #q\#q just like above:

4×∑b=0B∑P⊆[0,b], Q⊆[0,b]∣P∣≥∣Q∣14 \times\sum_{b=0}^{B} \sum_{\substack{P \subseteq[0,b],\ Q \subseteq[0,b]\\ |P|\geq|Q|}} 1

By above we have

∑P⊆[0,b], Q⊆[0,b]∣P∣≥∣Q∣1=4b+(2bb)2\sum_{\substack{P \subseteq[0,b],\ Q \subseteq[0,b]\\ |P|\geq|Q|}} 1 = \frac{4^b+\binom{2^b}{b}}{2}

Hence

μB(#p≥#q)=4×∑b=0B4b+(2bb)24×∑b=0B(4b)\mu_B(\#p \geq\#q)=\frac{4\times\sum_{b=0}^{B}\frac{4^b+\binom{2^b}{b}}{2}}{4\times\sum_{b=0}^{B}(4^b)}

A Condition for 0-1 Law for Majority Logic

In this section, we introduce a fragment of K#K^{\#} that we call Majority Logic. The restriction is as follows. The inequations we allow are of the form #φ≥#ψ\#\varphi\geq\#\psi. Majority logic does not have 0-1 law (e.g. μnT(#p≥#q)→n→+∞1/2\mu_n^T(\#p \geq\#q) \xrightarrow[n\to+\infty]{} 1/2). But we introduce a constraint, called full Boolean bias, that gives majority logic 0-1 law back.

Boolean Bias Condition

The idea is to resolve all the Boolean bias. Given P(p1),…,P(pn)\mathbb{P}(p_1),\ldots,\mathbb{P}(p_n), we compute the probability of P(χ)\mathbb{P}(\chi) for a Boolean formula χ\chi by assuming that the truth values of p1,…,pnp_1,\ldots,p_n are independent.

Definition 40. P(p1),…,P(pn)\mathbb{P}(p_1),\ldots,\mathbb{P}(p_n) has full Boolean bias iff for all Boolean formulas χ1,χ2\chi_1,\chi_2, if P(χ1)=P(χ2)\mathbb{P}(\chi_1)=\mathbb{P}(\chi_2) then χ1≡χ2\chi_1\equiv\chi_2.

Example 41 (no full Boolean bias). If P(p)=1/3\mathbb{P}(p)=1/3 and P(q)=1/4\mathbb{P}(q)=1/4, then there is a no full Boolean bias because:

  • P(p∧q)=1/3×1/4\mathbb{P}(p\land q)=1/3\times1/4

  • P(p∧¬q)=1/3×3/4\mathbb{P}(p\land\neg q)=1/3\times3/4

  • P(¬p∧¬q)=2/3×3/4=1/2\mathbb{P}(\neg p\land\neg q)=2/3\times3/4=1/2 (no bias)

  • P(p∨q)=1−1/2=1/2\mathbb{P}(p\lor q)=1-1/2=1/2

Example 42 (full Boolean bias). If P(p)=1/3\mathbb{P}(p)=1/3 and P(q)=1/5\mathbb{P}(q)=1/5, then there is a full Boolean bias because:

  • P(p∧q)=P(p)×P(q)=1/3×1/5\mathbb{P}(p\land q)=\mathbb{P}(p)\times\mathbb{P}(q)=1/3\times1/5

  • P(p∧¬q)=1/3×3/5\mathbb{P}(p\land\neg q)=1/3\times3/5

  • P(¬p∧¬q)=2/3×3/5=2/5\mathbb{P}(\neg p\land\neg q)=2/3\times3/5=2/5

  • P(p∨q)=1−2/5=3/5\mathbb{P}(p\lor q)=1-2/5=3/5

The following is our conjecture:

Conjecture 43. Under the condition full Boolean biais, for all φ\varphi of majority logic,

lim⁡n→+∞μn(φ)∈{0,1}.\lim_{n\to+\infty}\mu_n(\varphi)\in\{0,1\}.

References

  1. [1]Sam Adam-Day, Michael Benedikt, Ismail İlkan Ceylan, and Ben Finkelstein. Almost surely asymptotically constant graph neural networks. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 124843–124886. Curran Associates, Inc., 2024. URL: https://proceedings.neurips.cc/paper_files/paper/2024/file/e1cd1db6fcd4a6df8618259f5b9cca0f-Paper-Conference.pdf, doi:10.52202/079017-3965.
  2. [2]Sam Adam-Day, Theodor-Mihai Iliant, and Ismail İlkan Ceylan. Zero-one laws of graph neural networks. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/dfba85bc32a3cb63a96d1142062b4d8e-Abstract-Conference.html.
  3. [3]Alberto Apostolico, Gad M. Landau, and Steven Skiena. Matching for run-length encoded strings. In Bruno Carpentieri, Alfredo De Santis, Ugo Vaccaro, and James A. Storer, editors, Compression and Complexity of SEQUENCES 1997, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, Proceedings, pages 348–356. IEEE, 1997. doi:10.1109/SEQUEN.1997.666929.
  4. [4]Bartosz Bednarczyk, Maja Orlowska, Anna Pacanowska, and Tony Tan. On classical decidable logics extended with percentage quantifiers and arithmetics. In Mikolaj Bojanczyk and Chandra Chekuri, editors, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, Virtual Conference, December 15-17, 2021, volume 213 of LIPIcs, pages 36:1–36:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.36, doi:10.4230/LIPIcs.FSTTCS.2021.36.
  5. [5]Michael Benedikt, Chia-Hsuan Lu, Boris Motik, and Tony Tan. Decidability of graph neural networks via logical characterizations. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.ICALP.2024.127, doi:10.4230/LIPIcs.ICALP.2024.127.
  6. [6]P. Billingsley. Probability and Measure. Wiley Series in Probability and Statistics. Wiley, 1995. URL: https://books.google.fr/books?id=z39JgQJgAACAAJ.
  7. [7]Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001. doi:10.1017/CBO9781107050884.DOI
  8. [8]Artem Chernobrovkin, Marco Sälzer, François Schwarzentrüber, and Nicolas Troquard. Verifying quantized gnns with readout is decidable but highly intractable. In Renata Wassermann, Marie-Laure Mugnier, and Franz Baader, editors, Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning, KR 2026, Lisbon, Portugal, July 20-23, 2026, 2026. URL: https://doi.org/10.24963/kr.2026/83, doi:10.24963/KR.2026/83.
  9. [9]Ronald Fagin. Probabilities on finite models. J. Symb. Log., 41(1):50–58, 1976. doi:10.1017/S0022481200051756.DOI
  10. [10]Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Inf. Comput., 87(1/2):78–128, 1990. doi:10.1016/0890-5401(90)90060-U.DOI
  11. [11]W. Feller. An Introduction to Probability Theory and Its Applications, Volume 2. Number v. 1-2 in An Introduction to Probability Theory and Its Applications. Wiley, 1957. URL: https://books.google.fr/books?id=BsSwAAAAIAAJ.
  12. [12]Yu V Gleb​skii, Dmitry I Kogan, MI Liogon’kil, and Vladimir A Talanov. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics, 5(2):142–154, 1969.
  13. [13]Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science, 2nd Ed. Addison-Wesley, 1994. URL: https://www-cs-faculty.stanford.edu/%7Eknuth/gkp.html.
  14. [14]Etienne Grandjean. Complexity of the first-order theory of almost all finite structures. Inf. Control., 57(2/3):180–204, 1983. doi:10.1016/S0019-9958(83)80043–6.DOI
  15. [15]Joseph Y. Halpern and Bruce M. Kapron. Zero-one laws for modal logic. Ann. Pure Appl. Log., 69(2-3):157–193, 1994. doi:10.1016/0168-0072(94)90084–1.
  16. [16]Richard E. Ladner. Polynomial space counting problems. SIAM J. Comput., 18(6):1087–1097, 1989. doi:10.1137/0218073.DOI
  17. [17]James F. Lynch. Probabilities of first-order sentences about unary functions. Transactions of the American Mathematical Society, 287(2):543–568, 1985.
  18. [18]Pierre Nunn, Marco Sälzer, François Schwarzen truber, and Nicolas Troquard. A logic for reasoning about aggregate-combine graph neural networks. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 3532–3540. ijcai.org, 2024. URL: https://www.ijcai.org/proceedings/2024/391.arxiv.org/abs/2405.00205
  19. [19]Pierre Nunn and François Schwarzen truber. A modal logic for explaining some graph neural networks. CoRR, abs/2307.05150, 2023. URL: https://doi.org/10.48550/arXiv.2307.05150, arXiv:2307.05150, doi:10.48550/ARXIV.2307.05150.
  20. [20]Ryan O’Donnell. Analysis of boolean functions. CoRR, abs/2105.10386, 2021. URL: https://arxiv.org/abs/2105.10386, arXiv:2105.10386.
  21. [21]Marco Sälzer, François Schwarzen truber, and Nicolas Troquard. Verifying quantized graph neural networks is pspace-complete. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 4660–4668. ijcai.org, 2025. URL: https://doi.org/10.24963/ijcai.2025/519, doi: 10.24963/IJCAI.2025/519.
  22. [22]Hazem Torfah and Martin Zimmermann. The complexity of counting models of linear-time temporal logic, 2014. URL: https://arxiv.org/abs/1408.5752, arXiv:1408.5752.
  23. [23]Yasmin Toussaint and Vera Koponen. Random coloured digraphs defined by a markov logic network. CoRR, abs/2606.23715, 2026. URL: https://doi.org/10.48550/arXiv.2606.23715, arXiv:2606.23715, doi:10.48550/ARXIV.2606.23715.
  24. [24]Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189–201, 1979. doi:10.1016/0304-3975(79)90044–6.DOI

Paper details

vlnc:W_r3nrep8e
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents