TAG

What Is TAG? - Part I

Michael Gelfond and Vladimir Lifschitz

Texas Tech University and University of Texas at Austin

Area Editor: Son Cao Tran

The PDF-version of this article can be found here.

A Brief History

On December 9, 1998 we e-mailed the following message to several students and friends:

  Subject: Would you like to join TAG?

                     Texas Action Group:
           The University of Texas Research Group
          for the Study of Reasoning about Actions

  Texas Action Group (TAG) is a newly organized group of
  researchers interested in the study of formal and automated
  reasoning about the effects of actions using action
  languages, logic programming under the answer set semantics,
  and related ideas.  It is led by Michael Gelfond (University
  of Texas at El Paso) and Vladimir Lifschitz (University of
  Texas at Austin).  TAG members will use a mailing list and a
  web page to communicate on topics of common interest.

  Although TAG is being created primarily for the benefit of
  graduate students and faculty of the University of Texas,
  membership is open to anyone.

  If you would like to join TAG, please send a request to
  Vladimir Lifschitz (vl@cs.utexas.edu).  Then your name and
  e-mail address will be placed on the TAG home page; we will
  also provide a link to your personal page if your message
  includes the URL.

  Please forward this announcement to your colleagues who you
  think may be willing to participate.

Today, more than five years later, this ``Texas group'' includes many participants from other parts of the United States and from other countries, including Austria, Canada, China, Germany, Italy, Mexico, Spain and Turkey. The topics we are discussing now include many subjects other than reasoning about actions, but one thing has not changed: our interests are centered around the use of logic programs as a knowledge representation tool. Many of our technical discussions are related to answer set programming.

For the most part, TAG members communicate with each other electronically, but we do meet and talk face to face once in a while. More than 30 TAG members met last August at a meeting organized in New Mexico by Enrico Pontelli and Tran Cao Son. More than 20 participants of LPNMR-7 took part in a traditional TAG lunch in Fort Lauderdale in January of 2004.

To learn more about TAG, check our home page

http://www.cs.utexas.edu/tag
and the web page of the TAG meeting in New Mexico:
http://www.cs.nmsu.edu/~tson/TAG03/

(Would you like to join us?)

Texas Action Group at Austin

Vladimir's ``TAG team'' includes four doctoral students this year: Selim Erdogan, Paolo Ferraris, Joohyung Lee and Wanwan Ren. Here are some of the research topics that we in Austin are interested in.

$\bullet$ Applications of logic programming to historical linguistics.

The evolutionary history of families of natural languages, such as the Indo-European family, can be described in terms of ``temporal phylogenetic networks.'' These networks contain information about genetic relationships between linguistic communities and about interactions between them, including chronological information. The discrete data from a network can be conveniently represented in answer set programming languages; for the chronological part, constraint programming languages are more appropriate. In our experiments, the ASP system CMODELS and the CP system ECLIPSE work together to solve computational problems from historical linguistics.

$\bullet$ Why is exchanging hats irrelevant?

In one of the enhancements of the Missionaries and Cannibals problem introduced by John McCarthy, missionaries have hats, and they can exchange them, if they wish. This action is irrelevant, of course, if the goal is to cross the river. We are looking at the ``missionaries with hats'' domain represented in action language C+, closely related to logic programming, and we'd like to identify the syntactic features of this domain that make the action of exchanging hats irrelevant.

$\bullet$ General purpose database of properties of actions.

Commonsense reasoning domains involving actions, such as the blocks world and the Missionaries and Cannibals domain, have many common features. For instance, they often involve physical objects that change their positions in space. We would like to isolate the concepts and principles that these domains have in common and to compile a database of such principles, stated in a general form, and expressed in action language C+.

$\bullet$ Semantics of aggregates in ASP languages.

Cardinality and weight constraints in the language of lparse are the best known examples of aggregate constructs in the input languages of answer set solvers. Such constructs are used routinely in applications of ASP. Several definitions of the semantics of aggregates described in the literature are not always equivalent to each other, and in some cases their properties seem unintuitive. We'd like to clarify the relationship between various versions of the semantics of aggregates, and to find the ``right'' definition.

$\bullet$ Efficient elimination of weight constraints.

Weight constraints can be eliminated from a logic program in favor of additional atoms. The answer set solver cmodels uses this fact to reduce the problem of computing answer sets for programs with weight constraints to SAT. In the special case of cardinality constraints, the elimination process is efficient, in the sense that it does not lead to a significant increase in the size of the program. But in the general case the increase in size can be exponential. We are working on a translation that is efficient for arbitrary weight constraints.

$\bullet$ Relationship between modular translations and strong equivalence.

We are interested in general properties of the translations that do not introduce additional atoms, but rather turn a logic program into an equivalent program-a program with exactly the same answer sets. For instance, there exists a modular (rule-by-rule) transformation that turns any program with weight constraints into a program with nested expressions. Another example of a modular equivalent transformation is given by the process of converting programs with monotone cardinality atoms into programs with cardinality constraints. There seems to be a close relationship between modular equivalent transformations and the concept of strong equivalence. We would like to make this idea precise.

$\bullet$ Loop formulas.

The invention of loop formulas by Fangzhen Lin and Yuting Zhao was perhaps the most significant event in the area of LPNMR in recent years. The related work to which members of the Austin team have contributed is described in the papers ``Loop formulas in disjunctive logic programs'' (Proc. ICLP'03), ``Nondefinite vs definite causal theories'' (Proc. LPNMR-7), ``Loop formulas for circumscription'' (to appear in Proc. AAAI'04), and ``Why are there so many loop formulas?'' (to appear in ACM Transactions on Computational Logic). We plan to further explore this intriguing idea and its potential applications.

More information about the Austin group can be found at its web page:

http://www.cs.utexas.edu/users/tag/