It has generally been assumed that the knowledge employed by an AI reasoning system needs to be in an unambiguous, formally interpretable form. From that perspective, general knowledge expressed in ordinary language (e.g., “dogs bark”) is unacceptably ambiguous and incomplete. However, we can achieve at least a partial transformation of such knowledge into formal, generically quantified sentences by taking account of properties of words and phrases such as the aspectual category, tense, Levin class, and presuppositions of verbs, or the classification of predicates (adjectival, nominal, verbal) as applicable to objects or kinds of objects.

Grounding is the task of reducing a first-order theory and finite domain to an equivalent propositional theory. It is used as preprocessing phase in many logic-based reasoning systems. Such systems provide a rich first-order input language to a user and can rely on efficient propositional solvers to perform the actual reasoning. Besides a first-order theory and finite domain, the input for grounders contains in many applications also additional data. By exploiting this data, the size of the grounder's output can often be reduced significantly. A common practice to improve the efficiency of a grounder in this context is by manually adding semantically redundant information to the input theory, indicating where and when the grounder should exploit the data. In this paper we present a method to compute and add such redundant information automatically. Our method therefore simplifies the task of writing input theories that can be grounded efficiently by current systems. We first present our method for classical first-order logic (FO) theories. Then we extend it to FO(ID), the extension of FO with inductive definitions, which allows for more concise and comprehensive input theories. We discuss implementation issues and experimentally validate the practical applicability of our method.

The Zen Puzzle Garden (ZPG) [16] is a one-player puzzle game involving a Buddhist monk raking a sand garden. It is inspired by Japanese garden design (for example, the Komyozenji temple garden is shown in Figure 1). One common feature of such gardens is a flat region of sand or small pebbles, which is raked into a pattern. The ZPG is one example of a transport puzzle; these are problems that involve the player moving entities around a given domain (e.g., boxed around a warehouse), starting at some initial configuration, until they attain predefined goal conditions. Entities must move according to the constraints of the puzzle, and may only move between connected positions (that is, an entity may not be "lifted" off the board and replaced at a position perhaps far from its initial location). A graphical representation of the problem may use vertices to represent the set of positions an entity may occupy, with connecting edges determined either from any explicitly named connections, or from those implied by arrangement on the board or within a grid. The rest of the paper is organized as follows: We first describe related work in Section III and give an indepth description of the problem in Section III, before describing two solution methods (genetic algorithm and A*) for the ZPG in Section IV. Experimental results are presented in Section V, before we conclude with a brief discussion of the implications of our findings in terms of broader applicability.

This article introduces the challenge of digital preservation in the area of engineering design and manufacturing and presents a methodology to apply knowledge representation and semantic techniques to develop Digital Engineering Archives. This work is part of an ongoing, multiuniversity, effort to create cyber infrastructure-based engineering repositories for undergraduates (CIBER-U) to support engineering design education. The technical approach is to use knowledge representation techniques to create formal models of engineering data elements, workflows and processes. With these formal engineering knowledge and processes can be captured and preserved with some guarantee of long-term interpretability.

This article introduces the challenge of digital preservation in the area of engineering design and manufacturing and presents a methodology to apply knowledge representation and semantic techniques to develop Digital Engineering Archives. This work is part of an ongoing, multiuniversity, effort to create cyber infrastructure-based engineering repositories for undergraduates (CIBER-U) to support engineering design education. The technical approach is to use knowledge representation techniques to create formal models of engineering data elements, workflows and processes. With these formal engineering knowledge and processes can be captured and preserved with some guarantee of long-term interpretability. The article presents examples of how the techniques can be used to encode specific engineering information packages and workflows. These techniques are being integrated into a semantic wiki that supports the CIBER-U engineering education activities across nine universities and involving over 3500 students since 2006.

