We build upon recent work by Baral, Dzifcak and Son that de¯ne the translation into ASP of (some classes of) natural language sentences from the lambda-calculus intermediate format generated by CCG grammars. We introduce automatic generation of lambda-calculus expressions from template ones, thus improving the e®ectiveness and generality of the translation process.
Many intelligent systems have to deal with knowledge expressed in natural
language, either extracted from books, web pages and documents in general, or
expressed by human users. Knowledge acquisition from these sources is a
challenging matter, and many attempts are presently under way towards automatically
translating natural language sentences into an appropriate knowledge
representation formalism [
The so-called Web 3.0 [
Translating natural language sentences into a logic knowledge representation
is a key point on the applications side as well. In fact, designing applications
such as semantic search engines implies obtaining a machine-processable form
of the extracted knowledge that makes it possible to perform reasoning on the
data so as to suitably answer (possibly in natural language) to the user's queries,
as such an engine should interact with the user like a personal agent. We have
practically demonstrated in [
A central aspect of knowledge acquisition is related to the automation of
the process. Recent work in this direction has been presented in [
Before entering into the details of our proposal, we need to introduce the
necessary building blocks of the work of [
Lambda Calculus ¸-calculus is a formal system designed to investigate function de¯nition, function application and recursion. Any computable function can be expressed and evaluated via this formalism.
The central concept in ¸-calculus is the \expression", de¯ned recursively as follows (where a \variable", is an identi¯er which can be any of the letters a, b, c, . . . ):
M ::=< name > j < f unction > j < application > < f unction >::= ¸ < name > :M < application >::= M M
Parentheses can be used for clarity. Lambda-calculus has only two keywords: ¸ and the dot. A single identi¯er is a valid ¸-expression, like, e.g., ¸x:x that de¯nes the identity function. The name after the ¸ is the identi¯er of the argument of this function. The expression after the point is called the body of the de¯nition. Functions can be applied to expressions, like, e.g., (¸x:x)y is the identity function applied to y. Parentheses are used to avoid ambiguity. Function applications are evaluated by substituting the value of the argument x (in this case 'y') in the body of the function de¯nition. The names of the arguments in function de¯nitions do not carry any meaning by themselves, they are just place holders. In ¸-calculus all names are local to de¯nitions. In the function ¸x:x, x is bound since its occurrence in the body of the de¯nition is preceded by ¸x. A name not preceded by a ¸ is called a free variable. The same identi¯er can occur free and bound in the same expression.
Substitution corresponds to the operation that will replace in a term all the free occurrences of x with y, like [y=x]M .
An ®-conversion allows bounded variables to change their name, like ¸x:M = ¸y:[y=x]M where [y=x]M is the result of substituting y for free occurrences of x in M and y cannot already appear in M .
Reduction (also called ¯-reduction) is the only rule of computation. It
concerns the replacement of a formal parameter by an actual one. It can only occur
if a functional term has been applied to some other term. The ¯-reduction of
((¸x:M )N ) is [N=x]M where [N=x]M denotes the substitution of the formal
parameter x with the argument N throughout the expression M . ¯-reduction will
be denoted by the connective @. Reduction is nothing other than the textual
replacement of a formal parameter in the body of a function by the actual
parameter supplied, for example ¸x:f lies(x) @ tweety results in f lies(tweety). We can
have ¸ expressions with various arguments, e.g., ¸x¸y:M . In this case, we assume
¯-reduction to be possible on one variable at a time, and to be performed on the
leftmost free variable. E.g., ¸x¸y:likes(x; y) @ mary results in ¸y:likes(mary; y)
and ¸x:likes(mary; x) @ john results in likes(mary; john). We use parentheses
to indicate successive ¯-reductions, like in
((¸x¸y:likes(x; y) @ mary) @ john) that gives the same result as before.
ASP Answer Set Programming (ASP) is a form of logic programming based on
the answer set semantics [
In this logical framework, a problem can be encoded |by using a functionfree logic language| as a set of properties and constraints which describe the (candidate) solutions. More speci¯cally, an ASP-program is a collection of rules of the form
H Ã L1; : : : ; Lm; not Lm+1; : : : ; not Lm+n where H is an atom m ¸ 0, n ¸ 0 and each Li is an atom. The symbol not stands for negation-as-failure. Various extensions to the basic paradigm exist, that we do not consider here since they are not essential in the present context. The left-hand side and the right-hand side of the clause are called head and body, respectively. A rule with empty head is a constraint. (The literals in the body of a constraint cannot be all true, otherwise they would imply falsity.)
The semantics of ASP is expressed in terms of answer sets (or equivalently
stable models, [
Once a problem is described as an ASP-program P , its solutions (if any) are
represented by the answer sets of P . Unlike other semantics, a logic program
may have several or no answer sets, because conclusions are included in an
answer set only if they can be justi¯ed. The following program has no answer
sets: fa à not b; b à not c; c à not ag. The reason is that in every minimal
model of this program there is a true atom that depends (in the program) on the
negation of another true atom. Whenever a program has no answer sets, we will
say that the program is inconsistent. Correspondingly, checking for consistency
means checking for the existence of answer sets. For a survey of this and other
semantics of logic programs with negation, the reader may refer to [
Let us consider the program P consisting of the three rules fr à p, p à not q, q à not pg. Such a program has two answer sets: fp; rg and fqg. If we add the rule (actually, a constraint) à q to P , then we rule-out the second of these answer sets, because it violates the new constraint.
To ¯nd the solutions of an ASP-program, an ASP-solver is used. We used
Clasp solver [
CCG Combinatorial Categorial Grammars (CCGs) [
Categories identify constituents as either primitive categories or functions. Primitive categories, such as N (noun), NP (noun phrase), S (sentence), and so on, may be regarded as further distinguished by features, such as number, case, in°ection, and the like. Functions (such as verbs) bear categories identifying the type of their result (such as VP, verb phrase) and that of their argument(s)/complements(s) (both may themselves be either functions or primitive categories). Function categories also de¯ne the order(s) in which the arguments must combine, and whether they must occur to the right or the left of the functor. Each syntactic category is associated with a logical form whose semantic type is entirely determined by the syntactic category. The slash '/' and 'n' operators allow a category to combine by any combinatory rule.
In summary, a CCG grammar is composed of: a set of basic categories; a set of derived categories, constructed from the basic categories; and some syntactical rules describing via the slash operators the concatenation and determining the category of the result of the concatenation. For instance, assume that a CCG contains the following objects: Tweety whose category is NP (noun phrase) and °ies whose category is (SnNP). The category of °ies being SnNP means that if an NP (a noun phrase) is concatenated to the left of °ies then we obtain a string of category S, i.e., a sentence. In other words, the category SnNP of °ies indicates that it is a verb, and that whenever it occurs in a natural language sentence its argument (namely the subject of the verb) is to be found at its left. As another example, sentence mary likes joe is of category (SnNP)/NP meaning that this time there are two arguments, one on the right and the other one on the left of the verb.
Categorial grammars have been widely used in linguistic research concerning semantics of natural language. In fact, lexical items are associated with semantic functions which correspond to the syntactic functions implicit in their categories. For instance, a phrase of category S/NP can be represented, from a semantic point of view, by a function from NP-type items to S-type items. By adopting ¸-calculus, the sentence will be associated with a lambda expression of the form ¸x:Á, e.g., ¸x:f lies(x). Similarly, for the category (SnNP)/NP we get ¸x:¸Á, e.g., ¸x¸y:likes(x; y). 2.2
The problem CCG do not cope with is that of approximate linguistic
expressions that involve \fuzzy" assertions like, e.g., `normally', `most', etc. that do
not have a direct correspondence in existentially / universally quanti¯ed
sentences. Thus, an intermediate form is needed that is able to take this kind of
sentences into account. This intermediate form should be such as to allow a
translation/transposition into some executable formalism that allows the extracted
knowledge to be reasoned about. Recent relevant work presented in [
The sample language discussed as a running example in [
{ Tim is a bird.
The ¯rst sentence is a normative sentence expressing a default: namely, it states that birds normally °y. The second sentence represents a subclass relationship, while third and fourth sentences represent di®erent properties of the class of penguins. The last two sentences are statements about individuals.
It is important to notice that none of previous approaches to automatic translation of natural language sentences is able to deal with default statements. The authors show how it is possible to automatically translate these sentences into ASP rules.
As ¯rst step, a CCG grammar for this sentences set is de¯ned, Lbird. The CCG grammar is used because it gives information to \drive" the application of ¸-expressions. However, as the goal is to obtain an ASP representation, the notion of ¸-representation is expanded to ¸-ASP-expression which allows for construction of ASP rules. Then, the second step is the development of ¸-ASPexpressions for words and categories in the language of interest. For example, for the Lbird grammar, the ¸-ASP-expressions are (where variables denoting domain constants are indicated, as customary in ASP, in uppercase):
°y most birds
Notice that the formula for `most' is a schema to be instantiated to speci¯c cases, while the other expressions are directly related to the example at hand.
Given this theoretical tool an example of translation is the following. Given the sentence \Most birds °y", the CCG derivation tells how this sentence is constructed (where S=Sentence, NP=Noun phrase):
The word `birds' is concatenated to the right of `most', creating `most birds'. This will be concatenated to the left of `°y', creating a sentence whose category is S.
The ¸-ASP-expressions for the categories of interest are:
The concatenation is driven by the CCG derivation, so the ¯rst step implies to concatenate `birds' to `most' and thus applying M to B2:
The ¸-ASP-expression for `Most birds °y' is obtained by applying the above expression to F1, i.e.: f ly(X) Ã bird(X); not :f ly(X): 3
In this section, we propose an improved fully automated methodology for generating ASP rules from natural language sentences of the kind discussed above, i.e., involving determiners and thus uncertain knowledge. We remind the reader that the objective of producing an ASP representation of natural language sentences is that of adding the resulting ASP code to a knowledge base and then being able to reason and draw consequences from the knowledge extracted form the sentence. This on the one hand allows a system to enlarge its knowledge and on the other hand may improve the system capabilities: for instance, the system can provide the user with \intelligent" answers to her/his questions. Our proposal copes with the following aspects.
{ Meta-¸-ASP-expressions
In our proposal, we go farther in the direction of replacing domain-dependent
¸-expressions with templates. We associate to grammar categories
expressions which are `meta' in the sense that they are associated to sets of
sentences rather than, like in the work of [
In our methodology, we associate grammar rules to meta-¸-ASP-expressions. These expressions are `meta' in the sense that they are associated to categories rather than to speci¯c instances. This alleviates the problem of the construction of ¸-expressions, and is a ¯rst step towards their automatic generation. We de¯ne ¸-ASP-expressionsT (template ¸-ASP-expressions) as a meta extension of ¸-ASP-expressions. These expressions may contain lexical placeholders of the form < nt >, where < nt > is a non-terminal of the given grammar, in place of function symbols. In the context of the meta-expressions, they play the role of meta-variables that are intended to be instantiated to functional representatives of these syntactic categories. I.e., basic template ¸-ASP-expressions are of the form ¸x: < nt > (x) where < nt > can be instantiated for instance to °ies. The instantiation of a ¸-ASP-expressionT expression produces a ¸-ASP-expression.
We also extend the templates of ASP rules to include meta-axioms to be evaluated in the background knowledge base in order to better represent plausible knowledge. We give below the example of determiners `most', `some' and `many'.
Notice that we modify the de¯nition of `most' provided in [
We de¯ne ¯ as the ¸ ¡ ASP ¡ expressionT Base, i.e., the set of meta ¸expression upon which the translation into ASP of given sentences is based. For the running example, the ¸-ASP-expressionT Base is: most some many noun verb det det det We have to suitably de¯ne the instantiation and application operations. The instantiation, denoted with the symbol @@, is the operation that will replace the lexical placeholder in a ¸-ASP-expressionT with the given parameter. The syntax of instantiation is the following:
¸x: < noun > (x) The result of instantiation is a ¸-ASP-expression. For example, given the ¸-ASPexpressionT : The instantiation of noun with 'home', is performed as follows: and the resulting ¸-ASP-expression is:
¸x:home(x) For the instantiation operation we adopt the same convention as for ¯-reduction, i.e., an instantiation refers to the leftmost metavariable, and parentheses have to be used in case of successive instantiations.
An application operation is the transposition of the ¸-calculus application to the ¸-ASP-expression realm.
The translation of a given sentence into a corresponding ¸-ASP-expression starts from the leaves of the parse tree and go backwards to the root symbol. The bottom-up visit of the parse tree drives the translation execution. For each terminal symbol an instantiation operation is performed, while each non-terminal implies an application operation to be performed. 3.2
We illustrate the proposed methodology again with the help of the sentence Most birds °y . For the sake of simplicity, instead of the CCG parse tree we adopt in the example a more \traditional" parse tree, that looks as follows:
Starting a left-to-right bottom-up visit of the parse tree, we retrieve in the ¸-ASP-Template Expression Base the class det (semantic match) and the exact lexical match for the most lexicon. Since most is a terminal symbol, according to previous de¯nitions we have to perform an instantiation operation. The ¸-ASP-Template-expression for most is: By the instantiation we obtain the ¸ ¡ ASP ¡ expression: In this case, the instantiation operation returns the same ¸-ASP-expression, because no placeholders needs to be instantiated. This happens when both semantic and syntactic match occurs. This is seldom the case in complex sentences, where instantiation will in general perform constrains checks and syntactic manipulation.
The next leave of the parse tree is the lexicon birds. It has the semantic role of \noun" in the context of the sentence. We ¯nd in the template base a match for all lexicons of the semantic class noun. As the birds lexicon is a terminal symbol, according to previous de¯nitions we perform an instantiation. The appropriate ¸-ASP-Template-expression is ¸x: < noun > (x),
The instantiation operation is performed with birds as parameter, obtaining: ¸x:bird(x) Thus, the resulting ¸ ¡ ASP ¡ expression is: Going up the parse tree, we ¯nd non-terminal np. According to previous de¯nitions, an application operation needs to be performed. In this case, semantic information drive the application of the ¸-ASP-expression and thus we get which produces: Now, we encounter the °y lexicon (verb), thus we look for a match concerning the verb semantic class, applicable to all lexicons of this class. We use this ¸ ¡ ASP ¡ expressionT to instantiate the °y lexicon and we get
¸y:f ly(y).
For the vp class, the application is an identity, so we can skip to root symbol s, and thus perform the ¯nal application: from which we get the ¯nal ASP expression:
f ly(X) Ã bird(X); not :f ly(X); abnormal(:f ly(X); bird(X)) Below we illustrate the automatic translation process of another sentence, namely Some robots walk . This sentence make use of some determiner. The parse tree is trivial. We As ¯rst step we retrieve from the ¸-ASP-Template Expression Base the expression that matches the class det (semantic match) and the some lexicon. some is a terminal symbol and thus we perform an instantiation operation. The ¸-ASP-Template-expression for some is:
we obtain the ¸ ¡ ASP ¡ expression: The robots lexicon is the next leaf of the parse tree that we have to process. We ¯nd in the template base a match for all lexicons of the semantic class noun to which this lexicon belongs. According to de¯nition we perform an instantiation from ¸-ASP-Template-expression: ¸x: < noun > (x), obtaining: Thus, the resulting ¸ ¡ ASP ¡ expression is: ¸x:robot(x) Traversing the parse tree, we ¯nd the non-terminal symbol np. In this case, according to the semantic information the application of the ¸-ASP-expression produces: When encountering the walk lexicon (verb), we ¯nd the match with the verb semantic class that is applicable to all lexicons of this class. We use this ¸ ¡ ASP ¡ expressionT to instantiate the walk lexicon
For the vp class, the application is an identity, so we can skip to root symbol s, and thus perform the ¯nal application: which produces Finally, we get the ¯nal ASP expression:
walk(X) Ã robot(X); not :walk(X); abnormal(walk(X); robot(X))
We now illustrate how it is possible to translate sentences including conjunctions
(like and ). This is an important step that allows us to capture more complex
sentences. The hardest problem in dealing with these constructs lies in the
requirement to properly specify the correct category representing each word. [
The ¸-ASP-expressionT Base is extended to include more elements: Lexicon SemClass ¸ ¡ ASP ¡ expression T emplate are and most some many noun verb verb conj det det det As a ¯rst step, we retrieve the ¸ ¡ ASP ¡ ExpressionT from the ¸ ¡ ASP ¡ ExpressionT emplateBase for the semantic class noun, and Parrots lexicon. According to our de¯nition, we have to perform an instantiation, The ¸-ASPTemplate-expression for noun semantic class is ¸x: < noun > (x). We use this ¸ ¡ ASP ¡ expressionT to instantiate the Parrots lexicon and we get
¸x:parrot(x). and we get
¸x:penguin(x) Then we move to the Penguins lexicon. This lexicon was recognized as belonging to the noun semantic class by semantic analysis, so, similarly to previous step and according to the ¸ ¡ ASP ¡ expressionT instantiation, we obtain We retrieve from the ¸ ¡ ASP ¡ expressionT that the expression for the and conjunction is:
¸u¸v:u ^ ¸u¸v:v shortened as ¸u¸v:ujv
Note that due the di®erent nature of translation process achieved through the
parse tree returned by our enhanced methodology, the ¸ ¡ ASP ¡ expression
for the and conjunction is di®erent from previous ones de¯ned in literature [
From ¸u¸v:ujv, the two arguments are We obtain: and then that reduces to: ¸x:parrot(x) and ¸x:penguin(x). (¸v:(¸x:parrot(x))jv) Then: That simpli¯es to:
¸x:bird(x) Finally, we have to perform some ¸ ¡ calculus operations to obtain the ¯nal expression: (¸v:v@X Ã parrot(X)jpenguin(X)) (¸x:bird(x)@X Ã parrot(X)jpenguin(X)) bird(X) Ã parrot(X)jpenguin(X) To have an expression that is consistent with ASP de¯nition we can divide the expression above into the two following rules:
bird(X) Ã parrot(X) and
bird(X) Ã penguin(X) 4
In this paper, we have introduced an advancement over [
A main future direction is that of improving the present representation on the one hand by introducing more abstract templates and meta-axioms able to cope with functions with an arbitrary number of arguments and on the other hand by expressing more forms of plausible/uncertain knowledge, and dealing with the translation of complex sentences including other kinds of conjunctions and, in perspective, pronouns and adverbs.