Archives for 1999

Today I read a paper titled “Context-free multilanguages”

The abstract is:
This article is a sketch of ideas that were once intended to appear in the author’s famous series, “The Art of Computer Programming”.

He generalizes the notion of a context-free language from a set to a multiset of words over an alphabet.

The idea is to keep track of the number of ways to parse a string.

For example, “fruit flies like a banana” can famously be parsed in two ways; analogous examples in the setting of programming languages may yet be important in the future.

Today I read a paper titled “On Partially Controlled Multi-Agent Systems”

The abstract is:
Motivated by the control theoretic distinction between controllable and uncontrollable events, we distinguish between two types of agents within a multi-agent system: controllable agents, which are directly controlled by the system’s designer, and uncontrollable agents, which are not under the designer’s direct control.

We refer to such systems as partially controlled multi-agent systems, and we investigate how one might influence the behavior of the uncontrolled agents through appropriate design of the controlled agents.

In particular, we wish to understand which problems are naturally described in these terms, what methods can be applied to influence the uncontrollable agents, the effectiveness of such methods, and whether similar methods work across different domains.

Using a game-theoretic framework, this paper studies the design of partially controlled multi-agent systems in two contexts: in one context, the uncontrollable agents are expected utility maximizers, while in the other they are reinforcement learners.

We suggest different techniques for controlling agents’ behavior in each domain, assess their success, and examine their relationship.

Today I read a paper titled “Automatic processing proper names in texts”

The abstract is:
This paper shows first the problems raised by proper names in natural language processing.

Second, it introduces the knowledge representation structure we use based on conceptual graphs.

Then it explains the techniques which are used to process known and unknown proper names.

At last, it gives the performance of the system and the further works we intend to deal with..

Today I read a paper titled “Approximate Graph Coloring by Semidefinite Programming”

The abstract is:
We consider the problem of coloring k-colorable graphs with the fewest possible colors.

We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any vertex.

Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Delta.

This result can be generalized to k-colorable graphs to obtain a coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)} log^{1/2} n) colors.

Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems.

An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz theta-function.

We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the theta-function.