|
Size: 2558
Comment:
|
Size: 3018
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| * Input predicates: fold/3, length/1, time/1 * Output predicates: pivot/3 |
|
| Line 13: | Line 9: |
| 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. |
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. |
| Line 18: | Line 12: |
| fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1). | {{{fold(1,N,N). fold(2,N,N+1). fold(2,N,N+2). ... fold(N,N,2N-1).}}} |
| Line 21: | Line 17: |
| == Predicates == * '''Input''': {{{fold/3, length/1, time/1}}} * '''Output''': {{{pivot/3}}} == Input format == == Output format == == Example(s) == |
|
| Line 22: | Line 30: |
| {{{ 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). |
|
| Line 23: | Line 41: |
| 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>> |
length(9). time(4). }}} |
| Line 38: | Line 45: |
| {{{ | |
| Line 39: | Line 47: |
| | | <<BR>> | |_| <<BR>> |
| | | |_| }}} |
| Line 45: | Line 54: |
| {{{ 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: <<BR>> A. Dovier, A. Formisano, E. Pontelli. <<BR>> Perspectives on Logic-based Approaches for Reasoning About Actions and Change. <<BR>> To appear in LNCS 6565, Essay in honour of Michael Gelfond <<BR>> (paper draft available on line) |
|
| Line 46: | Line 79: |
| pivot(1,3,clock). <<BR>> pivot(2,5,clock). <<BR>> pivot(3,8,clock). <<BR>> pivot(4,7,clock). <<BR>> |
|
| Line 51: | Line 80: |
| Effects of pivot moves | |
| Line 53: | Line 81: |
| | <<BR>> | <<BR>> | <<BR>> | <<BR>> | <<BR>> | _ _ _ _ _ _ _ _ _ _ _ _ <<BR>> | | | | | | | | <<BR>> | | | | | | | |_| <<BR>> | _| <<BR>> | <<BR>> |
== Notes and Updates == |
| Line 64: | Line 83: |
| 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) |
Different elements must occupy different positions only at discrete time points. The case in which elements overlap during rotation from one time point to another is not to be considered. == 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 |
Reverse Folding
Contents
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.
Predicates
Input: fold/3, length/1, time/1
Output: pivot/3
Input format
Output format
Example(s)
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)
Notes and Updates
Different elements must occupy different positions only at discrete time points. The case in which elements overlap during rotation from one time point to another is not to be considered.
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