Preference logic grammars.
The addition of preferences to normal logic programs is a convenient way to represent many aspects of default reasoning. If the derivation of an atom A1 is preferred to that of an atom A2, a preference rule can be defined so that A2 is derived only if A1 is not. Although such situations can be modelled directly using default negation, it is often easier to define preference rules than it is to add negation to the bodies of rules. As first noted by Govindarajan et al. [Proc. Internat. Conf. on Logic Programming, 1995, pp. 731-746], for certain grammars, it may be easier to disambiguate parses using preferences than by enforcing disambiguation in the grammar rules themselves. In this paper we define a general fixed-point semantics for preference logic programs based on an embedding into the well-founded semantics, and discuss its features and relation to previous preference logic semantics. We then study how preference logic grammars are used in data standardization, the commercially important process of extracting useful information from poorly structured textual data. This process includes correcting misspellings and truncations that occur in data, extraction of relevant information via parsing, and correcting inconsistencies in the extracted information. The declarativity of Prolog offers natural advantages for data standardization, and a commercial standardizer has been implemented using Prolog. However, we show that the use of preference logic grammars allow construction of a much more powerful and declarative commercial standardizer, and discuss in detail how the use of the non-monotonic construct of preferences leads to improved commercial software.
Introduction
Context-free grammars (CFGs) have traditionally been used for specifying the syntax of a language,
while logic is generally the formalism of choice for specifying semantics (meaning). Logic grammars
combine these two notations, and can be used for specifying syntactic and semantic constraints in
a variety of parsing applications, from programming languages to natural languages to documents
layouts. Several forms of logic grammars have been researched over the last two decades [AD89].
Basically, they extend context-free grammars in that they generally allow: (i) the use of arguments
with nonterminals to represent semantics, where the arguments may be terms of some logic; (ii)
the use of unification to propagate semantic information; (iii) the use of logical tests to control the
application of production rules.
An important problem in these applications is that of resolving ambiguity-syntactic and
semantic. An example of syntactic ambiguity is the 'dangling else' problem in programming language
syntax. To illustrate, consider the following CFG rules for if-then and if-then-else statements in
procedural programming languages:
!ifstmt? ::= if !cond? then !stmtseq? j if !cond? then !stmtseq? else !stmtseq?
Given a sentence of the form if cond1 then if cond2 then assign1 else assign2, there are two possible
parses depending upon which then the else is paired with (parentheses are used below to indicate
if cond1 then (if cond2 then assign1 else assign2)
if cond1 then (if cond2 then assign1) else assign2
While one can re-design the language to avoid the ambiguity, this example typifies a form of ambiguity
that arises in other settings as well. For the above language of if-then-else statements, in general it
is not easy to alter the grammar to avoid ambiguity; doing so involves the introduction of several
additional nonterminals, which not only destroys the clarity of the original ambiguous grammar,
but also results in a less efficient parsing scheme. In such ambiguous grammars, we usually have a
preferred parse in mind. In the above example, we would like to pair up each else with the closest
previous unpaired then. We present in this paper a general means of stating such preferences.
We develop our methodology starting from a particular form of logic grammar called definite
clause grammar (DCG). (We also consider a generalization of DCGs called definite clause translation
grammars (DCTGs) [Abr84].) The primary contribution of this paper is in providing a modular and
declarative means of specifying the criteria to be used in resolving ambiguity in a logic grammar.
These criteria are understood using the concept of preference, hence we call the resulting grammars
preference logic grammars (PLG). In essence, a PLG is a logic grammar where some of the nonterminals
have one or more arbiter (preference) rules attached to them. Whenever there are multiple
parses for some sentence derivable from a nonterminal, these arbiter clauses will dictate the most preferred
parse for the sentence. Just as definite clause grammars can be translated into logic programs,
preference logic grammars can be translated into preference logic programs which we introduced
in our earlier work [GJM95, GJM96, Gov97]. The paradigm of preference logic programming was
introduced in order to obtain a logical means of specifying optimization problems. The operational
semantics of preference logic programs constructs the optimal parse by keeping track of alternative
parses and pruning parses that are suboptimal.
We first provide some simple examples to illustrate the use of PLGs for handling ambiguities
in programming-language grammars, and then discuss two applications of preference logic grammars:
optimal parsing and natural language parsing. Each of these topics is a substantial research area in
its own right, and we only give a brief introduction to the issues in this paper. Optimal parsing is an
extension of the standard parsing problem in that costs are associated with the different (ambiguous)
parses of a string, and the preferred parse of the string is the one with least cost. Many applications
such as optimal layout of documents [BMW92], code generation [AGT89], etc., can be viewed as
optimal parsing problems. We show in this paper how the criteria for laying out paragraphs-which
a formatter such as would use [KP81]-can be specified declaratively using a logic
grammar. In the area of ambiguity resolution, we illustrate the use of PLG resolving ambiguity in
natural language sentences using the problem of prepositional attachment. We show how preference
clauses provide a simple and elegant way of expressing preferences such as minimal attachment and
right association, and discuss some of the problems associated with ambiguity resolution.
The remainder of this paper is organized as follows: section 2 presents preference logic grammars
and illustrates their use for ambiguity resolution of programming language grammars. Section 3
introduces preference logic programs and shows how preference logic grammars can be translated into
preference logic programs. Section 4 illustrates the use of PLGs in optimal parsing and ambiguity
resolution in natural language sentences. Finally, section 5 contains the conclusions and directions
for further research. We assume that the reader is familiar with basic concepts in logic programming
and definite-clause grammars. A good introductory treatment of logic programming including its
theory can be found in [Llo87].
Preference Logic Grammars
We describe the syntax of preference logic grammars, and illustrate their use with examples from
programming language grammars. Since preference logic grammars are based upon definite clause
grammars (DCGs), we will briefly describe DCGs first.
Clause Grammars. A definite-clause grammar (DCG) is basically an extension of a
context-free grammar wherein each nonterminal is optionally accompanied by one or more arguments.
For the purpose of this paper, we consider two forms of DCG rules:
literal -? [ ].
literal -? literal 1 literal k .
The first form of DCG rule corresponds to a null production. Each literal is either a terminal symbol
of the form
or a nonterminal with arguments of the form
where terms is a sequence of zero or more term which (as usual) is built up of constants, variables,
and constructors. In general, on the right-hand side of a DCG rule it is legal to have any sequence
of Prolog goals enclosed with f and g. Such a goal sequence may occur in any position that a literal
may occur.
To illustrate a definite-clause grammar, we show below how one can encode the BNF of
section 1. Assuming definitions for the nonterminals expr, cond, and var, the ambiguous DCG is as
follows:
stmtseq(S) -? stmt(S).
stmt(S) -? assign(S).
stmt(S) -? ifstmt(S).
The above DCG also illustrates parse tree construction: the argument of each nonterminal
serves to carry the parse tree for the sentence spanned by the nonterminal. For example, the term
if(C,T) can be thought of as representing the parse tree for an if-then statement, while the term
if(C,T,E) can be thought of as representing the parse tree for an if-then-else statement. Here, C,
T, and E stand for the parse trees for the condition-part, then-part, and else-part respectively.
clause grammars can be translated in definite clause logic programs in a straightforward
way [PW80]: One definite clause is created per DCG rule. Each nonterminal with n arguments
in the DCG rule is translated into a predicate with n+2 arguments. The two extra arguments carry
respectively the input list to be parsed and the remaining list after some initial prefix of the input
list has been parsed. These two extra arguments are made the last two arguments of the predicate.
We illustrate the translated program for the above DCG:
stmtseq(S,I,O) :- stmt(S,I,O).
stmtseq(ss(S,Ss),I,O) :- stmt(S,I,[;-O1]), stmtseq(Ss,O1,O).
stmt(S,I,O) :- assign(S,I,O).
stmt(S,I,O) :- ifstmt(S,I,O).
assign(assign(V,E),I,O) :- var(V,I,[:=-O1]), expr(E,O1,O).
stmtseq(T,O1,O).
stmtseq(T,O1,[else-O2]),
stmtseq(E,O2,O).
Preference Logic Grammars. A preference logic grammar is a definite clause grammar in which
each nonterminal n is optionally accompanied by one or more preference clauses of the form:
where each L i is a positive or negative atom of the form p(terms), where p is a predicate. This form
of the rule states that when a sentence spanned by nonterminal n has two different parses, the parse
corresponding to -
t is less preferred than the one corresponding to - u provided the condition given
by (Later, we will also illustrate show how one can extend definite clause
translation grammars with preference clauses.)
To ilustrate PLGs, we can extend the above DCG with a preference clause to resolve the
'dangling else' ambiguity. As explained in section 1, to resolve the ambiguity we need to specify the
criterion that each else pairs up with the closest previous unpaired then. We can state this criterion
by the following preference clause:
This rule states that when an if-then-else statement has two different parses, the parse corresponding
to the tree if(C,if(C1,T),E) is less preferred than the one corresponding to the tree
ifstmt(if(C,if(C1,T,E)). Note that the above specification is capable of correctly resolving the
ambiguity for arbitrarily nested if-then-else statements.
In the above example, while it might appear that the preference clause is requiring the
sentence to be scanned twice in order to compute the two parses, this need not happen in an actual
implementation. The above specification actually does not commit to any specific parsing strategy.
By making use of memoization (or a related technique) [War92], we can avoid re-parsing the phrase
[if], cond(C), [then], stmtseq(T) when the second rule for ifstmt is being considered. For
example, a system such as XSB [SSW] would be a very good vehicle for implementing preference
logic grammars because of its memoization capability. However, we do not go into implementation
issues in this paper.
To illustrate the use of multiple preference clauses, consider the following ambiguous definite
clause grammar for arithmetic expressions:
exp(id) -? [id].
To resolve the ambiguity, preference clauses may be used to specify the precedence and associativity
of and * in a modular and declarative manner, i.e., without rewriting the original grammar. The
first two arbiter clauses below specify that * has a higher precedence than +. The third clause
specifies that + is left-associative whereas the fourth clause specifies that * is right-associative.
Readers familiar with Prolog DCGs may be concerned about the use of left-recursion in the above
grammar. Once again, memoization be used to circumvent the possible nontermination arising from
left-recursion.
3 Translation of Preference Logic Grammars
We present the translation of preference logic grammars into preference logic programs. We begin
with a brief introduction to preference logic programs.
3.1 Preference Logic Programs
A preference logic program (PLP) may be thought of as containing two parts: a first-order theory
and an arbiter. The first-order theory consists of clauses each of which can have one of two forms:
1. clauses. Each B i is of the form p( - t) where p is a
predicate and - t is a sequence of terms. In general, some of the B i s could be constraints as in
CLP [JL87, JM94].
2. clauses. are constraints 2
as in CLP [JL87, JM94] that must be satisfied for this clause to be applicable to a goal; they
must be read as antecedents of the implication. The variables that appear only on the RHS of
the ! clause are existentially quantified. The intended meaning of this clause is that the set
of solutions to the head is some subset of the set of solutions to the body.
Moreover, the predicate symbols can be partitioned into three disjoint sets depending on the kinds
of clauses used to define them:
1. C-predicates appear only in the heads of definite clauses and the bodies of these clauses contain
only other C-predicates (C stands for core).
2. O-predicates appear in the heads of only optimization clauses (O stands for optimization). For
each ground instance of an optimization clause, the instance of the O-predicate at the head is
a candidate for the optimal solution provided the corresponding instance of the body of the
clause is true. The constraints that appear before the j in the body of an optimization clause
are referred to as the guard and must be satisfied in order for the head H to be reduced.
3. D-predicates appear in the heads of only definite clauses and any one goal in the body of any of
these clauses is either an O-predicate or a D-predicate. (D stands for derived from O-predicates.)
The arbiter part of a preference logic program, which specifies the optimization criterion for the
O-predicates, has clauses of form:
where p is an O-predicate and each L i is an atom whose head is a C-predicate or a constraint as in
CLP. In essence this form of the arbiter states that p( - t) is less preferred than p(-u) if L
We have formalized the semantics of preference logic programs in our earlier work, and we
refer the reader to [GJM96, Gov97] for a detailed exposition. In short, preference logic programs
have a well-defined meaning as long as recursion through the optimization clauses is well-founded,
or locally-stratified. (This is similar in spirit to the semantics of negation-as-failure [Llo87].) We
have given a possible-worlds semantics for a preference logic program; essentially, each world is a
model for the constraints of the program, and an ordering over these worlds is enforced by the arbiter
clauses in the program. We introduce the concept of preferential consequence to refer to truth in the
optimal worlds (in contrast with logical consequence which refers to truth in all worlds). An optimal
2 We do not need the full generality of this feature for the translation of preference logic grammars.
answer to the query G is a substitution ' such that G' is a preferential consequence of the preference
logic program. It is not hard to see that such notions are also relevant to the semantics of preference
logic grammars.
We have also provided a derivation scheme called PTSLD-derivation, which stands for
Pruned Tree SLD-derivation, for efficiently computing the optimal answers to queries [GJM96,
Gov97]. The basic idea is to grow the SLD search tree for a query and apply the arbiter clauses
to prune unproductive search paths, i.e., suboptimal solutions. Since we are computing preferential
consequences as opposed to logical consequences, we do not incur the cost of theorem proving in
a general modal logic. In order to achieve the needed efficiencies and termination properties for
preference logic grammars, we must augment this derivation procedure with memo-tables.
We present two simple examples of preference logic programs, the first being a naive formulation
of the shortest-path problem, and the second is a dynamic-programming formulation of the same
problem. Consider the following CLP clauses for the predicate path(X,Y,C,P), which determines P
as a path (list of edges) with distance C from node X to Y in a directed
path(X,Y,C,[e(X,Y)]) :- edge(X,Y,C).
Unlike Prolog, in the above definition, the symbol does indeed stand for the addition operator. A
logical specification of the shortest path problem could be given as follows:
sh path(X,Y,C,P) ! path(X,Y,C,P).
sh path(X,Y,C1,P1) - sh path(X,Y,C2,P2) :- C2 ! C1.
The first clause is an example of an optimization clause, and it identifies sh path as an optimization
predicate. The space of feasible solutions for this predicate is some subset of the solutions for path;
hence the use of a ! clause. This clause effectively says that every shortest path is also a path. The
second clause is an example of an arbiter clause and it states the criterion for optimization: given
two solutions for sh path, the one with lesser distance is preferred. Computationally speaking, the
search tree for path is first constructed and those solution paths that are suboptimal according to
the arbiter clause are pruned; the remaining paths form the solutions for sh path.
The program below is a dynamic-programming formulation of the shortest-path problem.
sh dist(X,X,N,0).
sh
sh sh dist(X,Z,1,C1), sh dist(Z,Y,N,C2).
sh sh dist(X,Y,N,C2) :- C2 ! C1.
(We show only the specification of the shortest distance; the associated path can be specified with
the aid of an extra argument). This program explicitly expresses the optimal sub-problem property of
a dynamic-programming algorithm. The recursive clause for sh dist encodes the fact that candidate
shortest paths with n edges between any two vertices a, and b are obtained by extending the shortest
paths with edges. Note that the variable Z that appears only on the right-hand side of the
clause is existentially quantified. It therefore gets bound to some neighbor of the source vertex. In
fact, a candidate shortest path of n edges is generated by composing the shortest path from the
neighboring vertex to the destination with the edge between the source and the neighbor. Note
that this formulation does not state that the shortest path is obtained by only considering the edge
with the least cost emanating from the source to compute the shortest path. Furthermore, by using
memoization, we can avoid recomputing subproblems. In the previous formulation of this problem,
domain knowledge, such as the monotonicity of +, would be necesary to achieve a similar effect. This
example also shows the need for the guard: the conditions X !? Y and N ? 1, X !? Y should be
read as antecedents of the implication.
3.2 From PLGs to PLPs
The translation of a preferene logic grammar into a preference logic program proceeds as follows:
1. For each nonterminal N that has no preference clause attached to it, the grammar clauses for
are translated into definite clauses as in the case of definite-clause grammars.
2. For each nonterminal N that has a preference clause attached to it, we introduce a new non-terminal
pref N with the same number of arguments as N . There is one optimization clause
associated with pref N , which is defined as follows:
pref
3. For each (grammatical) arbiter clause for N of the form
the translated preference clause for pref N is:
pref N(-u; I; O) - pref N(-v; I; O) :- L
4. For each occurrence of the predicate N in the body of a PLG rule, in the translated program
we replace N by pref N .
Nonterminals that have preference rules attached to them give rise to O-predicates (and their associated
definitions) in the target PLP program; and, nonterminals that depend upon other nonterminals
that have one or more preference rules attached to them give rise to D-predicates in the target PLP
program.
We briefly describe how the if-then-else grammar is translated into a PLP.
stmtseq(S,I,O) :- stmt(S,I,O).
stmtseq(ss(S,Ss),I,O) :- stmt(S,I,[;-O1]), stmtseq(Ss,O1,O).
stmt(S,I,O) :- assign(S,I,O).
stmt(S,I,O) :- pref ifstmt(S,I,O).
assign(assign(V,E),I,O) :- var(V,I,[:=-O1]), expr(E,O1,O).
stmtseq(T,O1,O).
stmtseq(T,O1,[else-O2]),
stmtseq(E,O2,O).
pref
pref ifstmt(if(C,if(C1,T),E),In,Out) - pref ifstmt(if(C,if(C1,T,E)),In,Out).
Note the introduction of the new predicate pref ifstmt. Every occurrence of ifstmt on the right
hand side of a grammar rule is replaced by the corresponding instance of pref ifstmt.
4 Applications of Preference Logic Grammars
We now present two major paradigms of preference logic grammars: optimal parsing and natural
language parsing.
4.1 Optimal Parsing
Clause Translation Grammars. We first briefly describe definite clause translation
grammars [Abr84], and then present an example of optimal parsing from a document layout appli-
cation. Definite clause translation grammars (DCTGs) can be viewed as a logical counterpart of
attribute grammars [Knu68]. In attribute grammars, the syntax is specified by context-free rules
and semantics are specified by attributes attached to nonterminal nodes in the derivation trees and
by function definitions that define the attributes. Attribute grammars and DCTGs can be readily
translated into constraint logic programs over some appropriate domain [JL87, vH89, JM94]. In
general, we need constraint logic programs rather than ordinary definite-clause programs because we
are interested in interpreting the functions defining the attributes over an appropriate domain.
rules augment context-free rules in two ways: (i) they provides a mechanism for
associating with nonterminals logical variables which represent subtrees rooted at the nonterminal;
and (ii) they provide a mechanism for specifying the computation of semantic values of properties
of the trees. DCTGs differ from attribute grammars in that the semantics of DCTGs is captured
by associating a set of definite clauses to nonterminal nodes of a derivation tree, and no distinction
is made in DCTGs between inherited and synthesized attributes. The use of logical variables that
unify with parse trees eliminates the need for this distinction. In DCTGs, we associate a logical
variable N with a nonterminal nt by writing:
The logical variable N will be eventually instantiated to the subtree corresponding to the nonterminal
nt. To specify the computation of a semantic value X of a property p of the tree N, we write:
The following is a simple DCTG from [AD89] that specifies the syntax and semantics of bitstrings.
The semantics of a bitstring is its decimal equivalent. Note that syntactic rules are specified by ::=
productions while semantic rules are specified by ::- productions.
bit ::= "0"
bit ::= "1"
bitstring
length(0).
bitstring ::= bit-B, bitstring-B1
number ::= bitstring-B
There are two productions for the nonterminal bit and two for bitstring. The toplevel nonterminal
is number. The predicates specifying semantic properties are bitval, length, and value. The
translation of this DCTG into a logic program is straightforward and is also explained in [AD89].
Line-Breaking Problem. We show how the problem of laying out paragraphs optimally can be
specified in the formalism. Logically, a paragraph is a sequence of lines where each line is a sequence
of words. This view of a paragraph can be captured by the following
Knuth and Plass [KP81] describe how to lay out a sequence of words forming a paragraph by
computing the badness of the paragraph in terms of the badness of the lines that make up the
paragraph. The badness of a line is determined by the properties of the line such as the total width
of the characters that make up the line, the number of white spaces in the line, the stretchability and
shrinkability of the white spaces, the desired length of the line, etc. [KP81] insists that each line in
the paragraph be such that the ratio of the difference between actual length and the desired length
and the stretchability or shrinkability (the adjustment ratio) be bounded. This can be captured
by the following DCTG (we take the liberty to extend the syntax to include interpreted function
para ::= line-Line
para ::= line-Line, para-Para
line ::= "word"
difference(Dl-N) ::- desiredlength(Dl), naturallength(N).
adjustment(D/S) ::- difference(D), D ? 0, stretchability(S).
adjustment(D/S) ::- difference(D), D =! 0, shrinkability(S).
lineshrinkbound, A ? linestretchbound.
line ::= "word", line-Line
difference(Dl-N) ::- desiredlength(Dl), naturallength(N).
adjustment(D/S) ::- difference(D), D ? 0, stretchability(S).
adjustment(D/S) ::- difference(D), D =! 0, shrinkability(S).
lineshrinkbound, A ? linestretchbound.
The grammars specifying document structures, such as the one above, are extremely ambigu-
ous. Given a description of a document and a sequence of words representing its content, we are
interested in a parse that has a particular property. For instance, we may be interested in the parse
of a sequence of words from !para? that has the least badness. Brown et al [BMW92] augmented
attribute grammars with minimization directives that specified which attributes had to be minimized
in the preferred parse. Similarly, we extend DCTGs with statements that specify the preferred parse.
For instance, in the line-breaking example above, the preferred parse is specified by augmenting the
definition of para as follows:
In essence, PLGs allow one to specify optimal parsing problems in a succinct manner. Once again, we
note that the above specification does not commit to any particular parsing strategy for obtaining
the optimal parse. The naive method for computing the best parse involves enumerating all the
parses, and this approach can easily lead to an exponential complexity. Note that the line-breaking
algorithm used by T E X [KP81] constructs the optimal parse in polynomial time.
4.2 Natural Language Parsing
A practical use of preference logic grammars lies in ambiguity resolution in natural languages. This is
a substantial research area and we provide a brief glimpse of the issues through an example. Consider
the following simple ambiguous definite-clause grammar.
verbphrase(vp(V,N)) -? verb(V), nounphrase(N)
verbphrase(vp(V,N,P)) -? verb(V), nounphrase(N), prepphrase(P)
prepphrase(pp(P,N)) -? preposition(P), nounphrase(N)
where the details of determiner, noun, verb, and preposition are not shown. Given a sentence,
The boy saw the girl with binoculars,
there are two possible parses:
sent(np(the boy), vp(verb(saw), np(the girl), pp(with binoculars)))
sent(np(the boy), vp(verb(saw), np(np(the girl), pp(with binoculars))))
This is the well-known prepositional attachment problem. In this example, the preferred reading
of the sentence is given by the first parse, which conforms to the principle of minimal attachment
[Kim73], i.e., create the simplest syntactic analysis, where simplicity might be measured by the
number of nodes in the parse tree. On the other hand, minimal attachment does not yield the
preferred reading of the sentence
The boy saw the girl with long hair.
Instead, we prefer here to parse the sentence according to the principle of right association, i.e., a
new constituent is analyzed as being part of the phrase subtree under construction rather than a
part of a higher phrase subtree. Both principles can be expressed by preference clauses, as shown
below (nodes in(P) counts the number of nodes in parse tree P, while span(P) returns the length
of the sentence spanned by P):
While these two principles are purely syntactic in nature, in general the attachment problem
is more complex, requiring semantic and contextual knowledge for correct resolution. There has been
considerable recent interest in the computational linguistics community in the use of constraints and
preferences. For example, [Sch86] discusses preference tradeoffs in attachment decisions; [Per85]
shows how the principles of minimal attachment and right association can be realized by suitable
parsing actions in a bottom-up parser; [Usz91] presents controlled linguistic deduction as a means
for adding control knowledge to declarative grammars; and [Erb92] discusses the use of preference
values with typed feature structures and resolving ambiguity by choosing feature structures with the
highest preference value. We are at present developing an extension of preference logic grammars
to formulate a principled and practical scheme for using context-sensitive information for ambiguity
resolution in feature-based grammar formalisms.
5 Conclusions and Further Research
We have presented a logic-grammar extension called preference logic grammars, and shown their
use for ambiguity resolution in logic grammars and for specifying optimal parsing problems. The
use of preferential statements in logic grammars is concise, modular, and declarative. Although
this extension was originally motivated by the extension to attribute grammars to specify document
layout [BMW92], this paper shows that the ideas are applicable in a broader setting.
There are many interesting avenues for further research. The first is to develop an implementation
of PLGs incorporating memoization and pruning. For applications such as optimal parsing, it
is desirable to further annotate the grammar with information so that pruning of suboptimal parses
can be done at the earliest opportunity. For this purpose, domain knowledge, such as the additive
property of costs, is important. It may be noted that this kind of information is generally not of
interest in other applications of ambiguity resolution.
The paradigm of preference logic programming was originally proposed for specifying both
optimization and relaxation problems [GJM96, Gov97]. Relaxation is performed when the constraints
specifying the problem do not have any solutions or when the optimality requirements need to
weakened. In PLP [GJM96], we can encode constraint relaxation regimes such as those given in
[WB93] and also preference relaxation regimes. The latter is achieved through the notion of a
relaxable goal of the following form:
where p is an O-predicate and c is a C-predicate or a constraint as in CLP. The predicate p is said to
be a relaxable predicate and c is said to be the relaxation criterion of the relaxation goal. Essentially
if the optimal solutions to p( - t) satisfy c(-u), those are the intended solutions. However, if none of the
optimal solutions to p( - t) satisfies c(-u), then the feasible set of solutions of p is reduced by adding c
as an additional constraint and the arbiter is applied to this constrained set. In applications such
as document processing, this notion of relaxation seems particularly useful. For instance, a page
may consist of many paragraphs but the optimal layout of the page might require that some of the
paragraphs that make up the page are laid out sub-optimally. We are investigating the methods
by which such criteria could be incorporated into a logic grammar formalism. Another possible
application for relaxation is in specifying error-recovery strategies in compilers and code generation.
In the area of natural language processing, we are interested in exploring how preferences can
be used to resolve several semantic ambiguity issues, such as 'quantifier scoping'. For example, the
sentence Every man loves a woman has a quantifier scoping ambiguity, i.e., does every man love
the same woman or can the woman be different for different men? The latter reading is usually the
one intended, and this reflects our preference that the quantifier in the noun-phrase should scope
over the one in the verb-phrase.
Finally, we are also interested in incremental computation strategies for parsing with preference
logic grammars. For example, in code-generation, if a small change were made to the input
program, the compiler should not have to compute the optimal code sequence of the program from
scratch. In the document layout application, the formatter (T E X, L A T E X, etc.) should not have to
reformat the whole document after each change to obtain the new layout.



--R

Clause Translation Grammars.
Logic Grammars.
Code Generation using Tree Matching and Dynamic Programming.
The Declarative Semantics of Document Pro- cessing
Using Preference Values in Typed Feature Structures to Exploit Non-absolute Constraints for Disambiguation
Preference Logic Programming.
Optimization and Relaxation in Constraint Logic Languages.
Optimization and Relaxation in Logic Languages.
Constraint Logic Programming.
Constraint Logic Programming: A Survey.
Seven Principles of Surface Structure Parsing in Natural Language.
Semantics of Context-Free Languages
Breaking Paragraphs into Lines.
Foundations of Logic Programming.
A new Characterization of Attachment Preferences
Clause Grammars for Language Analysis - A Survey of the Formalism and a Comparison with Augmented Transition Networks
Are There Preference Trade-offs in Attachment Decisions? <Proceedings>In Proc
XSB: An Overview of its Use and Implementation.
Strategies for Adding Control Information to Declarative Grammars.
Constraint Satisfaction in Logic Programming.
Memoing for Logic Programs.
Hierarchical Constraint Logic Programming.
--TR
Foundations of logic programming
Every logic program has a natural stratification and an iterated least fixed point model
The well-founded semantics for general logic programs
Preferred answer sets for extended logic programs
Tabling for non-monotonic programming
Reasoning with Prioritized Defaults
Psychiatric Diagnosis from the Viewpoint of Computational Logic

--CTR
Hai-Feng Guo , Bharat Jayaraman, Mode-directed preferences for logic programs, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Hai-Feng Guo , Bharat Jayaraman , Gopal Gupta , Miao Liu, Optimization with mode-directed preferences, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.242-251, July 11-13, 2005, Lisbon, Portugal
Torsten Schaub , Kewen Wang, A semantic framework for preference handling in answer set programming, Theory and Practice of Logic Programming, v.3 n.4, p.569-607, July
Logic programming and knowledge representation-the A-prolog perspective, Artificial Intelligence, v.138 n.1-2, p.3-38, June 2002
non-monotonic reasoning;reasoning with preferences;logic programming;natural language processing;XSB