/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^2), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).

(0) CpxTRS
(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(2) CdtProblem
    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CdtProblem
    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CdtProblem
    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 46 ms]
    (8) CdtProblem
    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 35 ms]
    (10) CdtProblem
    (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) BOUNDS(1, 1)
(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxTRS
    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) typed CpxTrs
    (17) OrderProof [LOWER BOUND(ID), 0 ms]
    (18) typed CpxTrs
    (19) RewriteLemmaProof [LOWER BOUND(ID), 291 ms]
    (20) BEST
        (21) proven lower bound
            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
            (23) BOUNDS(n^1, INF)
        (24) typed CpxTrs
            (25) RewriteLemmaProof [LOWER BOUND(ID), 5 ms]
            (26) proven lower bound
            (27) LowerBoundPropagationProof [FINISHED, 0 ms]
            (28) BOUNDS(n^2, INF)


----------------------------------------

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).


The TRS R consists of the following rules:

   rev(nil) -> nil
   rev(.(x, y)) -> ++(rev(y), .(x, nil))
   car(.(x, y)) -> x
   cdr(.(x, y)) -> y
   null(nil) -> true
   null(.(x, y)) -> false
   ++(nil, y) -> y
   ++(.(x, y), z) -> .(x, ++(y, z))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   rev(nil) -> nil
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   car(.(z0, z1)) -> z0
   cdr(.(z0, z1)) -> z1
   null(nil) -> true
   null(.(z0, z1)) -> false
   ++(nil, z0) -> z0
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
Tuples:
   REV(nil) -> c
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   CAR(.(z0, z1)) -> c2
   CDR(.(z0, z1)) -> c3
   NULL(nil) -> c4
   NULL(.(z0, z1)) -> c5
   ++'(nil, z0) -> c6
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
S tuples:
   REV(nil) -> c
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   CAR(.(z0, z1)) -> c2
   CDR(.(z0, z1)) -> c3
   NULL(nil) -> c4
   NULL(.(z0, z1)) -> c5
   ++'(nil, z0) -> c6
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
K tuples:none
Defined Rule Symbols:   rev_1, car_1, cdr_1, null_1, ++_2

Defined Pair Symbols:   REV_1, CAR_1, CDR_1, NULL_1, ++'_2

Compound Symbols:   c, c1_2, c2, c3, c4, c5, c6, c7_1


----------------------------------------

