Journal of Arti ial In telligen e Resear h 20 (2003) 139-144 Submitted 09/03; published 12/03 Commentary PDDL 2.1: Represen tation vs. Computation H e tor Gener he tor.geffner ICREA { Universitat Pomp eu F abr a Pase o de Cir unvala ion 8 08003 Bar elona, Sp ain Abstra t I ommen t on the PDDL 2.1 language and its use in the planning omp etition, fo using on the hoi es made for a ommo dating time and on urren y . I also dis uss some metho d-ologi al issues that ha v e to do with the mo v e to w ard more expressiv e planning languages and the balan e needed in planning resear h b et w een seman ti s and omputation. In tro du tion F o x and Long should b e thank ed and ongratulated for their eort in organizing and running the 3rd In ternational Planning Comp etition. They ame up with an extended planning language along with a n um b er of new problems and domains that hallenged existing planners and will ertainly hallenge future planners as w ell.

Journal of Arti ial In telligen e Resear h 21 (2004) 287-317 Submitted 06/03; published 03/04 IDL-Expressions: A F ormalism for Represen ting and P arsing Finite Languages in Natural Language Pro essing Mark-Jan Nederhof markjan let.r ug.nl F a ulty of A rts, University of Gr oningen P.O. Dept. of Information Engine ering, University of Padua via Gr adenigo, 6/A I-35131 Padova, Italy Abstra t W e prop ose a formalism for represen tation of nite languages, referred to as the lass of IDL-expr essions, whi h om bines on epts that w ere only onsidered in isolation in existing formalisms. The suggested appli ations are in natural language pro essing, more sp e i ally in surfa e natural language generation and in ma hine translation, where a sen ten e is obtained b y rst generating a large set of andidate sen ten es, represen ted in a ompa t w a y, and then ltering su h a set through a parser. W e study sev eral formal prop erties of IDL-expressions and ompare this new formalism with more ...

F or sev eral small lusters of no des upp er and lo w er b ounds on the marginal v alues are omputed indep enden tly of the rest of the net w ork. The range of allo w ed proba-bilit y distributions o v er the surrounding no des is restri ted using earlier omputed b ounds. As w e will sho w, this an b e onsidered as a set of onstrain ts in a linear programming problem of whi h the ob je tiv e fun tion is the marginal probabilit y of the en ter no des. In this w a y kno wledge ab out the maginals of neigh b ouring lusters is passed to other lusters thereb y tigh tening the b ounds on their marginals. W e sho w that sharp b ounds an b e obtained for undire ted and dire ted graphs that are used for pra ti al appli ations, but for whi h exa t omputations are infeasible. F or small net w orks an exa t omputation of the marginal probabilities for ertain no des is feasible (see, for example Zhang & P o ole, 1994). Unfortunately, due to an exp onen tial s aling of the omputational omplexit y, these exa t algorithms so on fail for somewhat more omplex and more realisti net w orks. T o deal with this omputational problem t w o main streams an b e distinguished. Firstly, there is the approa h of appro ximating the exa t solution.

Simple conceptual graphs are considered as the kernel of most knowledge representation formalisms built upon Sowa's model. Reasoning in this model can be expressed by a graph homomorphism called projection, whose semantics is usually given in terms of positive, conjunctive, existential FOL. We present here a family of extensions of this model, based on rules and constraints, keeping graph homomorphism as the basic operation. We focus on the formal definitions of the different models obtained, including their operational semantics and relationships with FOL, and we analyze the decidability and complexity of the associated problems (consistency and deduction). As soon as rules are involved in reasonings, these problems are not decidable, but we exhibit a condition under which they fall in the polynomial hierarchy. These results extend and complete the ones already published by the authors. Moreover we systematically study the complexity of some particular cases obtained by restricting the form of constraints and/or rules.

Order of magnitude reasoning - reasoning by rough comparisons of the sizes of quantities - is often called 'back of the envelope calculation', with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form 'Points a and b are much closer together than points c and d.' We prove that this algorithm can be applied if `much closer together' is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.