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


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


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxRelTRS
(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 168 ms]
(2) CpxRelTRS
(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(4) CdtProblem
    (5) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (6) CdtProblem
    (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 53 ms]
    (10) CdtProblem
    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 151 ms]
    (12) CdtProblem
    (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) BOUNDS(1, 1)
(15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(16) TRS for Loop Detection
    (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) TRS for Loop Detection


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

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


The TRS R consists of the following rules:

   isort(Cons(x, xs), r) -> isort(xs, insert(x, r))
   isort(Nil, r) -> Nil
   insert(S(x), r) -> insert[Ite](<(S(x), x), S(x), r)
   inssort(xs) -> isort(xs, Nil)

The (relative) TRS S consists of the following rules:

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   insert[Ite](False, x', Cons(x, xs)) -> Cons(x, insert(x', xs))
   insert[Ite](True, x, r) -> Cons(x, r)

Rewrite Strategy: INNERMOST
----------------------------------------

(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

   isort(Cons(x, xs), r) -> isort(xs, insert(x, r))
   isort(Nil, r) -> Nil
   insert(S(x), r) -> insert[Ite](<(S(x), x), S(x), r)
   inssort(xs) -> isort(xs, Nil)

The (relative) TRS S consists of the following rules:

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   insert[Ite](False, x', Cons(x, xs)) -> Cons(x, insert(x', xs))
   insert[Ite](True, x, r) -> Cons(x, r)

Rewrite Strategy: INNERMOST
----------------------------------------

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

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   <(S(z0), S(z1)) -> <(z0, z1)
   <(0, S(z0)) -> True
   <(z0, 0) -> False
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   isort(Cons(z0, z1), z2) -> isort(z1, insert(z0, z2))
   isort(Nil, z0) -> Nil
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   inssort(z0) -> isort(z0, Nil)
Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   <'(0, S(z0)) -> c1
   <'(z0, 0) -> c2
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   INSERT[ITE](True, z0, z1) -> c4
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   ISORT(Nil, z0) -> c6
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
   INSSORT(z0) -> c8(ISORT(z0, Nil))
S tuples:
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   ISORT(Nil, z0) -> c6
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
   INSSORT(z0) -> c8(ISORT(z0, Nil))
K tuples:none
Defined Rule Symbols:   isort_2, insert_2, inssort_1, <_2, insert[Ite]_3

Defined Pair Symbols:   <'_2, INSERT[ITE]_3, ISORT_2, INSERT_2, INSSORT_1

Compound Symbols:   c_1, c1, c2, c3_1, c4, c5_2, c6, c7_2, c8_1


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

(5) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 1 leading nodes:
   INSSORT(z0) -> c8(ISORT(z0, Nil))
Removed 4 trailing nodes:
   <'(z0, 0) -> c2
   INSERT[ITE](True, z0, z1) -> c4
   <'(0, S(z0)) -> c1
   ISORT(Nil, z0) -> c6

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   <(S(z0), S(z1)) -> <(z0, z1)
   <(0, S(z0)) -> True
   <(z0, 0) -> False
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   isort(Cons(z0, z1), z2) -> isort(z1, insert(z0, z2))
   isort(Nil, z0) -> Nil
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   inssort(z0) -> isort(z0, Nil)
Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
S tuples:
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
K tuples:none
Defined Rule Symbols:   isort_2, insert_2, inssort_1, <_2, insert[Ite]_3

Defined Pair Symbols:   <'_2, INSERT[ITE]_3, ISORT_2, INSERT_2

Compound Symbols:   c_1, c3_1, c5_2, c7_2


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

