/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^1))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

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


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

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


The TRS R consists of the following rules:

   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
   lte(Cons(x, xs), Nil) -> False
   even(Cons(x, Nil)) -> False
   even(Cons(x', Cons(x, xs))) -> even(xs)
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lte(Nil, y) -> True
   even(Nil) -> True
   goal(x, y) -> and(lte(x, y), even(x))

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

   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True

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

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

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


The TRS R consists of the following rules:

   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
   lte(Cons(x, xs), Nil) -> False
   even(Cons(x, Nil)) -> False
   even(Cons(x', Cons(x, xs))) -> even(xs)
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lte(Nil, y) -> True
   even(Nil) -> True
   goal(x, y) -> and(lte(x, y), even(x))

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

   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True

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

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

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))
Tuples:
   AND(False, False) -> c
   AND(True, False) -> c1
   AND(False, True) -> c2
   AND(True, True) -> c3
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   LTE(Cons(z0, z1), Nil) -> c5
   LTE(Nil, z0) -> c6
   EVEN(Cons(z0, Nil)) -> c7
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   EVEN(Nil) -> c9
   NOTEMPTY(Cons(z0, z1)) -> c10
   NOTEMPTY(Nil) -> c11
   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   LTE(Cons(z0, z1), Nil) -> c5
   LTE(Nil, z0) -> c6
   EVEN(Cons(z0, Nil)) -> c7
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   EVEN(Nil) -> c9
   NOTEMPTY(Cons(z0, z1)) -> c10
   NOTEMPTY(Nil) -> c11
   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
K tuples:none
Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2

Defined Pair Symbols:   AND_2, LTE_2, EVEN_1, NOTEMPTY_1, GOAL_2

Compound Symbols:   c, c1, c2, c3, c4_1, c5, c6, c7, c8_1, c9, c10, c11, c12_3


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

(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 10 trailing nodes:
   AND(False, False) -> c
   LTE(Nil, z0) -> c6
   AND(True, False) -> c1
   EVEN(Nil) -> c9
   LTE(Cons(z0, z1), Nil) -> c5
   AND(True, True) -> c3
   AND(False, True) -> c2
   NOTEMPTY(Nil) -> c11
   NOTEMPTY(Cons(z0, z1)) -> c10
   EVEN(Cons(z0, Nil)) -> c7

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c12(AND(lte(z0, z1), even(z0)), LTE(z0, z1), EVEN(z0))
K tuples:none
Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2

Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2

Compound Symbols:   c4_1, c8_1, c12_3


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

(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 1 trailing tuple parts
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c12(LTE(z0, z1), EVEN(z0))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c12(LTE(z0, z1), EVEN(z0))
K tuples:none
Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2

Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2

Compound Symbols:   c4_1, c8_1, c12_2


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

(9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
Split RHS of tuples not part of any SCC
----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c(LTE(z0, z1))
   GOAL(z0, z1) -> c(EVEN(z0))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
   GOAL(z0, z1) -> c(LTE(z0, z1))
   GOAL(z0, z1) -> c(EVEN(z0))
K tuples:none
Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2

Defined Pair Symbols:   LTE_2, EVEN_1, GOAL_2

Compound Symbols:   c4_1, c8_1, c_1


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

(11) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 2 leading nodes:
   GOAL(z0, z1) -> c(LTE(z0, z1))
   GOAL(z0, z1) -> c(EVEN(z0))

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
K tuples:none
Defined Rule Symbols:   lte_2, even_1, notEmpty_1, goal_2, and_2

Defined Pair Symbols:   LTE_2, EVEN_1

Compound Symbols:   c4_1, c8_1


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

(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True
   lte(Cons(z0, z1), Cons(z2, z3)) -> lte(z1, z3)
   lte(Cons(z0, z1), Nil) -> False
   lte(Nil, z0) -> True
   even(Cons(z0, Nil)) -> False
   even(Cons(z0, Cons(z1, z2))) -> even(z2)
   even(Nil) -> True
   notEmpty(Cons(z0, z1)) -> True
   notEmpty(Nil) -> False
   goal(z0, z1) -> and(lte(z0, z1), even(z0))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:none
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
S tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
K tuples:none
Defined Rule Symbols:none

Defined Pair Symbols:   LTE_2, EVEN_1

Compound Symbols:   c4_1, c8_1


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

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
We considered the (Usable) Rules:none
And the Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(Cons(x_1, x_2)) = [1] + x_2
   POL(EVEN(x_1)) = x_1
   POL(LTE(x_1, x_2)) = x_1 + x_2
   POL(c4(x_1)) = x_1
   POL(c8(x_1)) = x_1

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:none
Tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
S tuples:none
K tuples:
   LTE(Cons(z0, z1), Cons(z2, z3)) -> c4(LTE(z1, z3))
   EVEN(Cons(z0, Cons(z1, z2))) -> c8(EVEN(z2))
Defined Rule Symbols:none

Defined Pair Symbols:   LTE_2, EVEN_1

Compound Symbols:   c4_1, c8_1


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

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

(18)
BOUNDS(1, 1)

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

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

(20)
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^1).


The TRS R consists of the following rules:

   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
   lte(Cons(x, xs), Nil) -> False
   even(Cons(x, Nil)) -> False
   even(Cons(x', Cons(x, xs))) -> even(xs)
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lte(Nil, y) -> True
   even(Nil) -> True
   goal(x, y) -> and(lte(x, y), even(x))

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

   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True

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

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

The rewrite sequence

lte(Cons(x', xs'), Cons(x, xs)) ->^+ lte(xs', xs)

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

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

The result substitution is [ ].




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

(22)
Complex Obligation (BEST)

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

(23)
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^1).


The TRS R consists of the following rules:

   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
   lte(Cons(x, xs), Nil) -> False
   even(Cons(x, Nil)) -> False
   even(Cons(x', Cons(x, xs))) -> even(xs)
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lte(Nil, y) -> True
   even(Nil) -> True
   goal(x, y) -> and(lte(x, y), even(x))

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

   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
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^1).


The TRS R consists of the following rules:

   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
   lte(Cons(x, xs), Nil) -> False
   even(Cons(x, Nil)) -> False
   even(Cons(x', Cons(x, xs))) -> even(xs)
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lte(Nil, y) -> True
   even(Nil) -> True
   goal(x, y) -> and(lte(x, y), even(x))

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

   and(False, False) -> False
   and(True, False) -> False
   and(False, True) -> False
   and(True, True) -> True

Rewrite Strategy: INNERMOST