(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 6 trailing nodes:
   ++'(nil, z0) -> c6
   NULL(.(z0, z1)) -> c5
   CDR(.(z0, z1)) -> c3
   REV(nil) -> c
   NULL(nil) -> c4
   CAR(.(z0, z1)) -> c2

----------------------------------------

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   rev(nil) -> nil
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   car(.(z0, z1)) -> z0
   cdr(.(z0, z1)) -> z1
   null(nil) -> true
   null(.(z0, z1)) -> false
   ++(nil, z0) -> z0
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
S tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
K tuples:none
Defined Rule Symbols:   rev_1, car_1, cdr_1, null_1, ++_2

Defined Pair Symbols:   REV_1, ++'_2

Compound Symbols:   c1_2, c7_1


----------------------------------------

(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   car(.(z0, z1)) -> z0
   cdr(.(z0, z1)) -> z1
   null(nil) -> true
   null(.(z0, z1)) -> false

----------------------------------------

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   rev(nil) -> nil
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   ++(nil, z0) -> z0
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
S tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
K tuples:none
Defined Rule Symbols:   rev_1, ++_2

Defined Pair Symbols:   REV_1, ++'_2

Compound Symbols:   c1_2, c7_1


----------------------------------------

(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
We considered the (Usable) Rules:none
And the Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(++(x_1, x_2)) = x_1 + x_2
   POL(++'(x_1, x_2)) = 0
   POL(.(x_1, x_2)) = [1] + x_1 + x_2
   POL(REV(x_1)) = x_1
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1)) = x_1
   POL(nil) = 0
   POL(rev(x_1)) = [1] + x_1

----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   rev(nil) -> nil
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   ++(nil, z0) -> z0
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
S tuples:
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
K tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
Defined Rule Symbols:   rev_1, ++_2

Defined Pair Symbols:   REV_1, ++'_2

Compound Symbols:   c1_2, c7_1


----------------------------------------

(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
We considered the (Usable) Rules:
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
   rev(nil) -> nil
   ++(nil, z0) -> z0
And the Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(++(x_1, x_2)) = x_1 + [2]x_2
   POL(++'(x_1, x_2)) = [2]x_1
   POL(.(x_1, x_2)) = [2] + x_2
   POL(REV(x_1)) = x_1^2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1)) = x_1
   POL(nil) = 0
   POL(rev(x_1)) = [2]x_1

----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   rev(nil) -> nil
   rev(.(z0, z1)) -> ++(rev(z1), .(z0, nil))
   ++(nil, z0) -> z0
   ++(.(z0, z1), z2) -> .(z0, ++(z1, z2))
Tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
S tuples:none
K tuples:
   REV(.(z0, z1)) -> c1(++'(rev(z1), .(z0, nil)), REV(z1))
   ++'(.(z0, z1), z2) -> c7(++'(z1, z2))
Defined Rule Symbols:   rev_1, ++_2

Defined Pair Symbols:   REV_1, ++'_2

Compound Symbols:   c1_2, c7_1


----------------------------------------

(11) SIsEmptyProof (BOTH BOUNDS(ID, ID))
The set S is empty
----------------------------------------

(12)
BOUNDS(1, 1)

----------------------------------------

(13) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(14)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   rev(nil) -> nil
   rev(.(x, y)) -> ++(rev(y), .(x, nil))
   car(.(x, y)) -> x
   cdr(.(x, y)) -> y
   null(nil) -> true
   null(.(x, y)) -> false
   ++(nil, y) -> y
   ++(.(x, y), z) -> .(x, ++(y, z))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(16)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.

----------------------------------------

(17) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
rev, ++

They will be analysed ascendingly in the following order:
++ < rev

----------------------------------------

(18)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
++, rev

They will be analysed ascendingly in the following order:
++ < rev

----------------------------------------

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)

Induction Base:
++(gen_nil:.4_0(0), gen_nil:.4_0(b)) ->_R^Omega(1)
gen_nil:.4_0(b)

Induction Step:
++(gen_nil:.4_0(+(n6_0, 1)), gen_nil:.4_0(b)) ->_R^Omega(1)
.(hole_car2_0, ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b))) ->_IH
.(hole_car2_0, gen_nil:.4_0(+(b, c7_0)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(20)
Complex Obligation (BEST)

----------------------------------------

(21)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
++, rev

They will be analysed ascendingly in the following order:
++ < rev

----------------------------------------

(22) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(23)
BOUNDS(n^1, INF)

----------------------------------------

(24)
Obligation:
Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Lemmas:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
rev
----------------------------------------

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
rev(gen_nil:.4_0(n535_0)) -> gen_nil:.4_0(n535_0), rt in Omega(1 + n535_0 + n535_0^2)

Induction Base:
rev(gen_nil:.4_0(0)) ->_R^Omega(1)
nil

Induction Step:
rev(gen_nil:.4_0(+(n535_0, 1))) ->_R^Omega(1)
++(rev(gen_nil:.4_0(n535_0)), .(hole_car2_0, nil)) ->_IH
++(gen_nil:.4_0(c536_0), .(hole_car2_0, nil)) ->_L^Omega(1 + n535_0)
gen_nil:.4_0(+(n535_0, +(0, 1)))

We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
----------------------------------------

(26)
Obligation:
Proved the lower bound n^2 for the following obligation:

Innermost TRS:
Rules:
rev(nil) -> nil
rev(.(x, y)) -> ++(rev(y), .(x, nil))
car(.(x, y)) -> x
cdr(.(x, y)) -> y
null(nil) -> true
null(.(x, y)) -> false
++(nil, y) -> y
++(.(x, y), z) -> .(x, ++(y, z))

Types:
rev :: nil:. -> nil:.
nil :: nil:.
. :: car -> nil:. -> nil:.
++ :: nil:. -> nil:. -> nil:.
car :: nil:. -> car
cdr :: nil:. -> nil:.
null :: nil:. -> true:false
true :: true:false
false :: true:false
hole_nil:.1_0 :: nil:.
hole_car2_0 :: car
hole_true:false3_0 :: true:false
gen_nil:.4_0 :: Nat -> nil:.


Lemmas:
++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0)


Generator Equations:
gen_nil:.4_0(0) <=> nil
gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x))


The following defined symbols remain to be analysed:
rev
----------------------------------------

(27) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(28)
BOUNDS(n^2, INF)