= Reverse Folding =

<<TableOfContents>>

== Problem Description ==

* Input predicates: fold/3, length/1, time/1

* Output predicates: pivot/3

This is a simplification of an important Biological problem. A string (e.g., representing a protein) composed of N consecutive elements (defined by the predicate length(N)) at a fixed unitary distance lays on a 2D (cartesian) plane. Admissible angles are 0 (straight line), .90. (left turn) and +90. (right turn). Different elements must occupy different positions. We refer to each placement of the string as a folding. A folding is represented by a predicate fold(I,X,Y) where I in {1,...,N} is the Ith element of the string, and (X,Y) are its coordinates in the plane. You can assume X and Y in {0,...,2N}.

A pivot move is defined by selecting an element i in {2,...,N-1} and its effect is to turn clockwise or counter-clockwise of 90 degrees the part of the string related to the elements i+1,...,N.

A move at time t is represented by pivot(t,i,clock) or pivot(t,i,anticlock). Exactly one move occurs at a time t.

The goal is to find (if it exists) a sequence of T moves (T is defined by the predicate time(T)) such that lead the initial straight line fold 
fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).
into the fold assigned as input.

Assume the input is:

fold(1,9,9). <<BR>>
fold(2,9,10). <<BR>>
fold(3,9,11). <<BR>>
fold(4,10,11). <<BR>>
fold(5,11,11). <<BR>>
fold(6,11,10). <<BR>>
fold(7,11,9). <<BR>>
fold(8,10,9). <<BR>>
fold(9,10,10). <<BR>>

length(9). <<BR>>
time(4). <<BR>>


This means that the the final form of the protein is
   _ _
  |   | <<BR>>
  | |_| <<BR>>

Starting from the straight line fold, it is possible to reach
that folding with the application of the following pivot
moves (which is the expected output from the system):

pivot(1,3,clock). <<BR>>
pivot(2,5,clock). <<BR>>
pivot(3,8,clock). <<BR>>
pivot(4,7,clock). <<BR>>

Effects of pivot moves

 | <<BR>>
 | <<BR>>
 | <<BR>>
 | <<BR>>
 | <<BR>>
 |    _ _ _ _ _ _    _ _     _ _     _ _ <<BR>>
 |   |              |   |   |   |   |   | <<BR>>
 |   |              |   |   |   |   | |_| <<BR>>
                        |      _| <<BR>>
                        | <<BR>>

Ideas on modeling with variants of ASP can be found in: <<BR>>
A. Dovier, A. Formisano, E. Pontelli.
Perspectives on Logic-based Approaches for Reasoning About Actions and Change.
To appear in LNCS 6565, Essay in honour of Michael Gelfond
(paper draft available on line)