On interpreting and inferring propositional formulas of data dependencies in a relational database

This paper concerns generally the satisfaction and the inference problem involving functional and/or multivalued dependencies in a relational database. In particular, two independent aids in solving an inference problem, concerning the logical counterparts of functional as well as multivalued dependencies, are introduced. The first aid is provided by establishing a pair of complementary inequivalence and equivalence theorems between the propositional formula corresponding to the difference, U-X, in set theory and the propositional formula not(X) where U is a relation scheme and X is a subset of U. By applying these theorems, correctness of solving an inference problem is assured. The second aid is the application of a Venn diagram for simplifying a propositional formula involving conjunctions, differences, etc., for solving an inference problem. A guideline for constructing simplified Venn diagrams is also given and discussed.     

New construction of highly nonlinear resilient S-boxes via linear codes

Highly nonlinear resilient functions play a crucial role in nonlinear combiners which are usual hardware oriented stream ciphers. During the past three decades, the main idea of construction of highly nonlinear resilient functions are benefited from concatenating a large number of affine subfunctions. However, these resilient functions as core component of ciphers usually suffered from the guess and determine attack or algebraic attack since the n-variable nonlinear Boolean functions can be easily given rise to partial linear relations by fixing at most n/2 variables of them. How to design highly nonlinear resilient functions (S-boxes) without concatenating a large number of n/2 variables affine subfunctions appears to be an important task. In this article, a new construction of highly nonlinear resilient functions is proposed. These functions consist of two classes subfunctions. More specially, the first class (nonlinear part) contains both the bent functions with 2 k variables and some affine subfunctions with n/2 − k variables which are attained by using [ n/2 − k, m, d] disjoint linear codes. The second class (linear part) includes some linear subfunctions with n/2 variables which are attained by using [ n/2, m, d] disjoint linear codes. It is illustrated that these resilient functions have high nonlinearity and high algebraic degree. In particular, It is different from previous well-known resilient S-boxes, these new S-boxes cannot be directly decomposed into some affine subfunctions with n/2 variables by fixing at most n/2 variables. It means that the S-boxes (vectorial Boolean functions) which use these resilient functions as component functions have more favourable cryptography properties against the guess and determine attack or algebraic attacks.     

Estimating posterior inference quality of the relational infinite latent feature model for overlapping community detection

Overlapping community detection has become a very hot research topic in recent decades, and a plethora of methods have been proposed. But, a common challenge in many existing overlapping community detection approaches is that the number of communities K must be predefinedmanually. We propose a flexible nonparametric Bayesian generative model for count-value networks, which can allow K to increase as more and more data are encountered instead of to be fixed in advance. The Indian buffet process was used to model the community assignment matrix Z, and an uncollapsed Gibbs sampler has been derived.However, as the community assignment matrix Z is a structured multi-variable parameter, how to summarize the posterior inference results and estimate the inference quality about Z, is still a considerable challenge in the literature. In this paper, a graph convolutional neural network based graph classifier was utilized to help to summarize the results and to estimate the inference quality about Z. We conduct extensive experiments on synthetic data and real data, and find that empirically, the traditional posterior summarization strategy is reliable.     

The foundations of confounding in epidemiology

A statistically coherent view of confounding motivated by the over controversy over the proper control of confounding in the presence of prior knowledge is presented. Confounding by a covariate C in the presence of data on C is distinguished from confounding in the absence of data on C. A covariate C is defined to be a nonconfounder in the absence of data on C if the population parameter of interest can be unbiasedly estimated (asymptotically) absent data on C. Under this definition, C may be a confounder for some parameters of interest and a nonconfounder for others. If C is a confounder for a parameter of interest that has a causal interpretation, we call C a causal confounder. When data on C are available, C is defined to be a nonconfounder for a particular parameter of interest if and only if inference on the parameter of interest does not depend on the data through C. Bayesians, frequentists and pure likelihoodists will in general agree on the prior knowledge necessary to render C a non-confounder. In particular C will in general be a nonconfounder precisely when the crude data ignoring C are S-sufficient for the parameter of interest. The intuitive view held by many practicing epidemiologists that confounding by C represents a bias of the unadjusted crude estimator is in a sense correct provided inference is performed conditional on approximate ancillary statistics that measure the degree to which associations in the data differ due to sampling variability from those population associations known a priori.     

On structuring proof search for first order linear logic

Full first-order linear logic can be presented as an abstract logic programming language in Miller's system Forum, which yields a sensible operational interpretation in the ‘proof search as computation’ paradigm. However, Forum still has to deal with syntactic details that would normally be ignored by a reasonable operational semantics. In this respect, Forum improves on Gentzen systems for linear logic by restricting the language and the form of inference rules. We further improve on Forum by restricting the class of formulae allowed, in a system we call G-Forum, which is still equivalent to full first-order linear logic. The only formulae allowed in G-Forum have the same shape as Forum sequents: the restriction does not diminish expressiveness and makes G-Forum amenable to proof theoretic analysis. G-Forum consists of two (big) inference rules, for which we show a cut elimination procedure. This does not need to appeal to finer detail in formulae and sequents than is provided by G-Forum, thus successfully testing the internal symmetries of our system.     

Dynamic composition of parameterised logic modules

We present a logic-based programming language that features meta-level composition operations over programs. Object programs are parameterised named collections of definite clauses which may contain formulae of the form A in Pexp, where A is a standard atomic formula and Pexp is a program expression obtained by applying composition operations over named object programs. The semantics of the language is presented in two different equivalent styles. An operational, top-down semantics is given by means of inference rules, while a denotational, bottom-up semantics is given via an immediate consequence operator associated with program expressions. A meta-programming implementation of the language is also presented by transforming the operational inference rules into meta-level axioms. Several programming examples are discussed to illustrate the expressive power of the language.     

A molecular quasi-random model of computations applied to evaluate collective intelligence

This paper presents a bio-inspired model of computations, the random PROLOG processor (RPP), used for analysis of collective intelligence (CI). In the RPP, clause_molecules (CMs) of facts, rules, goals, or higher-level logical structures enclosed by membranes move quasi-randomly in structured computational_PROLOG_space (CS). When CMs rendezvous, an inference process can occur iff the logical conditions are fulfilled. CI can be evaluated as follows: (1) the mapping is done of a given social structure into the RPP; (2) the beings and their behavior are translated into PROLOG expressions, carried by CMs; (3) the goal(s) of the social structure are translated into N-element inference (NEI); (4) the efficiency of the NEI is evaluated and given as the intelligence quotient of a social structure (IQS) projected onto NEI.     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.