Paolo Ferraris

(last update: December 2008)

phone: +1 (512) 406-9827

email: otto@cs.utexas.edu

Web page: http://www.cs.utexas.edu/~otto

Current Occupation:

Google Inc. - Software Engineer. Platforms group. Developing a web application for an internal tool.

Education:

Thesis: Expressiveness of Answer Set Languages - Supervisor: Vladimir Lifschitz.

Italian Laurea (between BS and MS) in Computer Engineering, DIST, Università di Genova, Italy. December 1999. Final score: 110/110.

Research interests:

• artificial intelligence (planning, commonsense reasoning),

• logic programming (answer set programming, nonmonotonic logics),

• programming methodologies.

Papers in books (B):

1. P. Ferraris and V. Lifschitz. "Mathematical foundations of answer set programming", in We Will Show Them! Essays in Honour of Dov Gabbay, Vol 1. S. Artemov, H. Barringer, A. S. d'Avila Garcez, L. C. Lamb, and J. Woods (eds.), College Publications, pp. 615--664, 2005.

Papers in refereed journals (J):

1. P. Ferraris, J. Lee, V. Lifschitz. "Stable Models and Circumscription". Artificial Intelligence, to appear.
2. P. Cabalar, P. Ferraris. "Propositional Theories Are Strongly Equivalent to Logic Programs". Theory and Practice of Logic Programming, 7:745-759, 2007.
3. P. Ferraris, J. Lee, V. Lifschitz. "A Generalization of the Lin-Zhao Theorem". Annals of Mathematics and Artificial Intelligence, 47(1-2): 79-101, 2006.

4. P. Ferraris and V. Lifschitz. "Weight Constraints as Nested Expressions". Theory and Practice of Logic Programming, 5:45-74, 2005.

Papers in refereed conferences (C):

1. P. Ferraris. "A Logic Program Characterization of Causal Theories". In Proc. Twentieth Joint Conference in Artificial Intelligence (IJCAI), 2007.

2. P. Ferraris, J. Lee, V. Lifschitz. "A new perspective on stable models". In Proc. Twentieth Joint Conference in Artificial Intelligence (IJCAI), 2007.

3. P. Ferraris. "Answer Sets for Propositional Theories". In Proc. Eighth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR), pp. 119-131, 2005.

4. P. Ferraris. "On Modular Translations and Strong Equivalence". In Proc. Eighth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR), pp. 75-91, 2005.

5. S. Doğandağ, P. Ferraris, V. Lifschitz. "Almost Definite Causal Theories". In Proc. Seventh International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR), pp. 114-126, 2004.
   

6. P. Ferraris, E. Giunchiglia. "Planning as Satisfiability in Nondeterministic Domains". In Proc. Seventeenth National Conference on Artificial Intelligence (AAAI), 2000.

Papers in refereed workshops with proceedings (W):

1. S. Erdoğan, P. Ferraris, V. Lifschitz and W. Ren. "Why the Monkey Needs the Box: A Serious Look at a Toy Domain." In Proc. Seventh IJCAI International Workshop on Nonmontonic Reasoning, Action and Change (NRAC 2007), Hyderabad (India), January 2007.
   

2. P. Ferraris. "Causal Theories as Logic Programs". In Proc. 20th Workshop on Logic Programming (WLP 2006), Vienna, February 2006.
   

1. P. Ferraris. "Logic Programs with Propositional Connectives and Aggregates". Under review. (Journal paper)

Unpublished papers/work  in progress(U):

1. P. Ferraris. "Eliminating Weight Constraints in Polynomial Time". Unpublished draft.

2. P. Ferraris. "A Stable Model Characterization of the Logic of Causal Explanation". Work in progress.

3. P. Ferraris, J. Lee, V. Lifschitz, R. Palla. "Symmetric Splitting in the General Theory of Stable Models". Work in progress.
4. P. Ferraris. "Loop formulas in presence of arbitrary aggregates." Work in progress.
   

Invited talks:

• Seminar at the Artificial Intelligence undergraduate course, DISI, Università di Genova, Italy, December 2006.

• Answer sets for propositional theories, given at Dagstuhl Seminar on Nonmonotonic Reasoning, Answer Set Programming and Constraints, Germany, April 2005.

Research description:
My work is mainly focused on answer set programming, a recent formalism for declarative programming. It is based on the stable model/answer set semantics for logic programs, originally invented as a semantics for Prolog. Answer set programming can be used to solve difficult combinatorial search problems. This formalism is becoming more and more popular, with many researchers around the world involved.

My research contribution is in

