PENG Light
Processable ENGlish

1. Introduction

Specifications written in PENG Light can also be translated into answer set programs. Answer Set Programming has its roots in knowledge representation, logic programming, and constraint satisfaction. Below (2) is a simple puzzle in English that is first reconstructed in PENG Light (3) and then translated via discourse representation structures (4) into an answer set program (5). The answer set program is then processed by the clingo system (6) that finds the solutions to the puzzle. Alternatively, we can add specific questions directly to the puzzle and then process the entire text (7).

2. Original Puzzle

Dominique, Ignace, Naren, Olivier, Philippe, and Pascal have arrived as the first six at the Paris marathon.

Reconstruct their arrival order from the following information:

a) Olivier has not arrived last.

b) Dominique, Pascal and Ignace have arrived before Naren and Olivier.

c) Dominique who was third last year has improved this year.

d) Philippe is among the first four.

e) Ignace has arrived neither in second nor third position.

f) Pascal has beaten Naren by three positions.

g) Neither Ignace nor Dominique are on the fourth position.

3. Reconstruction of the Puzzle in PENG Light

To the best of my knowledge there exists no natural language processing tool that can take the original version of the marthon puzzle directly as input and find the solution(s) automatically. This is -- as you will see below -- because additional information is required that is not available in the text. I reconstruct this puzzle in controlled natural language in order to make it processable by a machine.
  1. Dominique, Ignace, Naren, Olivier, Pascal, and Philippe are runners.
  2. There exist exactly six positions.
  3. Every runner is allocated to exactly one position.
  4. Reject that a runner R1 is allocated to a position and that a runner R2 is allocated to the same position and that R1 is not equal to R2.
  5. Reject that Olivier is allocated to the sixth position.
  6. If a runner R1 is allocated to a position P1 and a runner R2 is allocated to a position P2 and P1 is smaller than P2 then R1 is before R2.
  7. Reject that Naren is before Dominique and reject that Naren is before Pascal and reject that Naren is before Ignace.
  8. Reject that Olivier is before Dominique and reject that Olivier is before Pascal and reject that Olivier is before Ignace.
  9. Reject that Dominique is allocated to a position that is greater than or equal to 3.
  10. Reject that Philippe is allocated to a position that is greater than 4.
  11. Reject that Ignace is allocated to the second position.
  12. Reject that Ignace is allocated to the third position.
  13. Reject that Pascal is allocated to a position P1 and that Naren is allocated to a position P2 and that P1 is not equal to P2 minus 3.
  14. Reject that Ignace is allocated to the fourth position.
  15. Reject that Dominique is allocated to the fourth position.

4. Automatic Translation into a Discourse Representation Structure

The reconstructed puzzle is translated automatically into a discourse representation structure (DRS). The DRS uses a flat notation for atoms and number of predefined predicates (and eventualities are reified, but this is not really important for our case). Note that the command reject that is translated into a CSTR operator in the DRS that will trigger a constraint in ASP. This is done because we want to distinguish between constraints (CSTR) and strong negation (NOT) in other constructions (that are not used here).

[A,B,C,D,E,F,G,H,I,J]
named(A,dominique)
named(B,ignace)
named(C,naren)
named(D,olivier)
named(E,pascal)
named(F,philippe)
object(G,runner)
predicate(H,isa, (A;B;C;D;E;F),G)
cardinal(I,eq,6)
object(I,position)
predicate(J,exist,I)

   [K]
   object(K,runner)
   ==>
      [L,M,N]
      cardinal(L,eq,1)
      object(L,position)
      predicate(M,be,K)
      property(M,allocated_to,L)

   CSTR
      [O,P,Q,R,S,T,U,V]
      object(O,runner)
      variable(O,r1)
      object(P,position)
      predicate(Q,be,O)
      property(Q,allocated_to,P)
      object(S,runner)
      variable(S,r2)
      predicate(T,be,S)
      property(T,allocated_to,P)
      predicate(V,be,O)
      operator(V,\=,S)

   CSTR
      [W,X,Y]
      ordinal(W,6)
      object(W,position)
      predicate(X,be,D)
      property(X,allocated_to,W)

   [Z,A1,B1,C1,D1,E1,F1,G1,H1]
   object(Z,runner)
   variable(Z,r1)
   object(A1,position)
   variable(A1,p1)
   predicate(B1,be,Z)
   property(B1,allocated_to,A1)
   object(D1,runner)
   variable(D1,r2)
   object(E1,position)
   variable(E1,p2)
   predicate(F1,be,D1)
   property(F1,allocated_to,E1)
   predicate(H1,be,A1)
   operator(H1,<,E1)
   ==>
      [I1]
      predicate(I1,be,Z)
      property(I1,before,D1)

   CSTR
      [J1]
      predicate(J1,be,C)
      property(J1,before,A)

   CSTR
      [K1]
      predicate(K1,be,C)
      property(K1,before,E)

   CSTR
      [L1]
      predicate(L1,be,C)
      property(L1,before,B)

   CSTR
      [M1]
      predicate(M1,be,D)
      property(M1,before,A)

   CSTR
      [N1]
      predicate(N1,be,D)
      property(N1,before,E)

   CSTR
      [O1]
      predicate(O1,be,D)
      property(O1,before,B)

   CSTR
      [P1,Q1,R1,S1]
      object(P1,position)
      cardinal(T1,3)
      predicate(Q1,be,P1)
      operator(Q1,>=,T1)
      predicate(R1,be,A)
      property(R1,allocated_to,P1)

   CSTR
      [U1,V1,W1,X1]
      object(U1,position)
      cardinal(Y1,4)
      predicate(V1,be,U1)
      operator(V1,>,Y1)
      predicate(W1,be,F)
      property(W1,allocated_to,U1)

   CSTR
      [Z1,A2,B2]
      ordinal(Z1,2)
      object(Z1,position)
      predicate(A2,be,B)
      property(A2,allocated_to,Z1)

   CSTR
      [C2,D2,E2]
      ordinal(C2,3)
      object(C2,position)
      predicate(D2,be,B)
      property(D2,allocated_to,C2)

   CSTR
      [F2,G2,H2,I2,J2,K2,L2]
      object(F2,position)
      variable(F2,p1)
      predicate(G2,be,E)
      property(G2,allocated_to,F2)
      object(I2,position)
      variable(I2,p2)
      predicate(J2,be,C)
      property(J2,allocated_to,I2)
      cardinal(M2,3)
      operator(I2,-,M2)
      predicate(L2,be,F2)
      operator(L2,\=,I2)

   CSTR
      [N2,O2,P2]
      ordinal(N2,4)
      object(N2,position)
      predicate(O2,be,B)
      property(O2,allocated_to,N2)

   CSTR
      [Q2,R2,S2]
      ordinal(Q2,4)
      object(Q2,position)
      predicate(R2,be,A)
      property(R2,allocated_to,Q2)

