We study an alternative to the prevailing approach to modelling qualitative spatial reasoning (QSR) problems as constraint satisfaction problems. In the standard approach, a relation between objects is a constraint whereas in the alternative approach it is a variable. The relation-variable approach greatly simplifies integration and implementation of QSR. To substantiate this point, we discuss several QSR algorithms from the literature which in the relation-variable approach reduce to the customary constraint propagation algorithm enforcing generalised arc-consistency.

We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations, we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraint programming system by drawing on ideas from bounded model checking. The resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects.

Constraint propagation algorithms implement logical infe r-ence. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level fra mework that clearly differentiates between information needed for cont rolling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriaten ess of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algo rithms, such as literal watching for unit clause propagation and the lexi cographic ordering constraint. We provide an implementation and benchm ark results that demonstrate the practicality and efficiency of our frame work.

The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this introduction, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the literature, developed for dealing with imprecise, uncertain and paradoxical sources of information. We focus our presentation here rather on the foundations of DSmT, and on the two important new rules of combination, than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout the presentation to show the efficiency and the generality of this new approach.

This paper introduces the notion of qualitative belief assignment to model beliefs of human experts expressed in natural language (with linguistic labels). We show how qualitative beliefs can be efficiently combined using an extension of Dezert-Smarandache Theory (DSmT) of plausible and paradoxical quantitative reasoning to qualitative reasoning. We propose a new arithmetic on linguistic labels which allows a direct extension of classical DSm fusion rule or DSm Hybrid rules. An approximate qualitative PCR5 rule is also proposed jointly with a Qualitative Average Operator. We also show how crisp or interval mappings can be used to deal indirectly with linguistic labels. A very simple example is provided to illustrate our qualitative fusion rules.

In this paper we consider and analyze the behavior of two combinational rules for temporal (sequential) attribute data fusion for target type estimation. Our comparative analysis is based on Dempster's fusion rule proposed in Dempster-Shafer Theory (DST) and on the Proportional Conflict Redistribution rule no. 5 (PCR5) recently proposed in Dezert-Smarandache Theory (DSmT). We show through very simple scenario and Monte-Carlo simulation, how PCR5 allows a very efficient Target Type Tracking and reduces drastically the latency delay for correct Target Type decision with respect to Demspter's rule. For cases presenting some short Target Type switches, Demspter's rule is proved to be unable to detect the switches and thus to track correctly the Target Type changes. The approach proposed here is totally new, efficient and promising to be incorporated in real-time Generalized Data Association - Multi Target Tracking systems (GDA-MTT) and provides an important result on the behavior of PCR5 with respect to Dempster's rule. The MatLab source code is provided in

In this report, a novel approach to intelligence and learning is introduced; this approach is based upon what we called percep tion logic. W h at we call ' perception automata ' is introduced in which learning is accom p lished at different perception resolution. Learning in this autom a ta is not heuristic, rather it guarantees the convergence of the approxim a ted function to whatever precision required. Furthe rm ore, the learning process can take place on-line and in at m o st O(log(N)) epochs, where N is the num ber of sam p les. The perception autom a ta is based on hierarchal leve ls of resolution in which each level adds som e details to the constructed function till th e final level can successfully reconstruct the whole function. This approach com b ines the favors of com putational approach in the sense that it is precise, structural and rigorous, and the features of distributed processing and adaptivity of soft com puting, as well as continuity and real-tim e response of dynam i cal system s.

This paper belongs to the area of research known as universal pre diction of individual sequences (see [2] for a review): the predictor's goal is t o compete with a wide benchmark class of prediction strategies. In the previou s papers [15] and [14] we constructed prediction strategies competitive with the important classes of Markov and stationary, respectively, continuous pred iction strategies. In this paper we consider competing against possibly discontinuous s trategies. Our main results assert the existence of prediction strategies com petitive with the Markov strategies. This paper's idea of transition from continuous to general benchma rk classes was motivated by Skorokhod's topology for the space D of "c` adl` ag" functions, most of which are discontinuous. Skorokhod's idea was to allow small d eforma-tions not only along the vertical axis but also along the horizontal ax is when defining neighborhoods. Skorokhod's topology was metrized by Kolm ogorov so that it became a separable space ([1], Appendix III; [11], p. 913), w hich allows us to apply one of the numerous algorithms for prediction with exper t advice (Kalnishkan and Vyugin's Weak Aggregating Algorithm in this paper) to construct a universal algorithm. In Section 2 we give the main definitions and state our main results, Th eo-rems 1 and 2; their proofs are given in Sections 3 and 4, respectively .

Suppose F is a normed function class of prediction strategies (the "benchmar k class"). It is well known that, under some restrictions on F, there exists a "master prediction strategy" (sometimes also called a "universal s trategy") that performs almost as well as the best strategies in F whose norm is not too large (see, e.g., [9, 5]). The "leading prediction strategies" constructed in this paper satisfy a stronger property: the loss of any prediction strategy in F whose norm is not too large exceeds the loss of a leading strategy by the diverge nce between the predictions output by the two prediction strategies. Therefo re, the leading strategy implicitly serves as a standard for prediction strategies F in F whose norm is not too large: such a prediction strategy F suffers a small loss to the degree that its predictions resemble the leading strategy's predict ions, and the only way to compete with the leading strategy is to imitate it. We start the formal exposition with a simple asymptotic result (Prop osition 1 in 2) asserting the existence of leading strategies in the problem of on -line 1 regression with the quadratic loss function for the class of continu ous limited-memory prediction strategies.

We present an unsupervised learning algorithm that mines large text corpora for patterns that express implicit semantic relations. For a given input word pair X:Y with some unspecified semantic relations, the corresponding output list of patterns is ranked according to how well each pattern Pi expresses the relations between X and Y. For example, given X=ostrich and Y=bird, the two highest ranking output patterns are "X is the largest Y" and "Y such as the X". The output patterns are intended to be useful for finding further pairs with the same relations, to support the construction of lexicons, ontologies, and semantic networks. The patterns are sorted by pertinence, where the pertinence of a pattern Pi for a word pair X:Y is the expected relational similarity between the given pair and typical pairs for Pi. The algorithm is empirically evaluated on two tasks, solving multiple-choice SAT word analogy questions and classifying semantic relations in noun-modifier pairs. On both tasks, the algorithm achieves state-of-the-art results, performing significantly better than several alternative pattern ranking algorithms, based on tf-idf.