1st Workshop on

Tabulation in Parsing and Deduction

TAPD'98

---

Paris, France
April 2-3, 1998

---

Organized by INRIA
in collaboration with CEDRIC of CNAM
and the support of Compulog and Xerox Research Center Europe

---

Motivations

Tabulation techniques are becoming a common way to deal with highly redundant computations occurring, for instance, in Natural Language Processing, Logic Programming, Deductive Databases, or Abstract Interpretation, and related to phenomena such as ambiguity. non-determinism, or domain ordering.

Different approaches, including for example Chart Parsing, Magic-Set rewriting, Memoization, and Dynamic Programming, have been proposed whose key idea is to keep traces of computations to achieve computation sharing and loop detection. In addition, tabulation also offers more flexibility to investigate new parsing or proof strategies and to represent ambiguity by shared structures (Shared Proof or Parse Forest).

The first objective of this workshop is to compare and discuss these different approaches. The second objective is to present tabulation and tabular systems to potential users in different application areas. One major area of application is Natural Language Processing, where tabulation has been known for a long time (CKY, Earley, chart parsing). However, sophisticated tabulation techniques are required for the more and more complex grammatical formalisms now used in NLP (unification, constraints, structural complexity). Contributions in other areas, such as picture parsing, genome analysis, or complete deduction techniques, are also encouraged.

Topics (not exclusive)

• Tabulation Techniques:
  Chart Parsing, Tabling, Memoization, Dynamic Programming, Magic Set, Generic Fix-Point Algorithms.
• Applications:
  Parsing, Generation, Logic Programming, Deductive Databases,
  Abstract Interpretation, Deduction in Knowledge Bases, Theorem Proving
• Static Analysis:
  How to improve tabular evaluation
• Parsing or resolution strategies.
• Efficiency issues:
  Dealing with large tables (structure sharing, term indexing), Execution models Exploiting the domain ordering
• Shared structures (parse or proof forest):
  their formal analysis, representation and processing.

Workshop Format

Submission Procedure

The collection of selected papers will be available at the workshop. After the workshop, authors are invited to submit a full paper for publication in a special issue of the Journal of Logic Programming oriented towards Natural Language Processing. The authors should note that this second submission will be treated according to the standards of the Journal of Logic Programming.

Important Dates

    Submission of contributions:            12 December  1997       
    Notification of acceptance:             26 January   1998
    Final versions due:                     20 February  1998

Program Committee

• Bernard Lang (chairman) -- INRIA, France
• Francois Bry -- University of Munich, Germany
• Eric de la Clergerie -- INRIA, France
• Marc Dymetman -- Xerox, France
• Mark Johnson -- Brown University, USA
• Baudouin Le Charlier -- University of Namur, Belgium
• Mark Jan Nederhof -- University of Groningen, NL
• David Rosenblueth -- University of Mexico, Mexico
• Manuel Vilares -- University of La Coruna, Spain
• David S. Warren -- University of New York at Stony Brook, USA

Organizing Committee

• Francois Barthelemy -- CNAM, Paris, France
• Eric de la Clergerie-- INRIA, Rocquencourt, France
• Bernard Lang-- INRIA, Rocquencourt, France
• Manuel Vilares-- University of La Coruna, Spain

Local Organization

• Claudie Thenault -- INRIA Rocquencourt, Relations Exterieures, France

For more information, please contact:

Scientific Secretariat

   Eric de la Clergerie
   INRIA Rocquencourt                Phone: +33 1 39 63 54 10
   Domaine de Voluceau - BP 105      Fax: +33 1 39 63 53 30
   78153 Le Chesnay Cedex (France)   E-mail: Eric.Clergerie@inria.fr

Local organisation

   Claudie Thenault 
   INRIA Rocquencourt                         
   Relations Extérieures / Cours-Colloques   Phone: +33 1 39 63 56 75         
   Domaine de Voluceau - BP 105              Fax: +33 1 39 63 56 38
   78153 Le Chesnay Cedex (France)           E-mail: symposia@inria.fr

WWW homepage: http://pauillac.inria.fr/~clerger/tapd.html