Mini-Symposium on Algorithms and Knowledge Representation

  • 2010-06-01

Talks: Online Algorithms for Packet Routing, Representing Preferences Among Sets, Learning semantic representations of words and sentences using inverse lambda

The Institute of Information Systems cordially invites you to the following talks:

14:00 // Online Algorithms for Packet Routing in Lines and Grids //

(Joint work with Moti Medina. Part of this work will be presented in ICALP 2010.)

We deal with the problem of routing packets in uni-directional two dimensional grids with bounded buffers or without buffers. The goal is to maximize the number of delivered packets. We present the first online algorithm with a poly-logarithmic competitive ratio for this problem. Our algorithm is deterministic and centralized.

We also outline a randomized packet routing algorithm for a line that achieves a logarithmic competitive ratio.

15:00 // Representing Preferences Among Sets //

(joint work with Gerd Brewka and Stefan Woltran)

We study methods to specify preferences among subsets of a set (a universe). The methods we focus on are of two types. The first one assumes the universe comes with a preference relation on its elements and attempts to lift that relation to subsets ofthe universe. That approach has limited expressivity but results in orderings that capture interesting general preference principles. The second method consists of developing formalisms allowing the user to specify `atomic’’ improvements, and generating from them preferences on the powerset of the universe. We show that the particular formalism we propose is expressive enough to capture the lifted preference relations of the first approach, and generalizes propositional CP-nets. We discuss the importance of domain -independent methods for specifying preferences on sets for knowledge representation formalisms, selecting the formalism of argumentation frameworks as an illustrative example.

17:00 // Learning semantic representations of words and sentences using inverse lambda: using answer set programming as a target language //

(Work in Progress)

Our long term goal is to develop ways to translate natural language to formal knowledge representation (KR) languages. Currently, research in KR has not zeroed in on a single language that would be appropriate for all the nuances of a natural language. Hence, depending on the nuances in a text and our purpose different KR languages may be appropriate. Here, we first present an inverse lambda operator that allows us to compute F given G and H such that F@G = H or G@F = H. We then present a method that uses this operator, a notion of generalization, and an adoption of a learning methodology from the literature to translate natural language sentences to ASP. This allows semantic characterization of normative statements, exceptions and other features one often encounters in many knowledge rich domains.

With kind support of the Wolfgang-Pauli-Institute


Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!