We present tropical games, a generalization of combinatorial min-max games based on tropical algebras. Our model breaks the traditional symmetry of rational zero-sum games where players have exactly opposed goals (min vs. max), is more widely applicable than min-max and also supports a form of pruning, despite it being less effective than alpha-beta. Actually, min-max games may be seen as particular cases where both the game and its dual are tropical: when the dual of a tropical game is also tropical, the power of alpha-beta is completely recovered. We formally develop the model and prove that the tropical pruning strategy is correct, then conclude by showing how the problem of approximated parsing can be modeled as a tropical game, profiting from pruning.

Ambient Intelligence environments consist of various devices that collect, process, change and share the available context information. The imperfect nature of context, the open and dynamic nature of ambient environments, and the special characteristics of the involved devices have introduced new research challenges in the field of KR. Previous work presented a solution based on an extension of multi-context systems through the use of defeasible reasoning to reason efficiently with conflicts. This paper reports on initial experiences gained from the deployment of contextual defeasible reasoning in real environments. We report on the architecture of an implementation on small devices, present the definition and implementation of two concrete application scenarios, and discuss the performance and issues of scalability of the approach.

By logical proportion, we mean a statement that expresses a semantical equivalence between two pairs of propositions. In these pairs, each element is compared to the other in terms of similarities and/or dissimilarities. An example of such a proportion is the well known analogical proportion: a is to b as c is to d . Analogical proportions have been recently characterized in logical terms, but there are many other proportions that are worth of interest. Some of them can be related to the analogical pattern, others are related to semantical equivalence between conditional objects and express statements such as a ressembles to b and differs from b in the same way as c with respect to d. We show that there are 5 direct proportions, including the analogical one and 4 others having a conditional object flavor, where the change (if any) from a to b goes in the same direction as the change from c to d (if any), together with 5 reverse proportions obtained by switching c and d. Moreover, there exists only one auto-reverse proportion called paralogy and stating that what a and b have in common, c and d have it as well. It is then established that there is none other proportion than these ones (with the exception of 4 degenerated ones) that satisfies a natural “full identity” requirement. The paper proposes a structured and unified view of these logical proportions and discusses their characteristic properties. It extends previous works where only proportions related to analogy were considered. It also explores the use of these logical proportions in transduction-like inference, where new items are classified on the basis of already classified items without trying to induce a generic model, considering similarities and differences between items only. Taking advantage of different proportions, a transduction procedure is proposed.

We consider a generalized form of planning, possibly involving loops, that arises in nondeterministic domains when ex- plicit strong fairness constraints are asserted over the planning domain. Such constraints allow us to specify the necessity of occurrence of selected effects of nondeterministic actions over domain’s runs. Also they are particularly meaningful from the technical point of view because they exhibit the expressiveness advantage of LTL over CTL in verification. We show that planning for reachability and maintenance goals is EXPTIME-complete in this setting, that is, it has the same complexity as conditional planning in nondeterministic domains (without strong fairness constraints). We also show that within the EXPTIME bound one can solve the more general problems of realizing agent planning programs as well as composition-based planning in the presence of strong fairness constraints.

Measuring the inconsistency degree of a knowledge base can help us to deal with inconsistencies. Several inconsistency measures have been given under different multi-valued semantics, including 4-valued semantics, 3-valued semantics, LPm and Quasi Classical semantics. In this paper, we first carefully analyze the relationship between these inconsistency measures by showing that the inconsistency degrees under 4-valued semantics, 3-value semantics, LPm are the same, but different from the one based on Quasi Classical semantics. We then consider the computation of these inconsistency measures and show that computing inconsistency measurement under multi-valued semantics is usually intractable. To tackle this problem, we propose two novel algorithms that respectively encode the problems of computing inconsistency degrees under 4-valued semantics (3-valued semantics, LPm) and under Quasi Classical semantics into the partial Max-SAT problems. We implement these algorithms and do experiments on some benchmark data sets. The preliminary but encouraging experimental results show that our approach is efficient to handle large knowledge bases.