Printer Friendly

Subcritical pattern languages for and/or trees.

Let [P.sub.k] (f) denote the density of and/or trees defining a boolean function f within the set of and/or trees with fixed number of variables k. We prove that there exists constant [B.sub.f] such that [P.sub.k](f) ~ [B.sub.f] x [k.sup.-L(f)-1] when k [right arrow] [infinity], where L(f) denote the complexity of f (i.e. the size of a minimal and/or tree defining f). This theorem has been conjectured by Daniele Gardy and Alan Woods together with its counterpart for distribution [pi] defined by some critical Galton-Watson process. Methods presented in this paper can be also applied to prove the analogous property for [pi].

Keywords: And/Or trees, probability distribution for Boolean functions, tree enumeration

1 Introduction

And/or trees are representations of boolean functions built from [conjunction], [disjunction] and positive and negative literals. Let us fix the set of variables to {[x.sub.1], ..., [x.sub.k]}. Since every and/or tree using at most variables {[x.sub.1], ..., [x.sub.k]} defines some boolean function f : [{0, 1}.sup.k] [right arrow] {0, 11}, the uniform probability distribution on the and/or trees of size n induces some probability distribution on the set of all boolean functions of k variables. It has been shown by Lefmann and Savicky in [8] that for every fixed number of variables k when n (the size) tends to infinity the induced distribution on boolean functions converge to some (positive) probability distribution which we denote by [P.sub.k]. The characterization of this limiting probability for big k is still a challenging problem. The authors of [8] suggested to study the relationships between [P.sub.k] (f) and so called complexity of function f which is the size of a minimal and/or tree defining f. They gave some lower and upper bounds for [P.sub.k](f) dependent on the complexity. Although the upper bound have been improved in [1] by Chauvin, Flajolet, Gardy and Gittenberger, the gap is still quite large. The authors of [1] also introduced other interesting distribution on boolean function usually denoted by [pi], which results from some critical Galton-Watson process. The relationships between both distributions are a subject of ongoing research. For the general survey on the research concerning and/or trees we refer to [4].

In the recent paper [5], Gardy and Woods focused on special functions (namely constant function and so called "read-once" functions). For such a function f they analysed behaviour of [P.sub.k](f) when k tends to infinity (in this approach f is treated as a boolean function of countably many variables, even though it depends only on the finite number of them). They stated the following conjecture:

For a "read-once" function f with complexity r, there exist constants [b.sub.f] and [B.sub.f] such that [[pi].sub.k](f) [~.sub.k] [b.sub.f][k.sup.-r] and [P.sub.k](f) [~.sub.k] [B.sub.f][k.sup.-r-1] as k [right arrow] [infinity].