5. Automatic Translation into an Answer Set Program

The discourse representation structure is further translated into an answer set program:
runner((dominique;ignace;naren;olivier;pascal;philippe)).

position(1..6).

1 { allocated_to(A,B) : position(B) } 1 :- runner(A).

:- runner(C), position(D), allocated_to(C,D), runner(E), allocated_to(E,D), C!=E.

:- allocated_to(olivier,6).

before(F,G) :- runner(F), position(H), allocated_to(F,H), runner(G), position(I), allocated_to(G,I), H<I.

:- before(naren,dominique).  

:- before(naren,pascal).

:- before(naren,ignace).

:- before(olivier,dominique).

:- before(olivier,pascal).

:- before(olivier,ignace).

:- position(J), J>=3, allocated_to(dominique,J).

:- position(K), K>4, allocated_to(philippe,K).

:- allocated_to(ignace,2).

:- allocated_to(ignace,3).

:- position(L), allocated_to(pascal,L), position(M), allocated_to(naren,M), L!=M-3.

:- allocated_to(ignace,4).

:- allocated_to(dominique,4).

6. Processing of the Answer Set Program by Clingo

Finally, we can use the answer set system clingo to process the logic program and get the following solutions:

Call ASP solver clingo ... 

Answer: 1
allocated_to(philippe,4) 
allocated_to(pascal,3) 
allocated_to(olivier,5) 
allocated_to(naren,6) 
allocated_to(ignace,1) 
allocated_to(dominique,2) 
SATISFIABLE

Models      : 1     
Time        : 0.016
  Prepare   : 0.016
  Prepro.   : 0.000
  Solving   : 0.000

7. Question Answering

Alternatively, we can add the relevant question directly to the reconstructed puzzle:

17. Which runner is allocated to what position?

This question results in the following sub-DRS:
   [D3,E3,F3,G3]
   object(D3,runner)
   object(E3,position)
   predicate(F3,be,D3)
   property(F3,allocated_to,E3)
   ==>
      []
      answer(D3,E3)
that is translated into the subsequent answer set rule and added to the answer set program:
answer(N,O) :- runner(N), position(O), allocated_to(N,O).

#hide.
#show answer(A, B).
If we run clingo again with the above setting, we will get the following results:
Call ASP solver clingo ... 

Answer: 1
answer(4,philippe) 
answer(3,pascal) 
answer(5,olivier) 
answer(6,naren) 
answer(1,ignace) 
answer(2,dominique) 
SATISFIABLE

Models      : 1     
Time        : 0.016
  Prepare   : 0.016
  Prepro.   : 0.000
  Solving   : 0.000

That means questions answering can be implemented in a straightforward way in Answer Set Programming.

Here is another example; the question:

18. Which runner is allocated to a position that is greater than 4?

is translated into the following sub-DRS:
   [E3,F3,G3,H3,I3]
   object(E3,runner)
   object(F3,position)
   cardinal(J3,4)
   predicate(G3,be,F3)
   property(G3,>,J3)
   predicate(H3,be,E3)
   property(H3,allocated_to,F3)
   ==>
      []
      answer(E3)

and then into this answer set rule:

answer(T) :- runner(T), position(U), U>4, allocated_to(T,U).

#hide.
#show answer(A).

The answer set solver clingo finds the following two solutions to question 18:

Call ASP solver clingo ... 

Answer: 1
answer(olivier) 
answer(naren) 
SATISFIABLE

Models      : 1     
Time        : 0.016
  Prepare   : 0.016
  Prepro.   : 0.000
  Solving   : 0.000

© Rolf Schwitter, Macquarie University, Australia
Last modified: 13th January 2013 (updated version of the puzzle)