Reverse Folding

Predicates

• Input: fold/3, length/1, time/1

• Output: pivot/3

Problem Description

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).
fold(2,9,10).
fold(3,9,11).
fold(4,10,11).
fold(5,11,11).
fold(6,11,10).
fold(7,11,9).
fold(8,10,9).
fold(9,10,10).

length(9).
time(4).

This means that the the final form of the protein is

• _ _

• | |
  | |_|
  

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).
pivot(2,5,clock).
pivot(3,8,clock).
pivot(4,7,clock).

Effects of pivot moves

• |
  |
  |
  |
  |
  | _ _ _ _ _ _ _ _ _ _ _ _
  | | | | | | | |
  | | | | | | | |_|
  

  • | _|
    |
    

Ideas on modeling with variants of ASP can be found in:
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)

Example

Author(s)

• Author: Agostino Dovier
  • Affiliation: University of Udine, Italy
• Author: Andrea Formisano
  • Affiliation: University of Perugia, Italy
• Author: Enrico Pontelli
  • Affiliation: New Mexico State University, USA