The main result of this paper is a proof of a variant of the conjectured property for all non-constant (not only "read-once") functions, for distributions [P.sub.k]. Due to the lack of space we prove only that [P.sub.k] (f) = [THETA]([k.sup.-r-1). We do not consider distributions [[pi].sub.k]. However, the full generality of the conjecture and the analogous results for the distribution [[pi].sub.k] can be obtained using the similar technique. The main tools we use are "subcritical tree pattern languages" defined in the section 2. As a simple example of applications of this technique, we present (in the subsection 3.2) quite simple proof of the result announced by Woods in [9] that "most of tautologies" are variations of formulae like x [disjunction] [bar.x] [disjunction] [phi].

1.1 Preliminaries

We use [n.sup.[k.bar]] to denote the falling factorial i.e. [n.sup.[k.bar]] = n(n - 1) ... (n - k + 1). For any set of finite objects A we denote by A(n) the number of elements of A of size n. All the trees we use are binary, planar and rooted. A tree language is any set of trees.

Generating functions. In the first part of this paper we make an extensive use of generating functions and singularity analysis (see [2]).

A function f(z) [member of] R[[z]] has singularity of the square root type in [rho] [member of] C if it has Puiseux expansion around [rho] of the form f(z) = [[summation].sub.n [member of] N] [c.sub.n [([rho] - z).sup.n/2] with [c.sub.1] [not equal to] 0. We use the following technical lemma, which is a consequence of the Theorem VII.8 from [2].

Lemma 1.1 Let f(z), g(z) be algebraic generating functions. Suppose that both functions have unique dominating singularities of the square root type in the same point [??] [member of] [R.sub.+]. Then the limit [lim.sub.n [right arrow] [infinity]] [[z.sup.n]]f(z) / [[z.sup.n]]g(z) exists and is positive.

Stirling numbers. After [7] we use the notation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the Stirling number of the second kind. The number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the number of partitions of a set of size n into k nonempty classes (subsets). We are going to use the following property.

Observation 1.2 For a fixed m [member of] N the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a polynomial of d.

Proof: Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the number of partitions of a set of size n into k classes of size at least 2 each. Therefore for any fixed number n we have exactly

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

partitions of a set of size d in which exactly n elements belong to non singleton classes. For a fixed n and m the last equation is easily seen to be polynomial in d.

For every partition of a set of size d into d - m classes there are at most 2m elements which do not belong to singleton classes. It means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a finite sum of polynomials like (1).

Terms. Let Var = {[x.sub.1], [x.sub.2], [x.sub.3], ...} be a countable set of variables. An and/or tree is a planar rooted, binary tree, with internal nodes labelled by connectors [conjunction], [disjunction], and leaves labelled by variables from Var or their negations (denoted by [[bar.x].sub.1]). The set of negated variables is denoted by [bar.Var]. The elements of Var [union] [bar.Var] are called literals. Throughout this paper we use many different kinds of trees, therefore we prefer to call and/or trees terms. The set of all terms is denoted by F.

For every k [member of] [N.sub.1], let [F.sub.k] be the set of all terms in which all used variables belong to the set [Var.sub.k] = {[x.sub.1], ..., [x.sub.k]}.

For a term [psi], the structure of [psi] is a tree which is constructed from [psi] by changing the labelling of all its leaves so that each leaf is labelled by *. The set of all structures is denoted by T. Leaf labelling functions are all the functions of type {1, ..., n} [right arrow] Var [union] [bar.Var] for some n [member of] [N.sub.1]. The leaf labelling of [psi] is the function f : {1, ..., n} [right arrow] Var [union] [bar.Var] such that f(i) is the label of the i-th (e.g. from the left) leaf of [psi]. In most cases we work with terms from [F.sub.k] for some fixed k [member of] [N.sub.1]. Then we consider only labellings of type f : {1, ..., n} [right arrow] [Var.sub.k] [union] [[bar.Var].sub.k].

The size of a structure is the total number of its leaves. The size of a formula is the size of its structure. The size of a labelling function f : {1, ..., n} [right arrow] Var [union] [bar.Var] equals n.

Note, that there is a natural (size-preserving) bijection between terms, and structure-labelling pairs of the same size. Therefore for every k, n [member of] [N.sub.1] we have [F.sub.k](n) = T(n) x [(2k).sup.n].

We denote by t(z) the generating function for the set of structures T. Simple computations show that t(z) = 1/4 (1 - [square root of 1 - 8z]), the radius of convergence is [rho] = 1/8, t(z) has unique square root type singularity in [rho] and t([rho]) = 1/4

Density. Instead of the definition of the distribution [P.sub.k] sketched in the Introduction, we use equivalent approach based on densities. For any set of terms A [subset] [F.sub.k] we consider the limit [lim.sub.n [right arrow] [infinity]] A(n) / [F.sub.k](n). If the limit exists, it is called a density of A in [F.sub.k]. For a fixed boolean function of k variables f let [A.sub.f] denote the set of terms from [F.sub.k] which define function f. It is easy to see that [lim.sub.n [right arrow] [infinity]] [A.sub.f(n) / [F.sub.k](n) = [P.sub.k](f) and the existence of the limit is granted by the result of Lefmann and Savicky from [8]. However, we lose connection with probability distribution on boolean functions when we consider set of terms which are essential subsets of [A.sub.f], while we still can talk about densities of such sets.

2 Pattern languages

A pattern language is any language of (binary, planar, rooted) trees with internal nodes labelled by [conjunction] or [disjunction] and leaves labelled by the elements of {*, [??]}. The leaves labelled by [??] are called placeholders (as opposed to regular leafs). For any tree language T and a pattern language P we define a language P[T] as the language of all trees which can be constructed by substituting all placeholders [??] in some pattern from P by some trees from T. P is unambiguous if for every T, every tree from P[T] can be constructed in only one way. The size of the pattern is the number of its leaves labelled with * (i.e. the number of regular leaves). For d, h [member of] N we denote by P(d, h) the number of elements of P having d regular leaves and h placeholders. For a pattern language P we use bivariate generating function p(x, y) with x marking regular leaves and y marking placeholders (i. e. p(x, y) = [[summation].sub.d [member of] N, h [member of] N] [x.sup.d][y.sup.h] P(d, h)).

For unambiguous P, in every tree t [member of] P[T] we can distinguish set of its nodes (internal or leaves) which correspond to the nodes of pattern used to construct t. We call these nodes P-pattern nodes or simply pattern nodes if the pattern language is clear from the context. E.g. for the pattern [??] [conjunction] [x.sub.1] the term ([x.sub.2] [disjunction] [[bar.x].sub.2]) [conjunction] [x.sub.1], constructed from the pattern by substituting the placeholder by ([x.sub.2] [disjunction] [[bar.x].sub.2]), contains two pattern nodes: the root and the rightmost leaf (labelled by [x.sub.1].)

Observation 2.1 Let P be an unambiguous pattern language, and T be a tree language. Let p(x, y) be the generating function for P, and t(z) for T. Then, the generating function of the language P[T] is p(z, t(z)).

Definition 2.2 Let t(z) be a generating function having unique dominating singularity of the square root type in [rho] [member of] [R.sub.+]. We say that the function p(x, y) is subcritical for t(z) if p(x, y) is analytic in some set {(x, y) : [absolute value of x] [less than or equal to] [rho] + [epsilon], [absolute value of y] [less than or equal to] t([rho]) + [epsilon]}.for some [epsilon] [member of] [R.sub.+].

We say that an unambiguous pattern language P is subcritical for a tree language T if the generating function t(z) of T has unique dominating singularity of the square root type and the generating function p(x, y) of P is subcritical for t(z).

Observation 2.3 Let t(z) be a generating function having unique dominating singularity of the square root type in [rho] [member of] [R.sub.+], and p(x, y) be subcritical for t(z). Suppose that both functions t(z), p(x, y) have nonnegative coefficients as a formal power series. If there exist [upsilon] [member of] N, [eta] [member of] [N.sub.1] for which [[x.sup.[upsilon]] [y.sup.[eta]]]p(x, y) > 0, then the function p(z, t(z)) has unique dominating singularity of the square root type in [rho]. In the opposite case its radius of convergence is strictly greater than [rho].

Proof: The function t(z) is analytically continuable to the set D = {z [member of] C : [absolute value of z] < [rho] + [epsilon]} [[rho], [infinity]]), for some positive [epsilon]. Since the composition of analytic functions is analytic, by subcriticality of p(x, y) we get that the function p(z, t(z)) is analytic in D (for small enough [epsilon]). This shows that p(z, t(z)) can not have singularities in the set [absolute value of z] [less than or equal to] [rho] except for the point [rho].

Suppose that we have [upsilon] [member of] N, [eta] [member of] [N.sub.1] for which [x.sub.[upsilon]] [y.sub.[eta]]]p(x, y) > 0. Then, by nonnegativity we get

[z.sup.n]p(z, t(z)) [greater than or equal to] [[z.sup.n]]t[(z).sup.[eta]][z.sup.[upsilon]], (2)

which shows that the radius of convergence of p(z, t(z)) cannot be greater than [rho]. It means that p(z, t(z)) has unique dominating singularity in [rho].

A composition with analytic function cannot increase the branching type of algebraic singularity, therefore the function p(z, t(z)) has algebraic singularity at [rho] with branching type at most 2. By the fact that p(z, y) is bounded in the neighbourhood of ([rho], t([rho])), we get that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is finite. It means that p(z, t(z)) has in [rho] Puiseux expansion of the form: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If [c.sub.1] = 0, then by the standard algebraic asymptotics (see Theorem VII.8 from [2]) we would obtain that [lim.sub.n [right arrow] [infinity], [[z.sup.n]]p(z, t(z)) / [[z.sup.n]]t(z) = 0, which is impossible according to 2. It means that [c.sub.1] [not equal to] 0, which proves that p(z, t(z)) has singularity of the square root type at [rho].

Suppose now that there are no [upsilon] [member of] N, [eta] [member of] [N.sub.1] for which [[x.sub.[upsilon]] [y.sub.[eta]]]p(x, y) > 0. Then by nonnegativity we get p(z, t(z)) = p(z, 0), but by subcriticality, the radius of convergence of this function is greater then [rho] + [epsilon].

If p(x, y) is subcritical for t(z) then from the complex analysis we know that all partial derivatives [[partial derivative].sup.m]p(x, y) / [([partial derivative]x).sup.m], for m [member of] N are subcritical for t(z) as well. According to the observation above it means that, for every m [member of] N the function [[[partial derivative].sup.m]p(x, y) / [([partial derivative]x).sup.m]|.sub.(z, t(z))] has dominating singularity of the square root type at [rho]. In such a case using the Lemma 1.1 we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some [c.sub.m] [member of] R. Additionally we get that [c.sub.m] is positive whenever there are [upsilon] [member of] N, [eta] [member of] [N.sub.1] for which [[x.sub.[upsilon]] [y.sub.[eta]]] [[[partial derivative].sup.m]p(x, y) / [([partial derivative]x).sup.m] > 0.

2.1 Restrictions

Repetitions. For every term [psi] and any distinguished set of its leaves D we say that [psi] has m-repetitions among the leaves from D, if m equals the difference between the number of leaves in D and the number of distinct variables which occurs in these leaves (e.g. there are 3 repetitions among all the leaves of the term (([x.sub.2] [conjunction] [x.sub.1]) [disjunction] [[bar.x].sub.1]) [disjunction] ([x.sub.2] [conjunction] [x.sub.1])). We say for short that [psi] has m D-repetitions.

Essential variables. Let k be a fixed number of allowed variables. In the section 3.3 we consider some distinguished subset of [Var.sub.k] denoted by EVar. The elements of EVar are called essential variables. Suppose that the set EVar is fixed, and has cardinality l.

Definition 2.4 For a term [psi] and distinguished set of its leaves D, we say that [psi] has m restrictions among the leaves from D, if m equals the sum of D-repetitions and the number of different essential variables which have occurrences among the leaves from D. We say that [[psi] has m D-restrictions for short.

We can rephrase the definition above as follows: let [Var.sub.D] denote the set of variables with occurrences in D and [#.sub.D](x) denote the number of occurrences of a variable x in D, then the number of D-restrictions in [psi] equals:

[summation over x [member of] [Var.sub.D] \ Evar]([#.sub.D](x) - 1) + [summation over x [member of] [Var.sub.D] [intersection] Evar][#.sub.D](x).

For a pattern language P and [psi] [member of] P [T], we say that [psi] has m P-restrictions if it has m restrictions among the P-pattern leaves.

Let t be a structure with size n and let D be some set of distinguished leaves of t. We are interested in the number of possible leaf labellings of t so that we obtain a term from [F.sub.k] with m restrictions among the leaves from D. Let d be a cardinality of D. (l is the cardinality of distinguished set EVar [subset] [F.sub.k] of essential variables.)

For any r [less than or equal to] m we calculate the number of labellings which gives r D-repetitions and m D-restrictions. Every such labelling determines some partition of the set D into d - r classes of leaves labelled by the same variable (no matter positively or negatively). Additionally it must use m - r essential variables. The number of such labellings is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the consecutive factors correspond to: number of partitions of D into d - r classes, number of choices of essential variables to be used for the leaves from D, number of assignments of essential variables to the classes of elements of D, number of assignments of non-essential variables to the remaining classes of elements of D, number of assignment of variables to the leaves not belonging to D, number of distributions of negations among all the leaves of constructed term.

Therefore the total number of labellings which gives terms from [F.sub.k] with m restrictions among the leaves is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

In case, when there are no essential variables we get much simpler [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The observation below is a straightforward consequence of the Observation 1.2.

Observation 2.5 For fixed l, m [member of] [N.sub.1] a junction

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a polynomial of d. It is easily seen to have nonnegative values for d [member of] N.

In the next lemma we prove that for a big k the value [(k - l).sup.[d-m.bar]] is well estimated by [k.sup.d-m]

Lemma 2.6

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: [k.sup.d-m] is a number of sequences of variables of length d - m, while [(k - l).sup.[d-m.bar]] is a number of sequences of different non-essential variables. Every sequence belonging to the difference of these sets contains either some essential variable (the number of such sequences is smaller than (d - m) x l x [k.sup.d-m-1) or some repeated variable (the number of such sequences is smaller than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 2.7 Let T [subset] T be a tree language whose generating function t(z) has unique dominating singularity in [rho] [member of] [R.sub.+] of the square root type. Let P be an unambiguous pattern language, which is subcritical for T. Let P[T] (n, d) denote the number of trees from P[T] of size n containing exactly d pattern leaves, and w(d) be a nonzero polynomial of degree [gamma]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some nonnegative real [c.sub.w]. If additionally w(d) has nonnegative values for all elements of N and there exists integer r [greater than or equal to] [gamma] for which w(r) > 0 and and P contains a pattern with r regular leaves and at least one placeholder, then [c.sub.w] [not equal to] 0.

Proof: Let [alpha][gamma][d.sup.[[gamma].bar]] + [alpha][gamma] - 1 [d.sup.[[gamma] - 1.bar] + ... + [[alpha].sub.0] be a representation of w(d). For p(x, y) = [[summation].sub.d [member of] N, h [member of] N][x.sup.d][y.sup.h] P(d, h) being the generating function for P we have:

[x.sup.j] [[partial derivative].sup.j]p(x, y) / [([partial derivative]x).sup.j] = [[summation].sub.d [member of] N, h [member of] N][x.sup.d][y.sup.h] P(d, h)[d.sup.[j.bar]]

Therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we denote this function by [p.sub.w] (x, y). Since the function p(x, y) was subcritical for t(z) all its derivatives in x multiplied by polynomials are subcritical as well, and so is any finite combination of them. It means that [p.sub.w] (x, y) is subcritical for t(z), hence by the Observation 2.3 the function [p.sub.w](z) = [p.sub.w](x, y)[|.sub.(z, t(z))] has unique dominating singularity of the square root type in [rho] or its radius of convergence is greater then [rho]. By the Lemma 1.1 we get [lim.sub.n [right arrow] [infinity] [[z.sup.n]][p.sub.w](z) / [[z.sup.n]]t(z) = [c.sub.w] for some [c.sub.w] [member of] [0, [infinity]) (if the radius of convergence of [p.sub.w](z) is strictly greater then p then [c.sub.w] = 0). The function [p.sub.w]m(z) is exactly the generating function of the sequence [[summation].sub.d[member of]N] P[T] (n, d)w(d) and t(z) of the sequence T(n), therefore [lim-n.sub.[right arrow][infinity]] [[summation].sub.d[member of]N] P[T] (n, d)w(d)/T(n) = [c.sub.w].

Suppose that there exists integer r [greater than or equal to] [gamma] for which w(r) > 0 and P contains a pattern with r regular leaves and h > 0 placeholders. By nonnegativity of values of w(d), and coefficients of P[T](n, d) for every i, j [member of] N we have [[x.sup.i] [y.sup.j]][p.sub.w] (x, y) [greater than or equal to] [[x.sup.i][y.sup.j]([x.sup.r][y.sup.h]w(r)). The inequality is preserved after substitution of the pair of nonnegative series (z, t (z)), hence [[z.sup.i]][p.sub.w](z) [greater than or equal to] [[z.sup.i]]([z.sup.r]t[(z).sup.h]w(r)). It shows that [p.sub.w] (z) must have singularity in [rho], which by the Lemma 1.1 gives [c.sub.w] [not equal to] 0.

Lemma 2.8 Let P be an unambiguous pattern language, which is subcritical for T. We denote by [F.sup.[m].sub.k] (P[T])(n) (resp. by [F.sup.[[greater than or equal to]m]].sub.k] (P[T])(n))the number of terms from [F.sub.k] of size n whose structure belongs to P[T] and which have m (resp. at least m) P-restrictions. For every m [member of] N for which P contains pattern with at least m + 1 regular leaves and at least one placeholder we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

for some [c.sub.m,l] [member of] [R.sub.+] (the constant [c.sub.m,l] depends on the number of essential variables l).

Proof: Let P[T](n, d) denote the number of trees from P[T] of size n containing exactly d pattern leaves. For any fixed d and number of variables k we have P[T](n, d) x [w.sub.m,l](d) x [k.sup.[d-m.bar]] x [k.sup.n-d] x [2.sup.n] terms from [F.sub.k] of size n with d pattern leaves and m restrictions among them. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

and by the Lemma 2.6

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Applying the Lemma (2.7) we get:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for some positive [c.sub.m,l] (it is easy to verify that [w.sub.m,l](d) and P satisfy additional assumptions). Analogously we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as a result of application of the same lemma with the polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The last two estimations, together with 5 and 6 gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally, by the fact that the upper bound from (5) is greater than the fraction of all terms from [F.sub.k] containing at least m P-restrictions, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3 Applications to and/or trees

3.1 Pattern languages and subcriticality

Two most important pattern languages we use are defined as follows:

N = N [disjunction] N [absolute value of [??] [conjunction] N]*, P = [??] [disjunction] P [absolute value of P [conjunction] P]*. (7)

It is easy to observe that both are unambiguous for any tree language. For every term t if some valuation valuates all its literals in N-pattern (resp. P-pattern) leaves to False (resp. True) then the whole term is valuated to False (resp. True).

We consider also patterns which are compositions of patterns. For a pattern language S the pattern language [S.sup.(i)] is defined as [S.sup.(i-1)][S] for i > 1 and as S for i = 1. Clearly, a composition of unambiguous pattern languages remains unambiguous. Let [S.sub.1], [S.sub.2] be unambiguous pattern languages with generating functions [s.sub.1](x, y), [s.sub.2](x, y). It is easy to observe that the generating function for [S.sub.1][S.sub.2] equals [s.sub.1] (x, [s.sub.2](x,y)).

Both pattern languages N and P have the same generating function p(x, y) which satisfies the equation

p(x, y) = p[(x, y).sup.2] + y x p(x, y) + x.

Therefore we have

p(x, y) = 1/2 (-(y - 1) - [square root of [(y - 1).sup.2] - 4x).

(We discard the second solution using the fact that p(x, 0) should be equal to the generating function of binary trees without any labels.)

The polynomial [(y - 1).sup.2] - 4x has no zeros within the set D = {(x, y) [member of] ([C.sup.2] : [absolute value of x] [less than or equal to] 1/8 [conjunction] [absolute value of y] [less than or equal to] 1/4}. It shows that p(x, y) is analytic in this set. Finally, by the fact that [absolute value of t(z)] [less than or equal to] 1/4 for [absolute value of z] [less than or equal to] 1/8 we obtain subcriticality of P and N for T. By nonnegativity of the coefficients of p(x, y) as a formal power series we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It shows that for an unambiguous pattern language S which is subcritical for T, the pattern language S[N] (resp. S[P]) is subcritical for T as well.

We are going to use also combined pattern language P [direct sum] N, such that for any tree a leaf is P [direct sum] N-pattern leaf if it is P-pattern leaf or N-pattern leaf. This pattern language is also unambiguous. In fact it is not hard to see that every P [direct sum] N pattern leaf is N[P]-pattern leaf. As a result, the pattern language P [direct sum] N is subcritical for T and for any unambiguous pattern language S which is subcritical for T, the pattern language S[P [direct sum] N] is subcritical for T as well.

Corollary 3.1 For every i [member of] N pattern language [N.sup.(1)][P [direct sum] N] is unambiguous and subcritical for T.

3.2 Simple Tautologies

Within this section we assume that the set of essential variables is empty. A term (and/or tree) is a simple tautology if up to commutativity and associativity it is equal to x [disjunction] [bar.x] [disjunction] [psi] for some variable x and term [psi].

We present a simple proof of the theorem announced by Woods in [9], which we are going to use in the next section.

Theorem 3.2 The density of tautologies among and/or trees with k variables asymptotically (with k) equals the density of simple tautologies.

Proof: We use the pattern N defined by the equation (7). It is a matter of algebraic calculations to prove that the density of simple tautologies is asymptotically d/k (the pattern S = [??] [conjunction] [??][absolute value of S [disjunction] S][??] might be helpful), for some positive d [member of] R.

Every term which has no opposite literals among the N-pattern leaves, can be falsified by the valuation sending all these literals to false. We consider terms with exactly one N[N]-restriction. Every simple tautology belongs to this set. An N[N]-pattern leaf is called a first level leaf if it is also N-pattern leaf, otherwise it is called a second level pattern leaf. Suppose that t is a tautology with exactly one N[N]-restriction (it must be repetition since there are no essential variables). In such a tautology the literals containing the occurrences of the repeated variable must be opposite. If at least one of the literals is on the second level, then we have no N-repetitions, and such a formula can be falsified. Therefore both opposite literals must be on the first level. If the t is not a simple tautology, then we have at least one node v labelled with [conjunction] above at least one of the N[N] leaves containing the repeated variable. Let [t.sub.1] [conjunction] [t.sub.2] be the subtree of t rooted at v. Since we have only one N[N]-repetition we can be sure that there are no opposite literals among the N[N]-pattern leaves of t which do not belong to the subtree [t.sub.2]. Now it is easy to see that valuating all those literals to False falsifies the whole term. It shows that all tautologies among the terms with exactly one N[N]-repetitions are simple.

The theorem follows from the fact that the density of terms with at least two N[N] repetitions is asymptotically of the order [k.sup.-2] (Lemma 2.8) and terms without N[N]-repetitions can not be tautologies.

3.3 D. Gardy, A. Woods conjecture

Within this section we prove the variant of the Conjecture 1 from [5]. We address only the case of the distribution [P.sub.k]. The proof for the distribution [[pi].sub.k] is based on the same methods.

By a boolean function we mean a function f : [{0,1}.sup.var] [right arrow] {0,1} (i.e. a function which transforms valuations of variables from Var to boolean values). We say that a function f depends on the variable [x.sub.i] when there exist two valuations [v.sub.1], [v.sub.2] [member of] [{0, 1}.sup.var], which differ only in the valuation of the variable [x.sub.i] such that f(v.sub.1) [not equal to] f ([v.sub.2]). All the functions we consider depend on the finite number of variables (every function defined by some term has this property). In that convention every distribution [P.sub.k] can be seen as a discrete probability distribution with finite support on the set of all functions of type [{0,1}.sup.Var] [right arrow] {0, 1}.

The generalised version of D. Gardy, A. Woods conjecture from [5] for the distribution [P.sub.k]:

Theorem 3.3 Let f be a boolean non-constant function defined by some minimal and/or tree with size r, then there exists positive constant [B.sub.f] such that

[P.sub.k](f) ~[sub.k] [B.sub.f][k.sup.-r-1]

Due to the limited space, we present a proof of the simplified version of the above theorem (Lemma 3.4), which (in our opinion) captures the most important part of it.

Let us fix function f as in the statement of the theorem. Without loss of generality we may assume that f depends on variables [x.sub.1], ..., [x.sub.j]. We fix the set of essential variables to EVar = {[x.sub.1], ..., [x.sub.j]}. Note that every minimal tree defining f must have r restrictions among all its leaves.

Lemma 3.4

[P.sub.k](f) = [THETA]([k.sup.-r-1]).

Proof: For r being a complexity of f we consider pattern language R = [N.sup.(r+1)] [P [direct sum] N]. By the Corollary 3.1, pattern language R is unambiguous and subcritical for T. For i [less than or equal to] r + 1 we say that R-pattern leaf is on the level i if it is [N.sup.(i)]-pattern leaf, but not [N.sup.(i-1)]-pattern leaf (there are no [N.sup.0] pattern leaves). An R-pattern leaf is on the level r + 2 if it is not [N.sup.(r+1)]-pattern leaf.

Let t be a term of the size r defining f. Every term of the form [psi] [conjunction] t, for [psi] being a tautology, defines function f. Since the density of tautologies is asymptotically equal to d/k we get the trivial lower bound for [P.sub.k] (f) which holds for big enough k:

[P.sub.k](f) [greater than or equal to] [bar.d] / [k.sup.r+1], (8)

for [bar.d] [member of] [R.sub.+]. From this bound we know that we can neglect all terms with at least r + 2 restrictions among R-pattern leaves (by the Lemma 2.8 the density of them is of the order [k.sup.-r-2]).

Using subcriticality of R it is easy to see that the trees which does not have leaves on the level r + 2 does not contribute to the density [P.sub.k](f). We assume that considered terms have at least one leaf on the level r + 2. We show that such a term must contain at least r + 1 restrictions among R-leaves to define function f.

Let t be a term defining f with at most r restrictions among R-leaves.

Let i be the smallest number such that term t contains the same number of [N.sup.(i-1)]-restrictions that of [N.sup.(i)]-restrictions. It is easy to observe that such i exists and is not greater than r + 1 (t must contain at least one restriction on the first level.) In particular there are no essential variables on the i-th level. We consider two cases:

First case: t has at most r - 1 restrictions among [N.sup.(i)] pattern leaves. Since there are no essential variables on the i-th level, we can replace these leaves with leaves labelled by constant False without changing the function defined by the term. But then, by the properties of the pattern N, all the nodes on the level i are valuated constantly to False, and hence we can trim the tree by replacing all subtrees whose roots are on the level i by leaves containing constant False. Such trimmed tree still calculates the same function f. By the same token we can substitute False for all non-essential variables occurring in the trimmed tree. Finally we can get rid of the constants using the rules:

False [conjunction] [psi] [equivalent to] False, False [disjunction] [psi] [equivalent to] [psi].

The resulting tree contains no constant leaves, calculates the same function as t, and has at most (r - 1) restrictions among all leaves. It means also that the resulting tree has size not greater than r - 1 (since all occurrences of variables are essential), which contradicts the fact that the complexity of f is r.

Second case: t has exactly r restrictions among [N.sup.(i)] pattern leaves. Then there are no restrictions among R-pattern leaves below the i-th level. It means that every variable which occurrs in R-pattern leaf on the level i or below is not essential and has exactly one occurrence among R-pattern leaves. We use special leaf labelling symbol * called wildcard, the occurrence of * means that the leaf can be valuated independently of all essential variables and all variables occurring in the other R-pattern leaves.

Let us consider a node v which is on the level r + 2, but whose parent is on the level r + 1. By the construction of the pattern R, all the (N [direct sum] P)-pattern leaves in the subtree rooted at v are R-pattern leaves. Since these leaves are on the level r + 2 the variables occurring in them are no repeated anywhere among R-leaves (they are also non essential). If we want to valuate the node v to True (resp. False) is suffices to evaluate all its positive (negative) leaves to True (False). It means that the node v can be evaluated to any value we want, independently of valuations of any R-pattern leaves, which are not below v. We substitute every such node v by a leaf labelled with wildcard. Whatever values we substitute for the wildcard, the computed function is still f. Note also that all the leaves in such constructed tree are R-pattern leaves. Similarly we can substitute wildcard * for every leaf of such constructed tree which is labelled by a non-essential variable which is not repeated among other leaves. Finally, we eliminate wildcards by the following rules (and their symmetric variations):

* [disjunction] * [equivalent to] * [conjunction] * [equivalent to] *

* [disjunction][psi] [equivalent to] True * [conjunction][psi] [equivalent to] False (9)

False [conjunction] [psi] [equivalent to] False True [disjunction] [psi] [equivalent to] True

True [conjunction] [psi] [equivalent to] [psi] False [disjunction] [psi] [equivalent to] [psi] (10)

where [psi] denotes a term which does not contain any wildcard. The interpretation of rules is straightforward (in case of rules 9 since * can be valuated to any value, we can always chose valuation which valuates *[disjunction][psi] to True independently of the valuation of any variables occurring in the R-pattern leaves of the tree). The tree [??] obtained after such elimination still computes function f and has no wildcards. The tree before elimination contained r restrictions, at least one wildcard, and no constants. All the wildcards vanish during elimination process. It means that one of the rules from 9 must be used at least once. But use of such rule removes some subtree which originally contained at least one leaf not labelled with wildcard. Since such a leaf must contain either essential or repeated variable, the application of the rule reduces the number of restrictions in the tree, by at least one. Therefore the tree [??] contains at most r - 1 restrictions which contradicts the fact that the complexity of f is r.

We got contradictions in both cases which shows that a tree having at least one leaf on the level r + 2 and defining the function f must have at least r + 1 repetitions among R-pattern leaves. This observation together with the Lemma 2.8 gives that for big enough k we have [P.sub.k](f) [less than or equal to] c/[k.sup.r+1]. Therefore, by the trivial lower bound (equation 8) we get: [P.sub.k](f) = [THETA](1/[k.sup.r+1]).

Using similar methods we can prove the existence of the constants [B.sub.f] from the theorem 3.3.

4 Concluding remarks

The method of subcritical pattern language seems to be suitable to be applied to a lot of problems concerning relative densities of tree languages. Beside the presented applications it can be used to prove the full version of D. Gardy, A. Woods conjecture for both of distributions (i.e. [P.sub.k] and [[pi].sub.k], we omit these proofs for the lack of space). Moreover, lots of the results on relative densities of propositional logics can be proven anew within this framework (e.g. [3], [6]).

Presented results explains the behaviour of [P.sub.k](f) for fixed function f when k tends to infinity. In such situation the complexity of f is eventually much smaller then the worst possible complexity (which is exponential in h). We believe that a deeper investigation of a typical structures of terms defining f with a carefull treatment of the lower order terms in the estimation of [P.sub.k](f) would give a new upper bound for that probability, which would be nontrivial for functions with small complexity. This would partially supplement the upper bound known so far (see [1]):

(1 + O(1/k)) exp(-c r/[k.sup.2],

(where r is the complexity of f, and c > 0, see [1]), which is easily seen to be trivial for sufficiently small complexity r.

References

[1] B. Chauvin, P. Flajolet, D. Gardy, and B. Gittenberger, And/or trees revisited., Combinatorics, Probability & Computing 13 (2004).

[2] Phillipe Flajolet and Robert Sedgewick, Analytic combinatorics, in preparation, preprint available at http://algo.inria.fr/flajolet/Publications/book.pdf, 2008.

[3] Herve Fournier, Daniele Gardy, Antoine Genitrini, and Marek Zaionc, Classical and intuitionistic logic are asymptotically identical, CSL, 2007, pp. 177-193.

[4] Daniele Gardy, Random boolean expressions, Computational Logic and Applications, CLA '05 (Rene David, Daniele Gardy, Pierre Lescanne, and Marek Zaionc, eds.), DMTCS Proceedings, vol. AF, Discrete Mathematics and Theoretical Computer Science, 2005, pp. 1-36.

[5] Daniele Gardy and Alan Woods, And/or tree probabilities of boolean functions, 2005 International Conference on Analysis of Algorithms (Conrado Martinez, ed.), DMTCS Proceedings, vol. AD, Discrete Mathematics and Theoretical Computer Science, 2005, pp. 139-146.

[6] Antoine Genitrini, Jakub Kozik, and Marek Zaionc, Intuitionistic vs classical tautologies, quantitative comparison, Types, 2007, to appear.

[7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.

[8] Hanno Lefmann and Petr Savicky, Some typical properties of large and/or boolean formulas, Random Struct. Algorithms 10 (1997), no. 3, 337-351.

[9] Alan Woods, On the probability of absolute truth for and/or formulas, Annual Conference of The Australian Association for Logic 2006., 2006.

([dagger]) Research described in this paper was partially supported by POLONIUM grant (Quantitative research in logic and functional languages, cooperation between Jagiellonian University of Krakow, L' Ecole Normale Superieure de Lyon and Universite de Versailles Saint-Quentin, contract number 7087/R07/R08) and French government research grant for young scientists (program number 0185)

Jakub Kozik

Theoretical Computer Science, Jagiellonian University

Gronostajowa 3, Krakow, Poland.

jkozik@tcs.uj.edu.pl
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Kozik, Jakub
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EXPO
Date:Jan 1, 2008
Words:7369
Previous Article:A note on the transience of critical branching random walks on the line.
Next Article:On density of truth of the intuitionistic logic in one variable.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |