Texas Action Group at Austin

Texas Action Group at Austin is a research group within the Department of Computer Science of the University of Texas at Austin. It is part of a larger community, Texas Action Group, which includes participants from many parts of the world. Most of our current work deals with the theory of answer set programming (ASP). We are interested in the semantics of ASP programming constructs and in the methodology of developing reliable, provably correct ASP programs.

Current and Former Members of Texas Action Group at Austin with Their Students
at the International Conference on Logic Programming in Istanbul, Turkey (2013)

Pictured (from left to right): Mike Bartholomew, Joohyung Lee, Selim Erdoğan,
Zeynep Gözen Sarıbatur, Vladimir Lifschitz, Esra Erdem, Amelia Harrison, Fangkai Yang.

What is Answer Set Programming?

Programmers usually solve computational problems by designing algorithms and encoding them in an implemented programming language. Research in artificial intelligence and computational logic has led to an alternative, "declarative" approach to programming, which does not involve encoding algorithms. A program in a declarative language only describes what is counted as a solution. Given such a description, a declarative programming system finds a solution by the process of automated reasoning.

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems, where the goal is to find a solution among a large, but finite, number of possibilities. Such problems arise in many areas of science and techology. ASP is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers--programs for generating stable models--are used to perform search.

History of Answer Set Programming in Austin

1988: The concept of a stable model is introduced by Michael Gelfond (then at UT El Paso) and Vladimir Lifschitz (then at Stanford University). Three years later, Vladimir moved to Austin.

1993: Stable models are applied to the problem of describing dynamic domains in artificial intelligence.

1994: Computing stable models by splitting is introduced.

1999: Answer set programming is applied to planning.

2001: Strong equivalence of logic programs is defined.

2002: Esra Erdem defends the dissertation on Theory and Applications of Answer Set Programming. This was the first dissertation on answer set programming anywhere in the world.

2003: Tight logic programs are investigated. Answer set programming is applied to reconstructing the evolutionary history of Indo-European languages. The concept of a loop formula is extended to disjunctive logic programs. Answer set solver CMODELS is released.

2004: Answer set programming is applied to protocol insecurity problems. The 1988 paper on stable models receives a Most Influential Paper in 20 Years award from the Association for Logic Programming.

2005: Relationship between weight constraints and nested expressions is investigated. The concept of a stable model is extended to arbitrary propositional theories and is used to define a new semantics of aggregates.

2006: Answer set programming is applied to natural language understanding.

2007: Answer set programming is applied to the history of Chinese dialects and to historical zoology. The concept of a stable model is extended to first-order formulas. Paolo Ferraris defends the dissertation on Expressiveness of Answer Set Languages.

2008: A survey of answer set programming is presented at the AAAI Conference on Artificial Intelligence.

2009: Symmetric splitting is defined. A new decidable class of finitely ground programs is found.

2010: Yuliya Lierler defends the dissertation on SAT-based Answer Set Programming.

2012: Answer set programming is applied to parsing natural language and to null values in deductive databases.

2013: Answer set programming is applied to recognizing textual entailment.

2014: Answer set programming is applied to mobile robot planning.

2015: Stable models of infinitary formulas are used to define the semantics of the ASP grounder GRINGO.

2016: Supersafe rules are investigated. A new approach to proving infinitary formulas is proposed. A new ASP programming methodology is introduced.