(7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   isort(Cons(z0, z1), z2) -> isort(z1, insert(z0, z2))
   isort(Nil, z0) -> Nil
   inssort(z0) -> isort(z0, Nil)

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

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   <(S(z0), S(z1)) -> <(z0, z1)
   <(z0, 0) -> False
   <(0, S(z0)) -> True
Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
S tuples:
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
K tuples:none
Defined Rule Symbols:   insert_2, insert[Ite]_3, <_2

Defined Pair Symbols:   <'_2, INSERT[ITE]_3, ISORT_2, INSERT_2

Compound Symbols:   c_1, c3_1, c5_2, c7_2


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

(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
We considered the (Usable) Rules:none
And the Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(<(x_1, x_2)) = [1] + x_2
   POL(<'(x_1, x_2)) = 0
   POL(Cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(False) = [1]
   POL(INSERT(x_1, x_2)) = 0
   POL(INSERT[ITE](x_1, x_2, x_3)) = x_2
   POL(ISORT(x_1, x_2)) = x_1
   POL(S(x_1)) = 0
   POL(True) = [1]
   POL(c(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1, x_2)) = x_1 + x_2
   POL(insert(x_1, x_2)) = [1] + x_1 + x_2
   POL(insert[Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   <(S(z0), S(z1)) -> <(z0, z1)
   <(z0, 0) -> False
   <(0, S(z0)) -> True
Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
S tuples:
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
K tuples:
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
Defined Rule Symbols:   insert_2, insert[Ite]_3, <_2

Defined Pair Symbols:   <'_2, INSERT[ITE]_3, ISORT_2, INSERT_2

Compound Symbols:   c_1, c3_1, c5_2, c7_2


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

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
We considered the (Usable) Rules:
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
And the Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(<(x_1, x_2)) = 0
   POL(<'(x_1, x_2)) = 0
   POL(Cons(x_1, x_2)) = [1] + x_1 + x_2
   POL(False) = 0
   POL(INSERT(x_1, x_2)) = [2]x_1 + x_1*x_2
   POL(INSERT[ITE](x_1, x_2, x_3)) = x_2 + x_2*x_3
   POL(ISORT(x_1, x_2)) = x_1*x_2 + [2]x_1^2
   POL(S(x_1)) = [2]
   POL(True) = 0
   POL(c(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c7(x_1, x_2)) = x_1 + x_2
   POL(insert(x_1, x_2)) = [1] + x_1 + x_2
   POL(insert[Ite](x_1, x_2, x_3)) = [1] + x_2 + x_3

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   insert(S(z0), z1) -> insert[Ite](<(S(z0), z0), S(z0), z1)
   insert[Ite](False, z0, Cons(z1, z2)) -> Cons(z1, insert(z0, z2))
   insert[Ite](True, z0, z1) -> Cons(z0, z1)
   <(S(z0), S(z1)) -> <(z0, z1)
   <(z0, 0) -> False
   <(0, S(z0)) -> True
Tuples:
   <'(S(z0), S(z1)) -> c(<'(z0, z1))
   INSERT[ITE](False, z0, Cons(z1, z2)) -> c3(INSERT(z0, z2))
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
S tuples:none
K tuples:
   ISORT(Cons(z0, z1), z2) -> c5(ISORT(z1, insert(z0, z2)), INSERT(z0, z2))
   INSERT(S(z0), z1) -> c7(INSERT[ITE](<(S(z0), z0), S(z0), z1), <'(S(z0), z0))
Defined Rule Symbols:   insert_2, insert[Ite]_3, <_2

Defined Pair Symbols:   <'_2, INSERT[ITE]_3, ISORT_2, INSERT_2

Compound Symbols:   c_1, c3_1, c5_2, c7_2


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

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

(14)
BOUNDS(1, 1)

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

(15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(16)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   isort(Cons(x, xs), r) -> isort(xs, insert(x, r))
   isort(Nil, r) -> Nil
   insert(S(x), r) -> insert[Ite](<(S(x), x), S(x), r)
   inssort(xs) -> isort(xs, Nil)

The (relative) TRS S consists of the following rules:

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   insert[Ite](False, x', Cons(x, xs)) -> Cons(x, insert(x', xs))
   insert[Ite](True, x, r) -> Cons(x, r)

Rewrite Strategy: INNERMOST
----------------------------------------

(17) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

isort(Cons(x, xs), r) ->^+ isort(xs, insert(x, r))

gives rise to a decreasing loop by considering the right hand sides subterm at position [].

The pumping substitution is [xs / Cons(x, xs)].

The result substitution is [r / insert(x, r)].




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

(18)
Complex Obligation (BEST)

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

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

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


The TRS R consists of the following rules:

   isort(Cons(x, xs), r) -> isort(xs, insert(x, r))
   isort(Nil, r) -> Nil
   insert(S(x), r) -> insert[Ite](<(S(x), x), S(x), r)
   inssort(xs) -> isort(xs, Nil)

The (relative) TRS S consists of the following rules:

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   insert[Ite](False, x', Cons(x, xs)) -> Cons(x, insert(x', xs))
   insert[Ite](True, x, r) -> Cons(x, r)

Rewrite Strategy: INNERMOST
----------------------------------------

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Analyzing the following TRS for decreasing loops:

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


The TRS R consists of the following rules:

   isort(Cons(x, xs), r) -> isort(xs, insert(x, r))
   isort(Nil, r) -> Nil
   insert(S(x), r) -> insert[Ite](<(S(x), x), S(x), r)
   inssort(xs) -> isort(xs, Nil)

The (relative) TRS S consists of the following rules:

   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   insert[Ite](False, x', Cons(x, xs)) -> Cons(x, insert(x', xs))
   insert[Ite](True, x, r) -> Cons(x, r)

Rewrite Strategy: INNERMOST