The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as context-sensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.

On the Ontological Quality and Logical Quality of Conceptual-Modeling Grammars: The Need for a Dual Perspective

A core activity in information systems development involves building a conceptual model of the domain that an information system is intended to support. Such models are created using a conceptual-modeling (CM) grammar. Just as high-quality conceptual models facilitate high-quality systems development, high-quality CM grammars facilitate high-quality conceptual modeling. This paper provides a new perspective on ways to improve the quality of the semantics of CM grammars. For many years, the leading approach to this topic has relied on ontological theory. We show, however, that the ontological approach captures only half the story. It needs to be coupled with a logical approach. We explain how the ontological quality and logical quality of CM grammars interrelate. Furthermore, we outline three contributions that a logical approach can make to evaluating the quality of CM grammars: a means of seeing some familiar conceptual-modeling problems in simpler ways; the illumination of new problems; and the ability to prove the benefit of modifying existing CM grammars in particular ways. We demonstrate these benefits in the context of the Entity-Relationship grammar. More generally, our paper opens up a new area of research with many opportunities for future research and practice.

Logic Brightens My Day: Evidence for Implicit Sensitivity to Logical Validity.

A key assumption of dual process theory is that reasoning is an explicit, effortful, deliberative process. The present study offers evidence for an implicit, possibly intuitive component of reasoning. Participants were shown sentences embedded in logically valid or invalid arguments. Participants were not asked to reason but instead rated the sentences for liking (Experiment 1) and physical brightness (Experiments 2-3). Sentences that followed logically from preceding sentences were judged to be more likable and brighter. Two other factors thought to be linked to implicit processing-sentence believability and facial expression-had similar effects on liking and brightness ratings. The authors conclude that sensitivity to logical structure was implicit, occurring potentially automatically and outside of awareness. They discuss the results within a fluency misattribution framework and make reference to the literature on discourse comprehension.