WORST_CASE(?,O(1))
* Step 1: LocalSizeboundsProc WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (?,1)
3. evaleasy1bb3in(A,B) -> evaleasy1returnin(A,B) [A >= 40] (?,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
9. evaleasy1returnin(A,B) -> evaleasy1stop(A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2,3},2->{4,5,6},3->{9},4->{7},5->{8},6->{8},7->{2,3},8->{2,3},9->{}]
+ Applied Processor:
LocalSizeboundsProc
+ Details:
LocalSizebounds generated; rvgraph
(<0,0,A>, A, .= 0) (<0,0,B>, B, .= 0)
(<1,0,A>, 0, .= 0) (<1,0,B>, B, .= 0)
(<2,0,A>, A, .= 0) (<2,0,B>, B, .= 0)
(<3,0,A>, A, .= 0) (<3,0,B>, B, .= 0)
(<4,0,A>, A, .= 0) (<4,0,B>, B, .= 0)
(<5,0,A>, A, .= 0) (<5,0,B>, B, .= 0)
(<6,0,A>, A, .= 0) (<6,0,B>, B, .= 0)
(<7,0,A>, 1 + A, .+ 1) (<7,0,B>, B, .= 0)
(<8,0,A>, 2 + A, .+ 2) (<8,0,B>, B, .= 0)
(<9,0,A>, A, .= 0) (<9,0,B>, B, .= 0)
* Step 2: SizeboundsProc WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (?,1)
3. evaleasy1bb3in(A,B) -> evaleasy1returnin(A,B) [A >= 40] (?,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
9. evaleasy1returnin(A,B) -> evaleasy1stop(A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2,3},2->{4,5,6},3->{9},4->{7},5->{8},6->{8},7->{2,3},8->{2,3},9->{}]
Sizebounds:
(<0,0,A>, ?) (<0,0,B>, ?)
(<1,0,A>, ?) (<1,0,B>, ?)
(<2,0,A>, ?) (<2,0,B>, ?)
(<3,0,A>, ?) (<3,0,B>, ?)
(<4,0,A>, ?) (<4,0,B>, ?)
(<5,0,A>, ?) (<5,0,B>, ?)
(<6,0,A>, ?) (<6,0,B>, ?)
(<7,0,A>, ?) (<7,0,B>, ?)
(<8,0,A>, ?) (<8,0,B>, ?)
(<9,0,A>, ?) (<9,0,B>, ?)
+ Applied Processor:
SizeboundsProc
+ Details:
Sizebounds computed:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<3,0,A>, 39) (<3,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
(<9,0,A>, 39) (<9,0,B>, B)
* Step 3: UnsatPaths WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (?,1)
3. evaleasy1bb3in(A,B) -> evaleasy1returnin(A,B) [A >= 40] (?,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
9. evaleasy1returnin(A,B) -> evaleasy1stop(A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2,3},2->{4,5,6},3->{9},4->{7},5->{8},6->{8},7->{2,3},8->{2,3},9->{}]
Sizebounds:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<3,0,A>, 39) (<3,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
(<9,0,A>, 39) (<9,0,B>, B)
+ Applied Processor:
UnsatPaths
+ Details:
We remove following edges from the transition graph: [(1,3)]
* Step 4: LeafRules WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (?,1)
3. evaleasy1bb3in(A,B) -> evaleasy1returnin(A,B) [A >= 40] (?,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
9. evaleasy1returnin(A,B) -> evaleasy1stop(A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2},2->{4,5,6},3->{9},4->{7},5->{8},6->{8},7->{2,3},8->{2,3},9->{}]
Sizebounds:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<3,0,A>, 39) (<3,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
(<9,0,A>, 39) (<9,0,B>, B)
+ Applied Processor:
LeafRules
+ Details:
The following transitions are estimated by its predecessors and are removed [3,9]
* Step 5: PolyRank WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (?,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2},2->{4,5,6},4->{7},5->{8},6->{8},7->{2},8->{2}]
Sizebounds:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
+ Applied Processor:
PolyRank {useFarkas = True, withSizebounds = [], shape = Linear}
+ Details:
We apply a polynomial interpretation of shape linear:
p(evaleasy1bb1in) = 39 + -1*x1
p(evaleasy1bb2in) = 38 + -1*x1
p(evaleasy1bb3in) = 40 + -1*x1
p(evaleasy1bbin) = 39 + -1*x1
p(evaleasy1entryin) = 40
p(evaleasy1start) = 40
The following rules are strictly oriented:
[39 >= A] ==>
evaleasy1bb3in(A,B) = 40 + -1*A
> 39 + -1*A
= evaleasy1bbin(A,B)
The following rules are weakly oriented:
True ==>
evaleasy1start(A,B) = 40
>= 40
= evaleasy1entryin(A,B)
True ==>
evaleasy1entryin(A,B) = 40
>= 40
= evaleasy1bb3in(0,B)
[B = 0] ==>
evaleasy1bbin(A,B) = 39 + -1*A
>= 39 + -1*A
= evaleasy1bb1in(A,B)
[0 >= 1 + B] ==>
evaleasy1bbin(A,B) = 39 + -1*A
>= 38 + -1*A
= evaleasy1bb2in(A,B)
[B >= 1] ==>
evaleasy1bbin(A,B) = 39 + -1*A
>= 38 + -1*A
= evaleasy1bb2in(A,B)
True ==>
evaleasy1bb1in(A,B) = 39 + -1*A
>= 39 + -1*A
= evaleasy1bb3in(1 + A,B)
True ==>
evaleasy1bb2in(A,B) = 38 + -1*A
>= 38 + -1*A
= evaleasy1bb3in(2 + A,B)
* Step 6: KnowledgePropagation WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (?,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (40,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (?,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (?,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (?,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (?,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (?,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2},2->{4,5,6},4->{7},5->{8},6->{8},7->{2},8->{2}]
Sizebounds:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
+ Applied Processor:
KnowledgePropagation
+ Details:
We propagate bounds from predecessors.
* Step 7: LocalSizeboundsProc WORST_CASE(?,O(1))
+ Considered Problem:
Rules:
0. evaleasy1start(A,B) -> evaleasy1entryin(A,B) True (1,1)
1. evaleasy1entryin(A,B) -> evaleasy1bb3in(0,B) True (1,1)
2. evaleasy1bb3in(A,B) -> evaleasy1bbin(A,B) [39 >= A] (40,1)
4. evaleasy1bbin(A,B) -> evaleasy1bb1in(A,B) [B = 0] (40,1)
5. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [0 >= 1 + B] (40,1)
6. evaleasy1bbin(A,B) -> evaleasy1bb2in(A,B) [B >= 1] (40,1)
7. evaleasy1bb1in(A,B) -> evaleasy1bb3in(1 + A,B) True (40,1)
8. evaleasy1bb2in(A,B) -> evaleasy1bb3in(2 + A,B) True (80,1)
Signature:
{(evaleasy1bb1in,2)
;(evaleasy1bb2in,2)
;(evaleasy1bb3in,2)
;(evaleasy1bbin,2)
;(evaleasy1entryin,2)
;(evaleasy1returnin,2)
;(evaleasy1start,2)
;(evaleasy1stop,2)}
Flow Graph:
[0->{1},1->{2},2->{4,5,6},4->{7},5->{8},6->{8},7->{2},8->{2}]
Sizebounds:
(<0,0,A>, A) (<0,0,B>, B)
(<1,0,A>, 0) (<1,0,B>, B)
(<2,0,A>, 39) (<2,0,B>, B)
(<4,0,A>, 39) (<4,0,B>, B)
(<5,0,A>, 39) (<5,0,B>, B)
(<6,0,A>, 39) (<6,0,B>, B)
(<7,0,A>, 39) (<7,0,B>, B)
(<8,0,A>, 39) (<8,0,B>, B)
+ Applied Processor:
LocalSizeboundsProc
+ Details:
The problem is already solved.
WORST_CASE(?,O(1))