Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. That is, we study the ability of an election's chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study--plurality, Condorcet, and approval voting--we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules.

We consider the problem of forecasting a new observation from the available data, which may include, e.g., all or some of the previous observation s and the values of some explanatory variables. To make the process of fore casting more vivid, we imagine that the data and observations are chosen by a play er called Reality and the forecasts are made by a player called Forecaster. T o establish properties of forecasting algorithms, the traditional theory of m achine learning makes some assumptions about the way Reality generates the ob servations; e.g., statistical learning theory [28] assumes that the data and obs ervations are generated independently from the same probability distribution. A m ore recent approach, prediction with expert advice (see, e.g., [5]), replaces th e assumptions about Reality by a comparison class of prediction strategies; a typical result of this theory asserts that Forecaster can perform almos t as well as the best strategies in the comparison class. This paper further explor es a third possibility, suggested in [11], which requires neither assumptions abo ut Reality nor a comparison class of Forecaster's strategies.

The development of effective knowledge discovery techniques has become in the recent few years a very active research area due to the important impact it has in several relevant application areas. One interesting task thereof is that of singling out anomalous individuals from a given population, e.g., to detect rare events in time-series analysis settings, or to identify objects whose behavior is deviant w.r.t. a codified standard set of "social" rules. Such exceptional individuals are usually referred to as outliers in the literature. Recently, outlier detection has also emerged as a relevant KR&R problem. In this paper, we formally state the concept of outliers by generalizing in several respects an approach recently proposed in the context of default logic, for instance, by having outliers not being restricted to single individuals but, rather, in the more general case, to correspond to entire (sub)theories. We do that within the context of logic programming and, mainly through examples, we discuss its potential practical impact in applications. The formalization we propose is a novel one and helps in shedding some light on the real nature of outliers. Moreover, as a major contribution of this work, we illustrate the exploitation of minimality criteria in outlier detection. The computational complexity of outlier detection problems arising in this novel setting is thoroughly investigated and accounted for in the paper as well. Finally, we also propose a rewriting algorithm that transforms any outlier detection problem into an equivalent inference problem under the stable model semantics, thereby making outlier computation effective and realizable on top of any stable model solver.

Designers of statistical machine translation (SMT) systems have begun to employ tree-structured translation models. Systems involving tree-structured translation models tend to be complex. This article aims to reduce the conceptual complexity of such systems, in order to make them easier to design, implement, debug, use, study, understand, explain, modify, and improve. In service of this goal, the article extends the theory of semiring parsing to arrive at a novel abstract parsing algorithm with five functional parameters: a logic, a grammar, a semiring, a search strategy, and a termination condition. The article then shows that all the common algorithms that revolve around tree-structured translation models, including hierarchical alignment, inference for parameter estimation, translation, and structured evaluation, can be derived by generalizing two of these parameters -- the grammar and the logic. The article culminates with a recipe for using such generalized parsers to train, apply, and evaluate an SMT system that is driven by tree-structured translation models.

We introduce a logic for reasoning about evidence that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence.

It is well known that the standard model of knowledge based on possible worlds is subject to the problem of logical omniscience, that is, the agents know all the logical consequences of the ir knowledge [Fagin, Halpern, Moses, and V ardi 1995, Chapter 9]. Thu s, possible-world definitions of knowledge make it difficult to reason about the knowledge tha t agents need to explicitly compute in order to make decisions and perform actions, or to capture si tuations where agents want to reason about the knowledge that other agents need to explicitly com pute in order to perform actions. This observation leads to a distinction between two forms of knowledge, implicit knowledge and explicit knowledge (or resource-bounded knowledge), a distinction long recog nized [Rosenschein 1985]. The classical AI approach known as the interpreted symbolic structures approach, where knowledge is based on information stored in data structures of the agent, can be seen as an instance of explicit knowledge. In contrast, the situated automata approach, which interprets knowledge based on information carried by the state of the machine, can be seen as an instance of implicit knowledge. Levesque [1984] makes a similar distinction bet ween implicit belief and explicit belief. While the possible-worlds approach is taken as the standard model for implicit knowledge, there is no standard model for explicit knowledge.

It is well known that, under certain conditions, it is possible to split logic programs under stable model semantics, i.e. to divide such a program into a number of different "levels", such that the models of the entire program can be constructed by incrementally constructing models for each level. Similar results exist for other non-monotonic formalisms, such as auto-epistemic logic and default logic. In this work, we present a general, algebraicsplitting theory for logics with a fixpoint semantics. Together with the framework of approximation theory, a general fixpoint theory for arbitrary operators, this gives us a uniform and powerful way of deriving splitting results for each logic with a fixpoint semantics. We demonstrate the usefulness of these results, by generalizing existing results for logic programming, auto-epistemic logic and default logic.

We have developed a web-based human-computer-intera ction system with natural language for foreign language learning: CSI EC (Computer Simulator in Educational Communication) [1]. The kernel of this system is the natural language understanding mechanism (NLML, NLOMJ and NLDB) and the communicational response (CR). NLML(Natural Language Markup Languag e) is a markup language to describe the grammar of an expression in a natur al language. It is produced to an expression of this natural language by a parser wri tten according to the grammar rules and lexicon of this language [2]. We use English as the experiment language in our system. For example, the NLML for the sentence " I come " is

Abstract-- We derive a hybrid feedback control law for the lateral leg spring (LLS) model so that the center of mass of a legged runner follows a curved path in horizontal plane. The control law enables the runner to change the placement and th e elasticity of its legs to move in a desired direction. Stable motion along a curved path is achieved using curvature, bearing and relative distance between the runner and the curve as feedba ck. Constraints on leg parameters determine the class of curves that can be followed. We also derive an optimal control law that stabilizes the orientation of the runner's body relative to the velocity of the runner's center of mass.

Categorical data clustering is an important research problem in pattern recognition and data mining. The k -modes algorithm [1] extends the k -means paradigm to cluster categorical data by using (1) a simple matching dissimilarity measure for categorical objects, (2) modes instead of means for clusters, and (3) a frequency-based method to update modes in the k -means fashion to minimize the cost function of clustering. The k -modes algorithm is widely used in real world applications due to its efficiency in dealing with large categorical database. In standard k -modes algorithm, a simple matching similarity measure is used, in which the distance is either 0 or 1. Such simple matching dissimilarity measure doesn't consider the implicit similarity relationship embedded in categorical values, which will result in a weaker intra-cluster similarity by allocating less similar objects to the cluster. To illustrate this fact, let's consider the following example shown in Fig.1. Example 1: In this artificial example, the dataset is described with 3 categorical attributes A1, A2,and A3, and there are two clusters with their modes. Assuming that we have to allocate a data object Y = [a, p, w] to either cluster 1 or cluster 2. According to the k -modes algorithm, we can assign Y to either cluster 1 or cluster 2 since these two clusters have the same mode. However, from the viewpoint of intra-cluster simila rity, it is more desirable to allocate Y to cluster 1.