Definitions First we recall relevent definitions. This objective function is piece-wise linear and convex. This objective function is piece-wise linear and convex. A matrix game is given by a (payoff) matrix A. To solve a matrix game is to find a row p (an optimal strategy for the row player), a column q (an optimal strategy for the column player), and a number v such that p = ( p The number v is known as the value of game. The pair ( p, q) is known as an equilibrium for the matrix game.

We are presenting a text analysis tool set that allows analysts in various fields to sieve through large collections of multilingual news items quickly and to find information that is of relevance to them. For a given document collection, the tool set automatically clusters the texts into groups of similar articles, extracts names of places, people and organisations, lists the user-defined specialist terms found, links clusters and entities, and generates hyperlinks. Through its daily news analysis operating on thousands of articles per day, the tool also learns relationships between people and other entities. The fully functional prototype system allows users to explore and navigate multilingual document collections across languages and time.

We show that the unification problem `is there a substitution instance of a given formula that is provable in a given logic?' is undecidable for basic modal logics K and K4 extended with the universal modality. It follows that the admissibility problem for inference rules is undecidable for these logics as well. These are the first examples of standard decidable modal logics for which the unification and admissibility problems are undecidable. We also prove undecidability of the unification and admissibility problems for K and K4 with at least two modal operators and nominals (instead of the universal modality), thereby showing that these problems are undecidable for basic hybrid logics. Recently, unification has been introduced as an important reasoning service for description logics. The undecidability proof for K with nominals can be used to show the undecidability of unification for boolean description logics with nominals (such as ALCO and SHIQO). The undecidability proof for K with the universal modality can be used to show that the unification problem relative to role boxes is undecidable for Boolean description logic with transitive roles, inverse roles, and role hierarchies (such as SHI and SHIQ).

We present an exploratory tool that extracts person names from multilingual news collections, matches name variants referring to the same person, and infers relationships between people based on the co-occurrence of their names in related news. A novel feature is the matching of name variants across languages and writing systems, including names written with the Greek, Cyrillic and Arabic writing system. Due to our highly multilingual setting, we use an internal standard representation for name representation and matching, instead of adopting the traditional bilingual approach to transliteration. This work is part of the news analysis system NewsExplorer that clusters an average of 25,000 news articles per day to detect related news within the same and across different languages.

A typical result of competitive on-line prediction says that, for a giv en benchmark class of prediction strategies, there is a prediction strategy that performs almost as well as the best prediction strategies in the benchmark cla ss. For simplicity, in this paper the performance of a prediction strategy will be measured by the cumulative squared distance between its predictions a nd the true observations, assumed to be real (occasionally complex) numbers . Different methods of competitive on-line predictions (such as Gradient Desce nt, following the perturbed leader, strong and weak aggregating algorithms, d efensive forecasting, etc.) tend to have their narrow "area of expertise": eac h works well for benchmark classes of a specific "size" but is not readily applicable to c lasses of a different size. In this paper we will apply a simple general method based on metric ent ropy to benchmark classes of a wide range of sizes. Typically, this method does not give optimal results, but its results are often not much worse than those given by specialized methods, especially for benchmark classes that are not too massive.

The paper aims at emphasizing that, even relaxed, the hypothesis of compositionality has to face many problems when used for interpreting natural language texts. Rather than fixing these problems within the compositional framework, we believe that a more radical change is necessary, and propose another approach.

In this paper, we study the construction and transformation of two-dimensional persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the context of moving autonomous agent formations, persistence characterizes the efficacy of a directed structure of unilateral distances constraints seeking to preserve a formation shape. Analogously to the powerful results about Henneberg sequences in minimal rigidity theory, we propose different types of directed graph operations allowing one to sequentially build any minimally persistent graph (i.e. persistent graph with a minimal number of edges for a given number of vertices), each intermediate graph being also minimally persistent. We also consider the more generic problem of obtaining one minimally persistent graph from another, which corresponds to the on-line reorganization of an autonomous agent formation. We prove that we can obtain any minimally persistent formation from any other one by a sequence of elementary local operations such that minimal persistence is preserved throughout the reorganization process.

Studies of different term extractors on a corpus of the biomedical domain revealed decreasing performances when applied to highly technical texts. The difficulty or impossibility of customising them to new domains is an additional limitation. In this paper, we propose to use external terminologies to influence generic linguistic data in order to augment the quality of the extraction. The tool we implemented exploits testified terms at different steps of the process: chunking, parsing and extraction of term candidates. Experiments reported here show that, using this method, more term candidates can be acquired with a higher level of reliability. We further describe the extraction process involving endogenous disambiguation implemented in the term extractor YaTeA.

An approach to the classification problem of machine learning, based on building local classification rules, is developed. The local rules are considered as projections of the global classification rules to the event we want to classify. A massive global optimization algorithm is used for optimization of quality criterion. The algorithm, which has polynomial complexity in typical case, is used to find all high--quality local rules. The other distinctive feature of the algorithm is the integration of attributes levels selection (for ordered attributes) with rules searching and original conflicting rules resolution strategy. The algorithm is practical; it was tested on a number of data sets from UCI repository, and a comparison with the other predicting techniques is presented.

We introduce and study logic programs whose clauses are buil t out of monotone constraint atoms . We show that the operational concept of the one-step provab ility operator generalizes to programs with monotone constraint atoms, bu t the generalization involves nondeterminism. Our main results demonstrate that our form alism is a common generalization of (1) normal logic programming with its semantics o f models, supported models and stable models, (2) logic programming with weight atoms ( lparse programs) with the semantics of stable models, as defined by Niemel a, Simons an d Soininen, and (3) of disjunctive logic programming with the possible-model semant ics of Sakama and Inoue. To appear in Theory and Practice of Logic Programming (TPLP).