• The concept of a stable model. The original stable model semantics of 1988 has been extended several times by introducing additional constructs, such as "choice rules" and "aggregates". The new definitions of a stable models are usually not compatible with each other, so it is not possible to have different kinds of constructs in the same logic program. We invented a simple definition of a stable model for arbitrary "propositional theories" (C3). This new semantics generalizes choice rules, aggregates and other constructs found in answer set programming languages (J4, C3, R1).

• Modular translations between logic programs. We found that two important concepts of the theory of answer sets -- modular translations and strong equivalence -- are closely related to each other (C4). We also showed that any formula in a propositional theory (see above) is strongly equivalent to a logic program (J2): as a result, we can  convert every propositional theory into a logic program in a modular way.

• Extending the stable model semantics to first-order formulas. In the past, all definitions of a stable model required, as a preliminary step, the elimination of all variables from logic programs, with a process called "grounding". We showed how an answer set can be defined without variable elimination and, more in general, for arbitrary first-order formulas (C2, J1). This opens several possibilities, such as studying properties of logic programs without the need of grounding them, and such as embedding other languages into answer set programming.
  

• Relating logic programs and causal theories. Causal theories are an important formalism for commonsense reasoning. They are syntactically and semantically similar to logic programs in the answer set semantics. However, in the past, we knew how to turn causal theories into logic programs only in very special cases. We found a linear time, modular translation from causal theories into logic programs that is applicable to arbitrary causal theories (C1, C5). This offers a way of computing the models of causal theories using answer set programming.

• Conformant planning. As my Italian Laurea thesis project, I wrote Cplan, a planner -- a system that is able to find actions leading to a given goal -- that is able to deal with incomplete initial information and nondeterministic effects of actions. (C6) (available at http://www.star.dist.unige.it/~otto/cplan.html).

Professional Activities:

• Program committee member:
  

  • Twenty-Third AAAI Conference on Artificial Intelligence, (AAAI'08)
  • Twelfth International Workshop on Nonmonotonic Reasoning (NMR'08)
  • Ninth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'07).

• Reviewer

  • Book: Handbook on Knowledge Representation, work in progress.

  • Journals:
  • Artificial Intelligence (AIJ),
  • Theory and Practice of Logic Programming (TPLP),
  •  Journal of Artificial Intelligence Research (JAIR).

  • Conferences:

  • Eighteenth National Conference on Artificial Intelligence (AAAI'02),

  • Eighteenth International Joint Conference on Artificial Intelligence (IJCAI'03),

  • Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05),

  • Twentieth National Conference on Artificial Intelligence (AAAI'05),

  • Eighth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR'05),

  • Twenty-fourth International Conference in Logic Programming (ICLP'08).

  • Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR'08)

• Research Assistant, University of Texas at Austin, 2002--2006.

• Teaching Assistant,

  • Istituto Don Bosco (Italian high school, Italy), 1999: math, technical subjects, Latin and English.

  • University of Texas at Austin, 2001--2006, with occasional instructor replacement:

    • CS388L Introduction to Mathematical Logic: graduate course (2 semesters),

    • CS341H Automata Theory: undergraduate course for computer sciences "honor" students,

    • CS336 Analysis of Programs: undergraduate course on discrete mathematics (2 semesters),

    • CS303H Logic, Sets & Functions: undergraduate introductory course for computer sciences "honor" students (held discussion sessions weekly).

• Tutor, for Italian high school and Italian university (engineering), 2000.

• Software Engineer, in Marconi Communications, a telecommunication company (Genova, Italy, Oct 2000--Jul 2001). Worked on control software (in C++) embedded in PLx40, a broadband telecommunication apparatus.

Scientific and Programming Contests:

• Contestant in 1991 at the Italian Mathematical Olympiad. Arrived in the top 23 in Italy. Took part at a week of preparation for the 2001 International Mathematical Olympiad.

• Member, from 1995 through 1999, of teams representing the University of Genova at the ACM Southwest European Regional Programming Contest. Came first several times among Italian teams and in the top positions (4th and 5th) against teams from Germany, Czech Republic, Switzerland, France, Spain and Portugal.

• World finalist in 2002 and 2003 at the ACM Collegiate Programming Contest, in a team representing The University of Texas at Austin. Finished 27th and 21st among 64-70 teams.

• 120th among 4046 participants (last time I participated) in TopCoder competitions (http://topcoder.com) and first (at least at that time) among the students of The University of Texas at Austin.

• Participating in informal programming contests on creating 1-kilobyte and 4-kilobyte games for 8-bit computers (http://www.ffd2.com/minigame). 1st place in 2004 and 2005.