Springer Science and Business Media LLC

This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be defined by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence, to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs does not increase when one considers the programs which have a unique stable model or a total well-founded model. This shows that all these classes of structures (perfect models of logically stratified logic programs, well-founded models which turn out to be total, and stable models of programs possessing a unique stable model) are all closely connected with Kleene's hyperarithmetical hierarchy. Thus, for general logic programming, negation with respect to two-valued logic is related to the hyperarithmetic hierarchy in the same way as Horn logic is to the class of recursively enumerable sets. In particular, a set is definable in the well-founded semantics by a programP whose well-founded partial model is total iff it is hyperarithmetic.

Analyzing the recent financial history of a firm is an important step in the annual audit cycle and in many other financial reasoning tasks. Auditors and other analysts performing this task have available to them a variety of mathematical models to fit to a set of historical and current period financial statement data. They also have expectations about the likelihoods and magnitudes of errors in that current period financial statement. Given these models and expectations, they must find the combination of models and statement errors that is most consistent with the numbers in the current period statement. A crucial difficulty in this task is in keeping track of the various models being tried and coping with the multiplicity of consistent combinations. This is a hard and general problem, and an important one in any uncertain environment in which human analysts must “juggle” many incompatible possibilities to arrive at a consistent view of the world. The program discussed in this paper prototypes a solution mechanism with potential to deal with this class of problems.

We prove a new property of dual hypergraphs and derive from it Nash-solvability of the corresponding (tight) game forms. This result is known since 1975, but its new proof is much simpler.

Over many different kinds of cryptomorphisms equivalent with closure systems (and so with closure operators), we focus here on implication relations and the related overhanging relations, as introduced and axiomatized in a previous paper (Domenach and Leclerc, Math Soc Sci 47(3):349–366, 2004). In relation with data analysis motivations, we particularize the axioms on overhanging relations in order to account for some types of closure systems, such as nested or distributive ones. We also examine the lattice structure of overhanging relations, which is isomorphic to the lattice of closure systems, and derived structures for particular sets of overhangings.

Acronyms—words formed from the initial letters of a phrase—are important for various natural language processing applications, including information retrieval and machine translation. While hand-crafted acronym dictionaries exist, they are limited and require frequent updates. We present a new machine-learning-based approach to automatically build an acronym dictionary from unannotated texts. This is the first such technique that specifically handles non-local acronyms, i.e., that can determine an acronym’s expansion even when the expansion does not appear in the same document as the acronym. Our approach automatically enhances the dictionary with contextual information to help address the acronym disambiguation task (selecting the most appropriate expansion for a given acronym in context), outperforming dictionaries built using prior techniques. We apply the approach to Modern Hebrew, a language with a long tradition of using acronyms, in which the productive morphology and unique orthography adds to the complexity of the problem.

Reasoning about the location of regions in 2-dimensional space is necessarily based on finite approximations to such regions. These finite approximations are often derived by describing how a region (the figure) relates to a frame of reference (the ground). The frame of reference generally consists of regions, or cells, forming a partition of the space under consideration. This paper presents a new approach to describing figure-ground relationships which is able to take account of how the figure relates to boundaries between cells as well as to their interiors. We also provide a general theory of how approximations to regions lead to approximations to operations on regions. This theory is applied to the case of our boundary-sensitive model of location. The paper concludes by indicating how interpreting boundaries in a more general sense should lead to a theory dealing with generalized partitions in which the cells may overlap. The applications of the theory developed here will include qualitative spatial reasoning, and should have practical relevance to geographical information systems.