KILLED
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, INF).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 63 ms]
(4) CpxRelTRS
(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) typed CpxTrs
    (9) OrderProof [LOWER BOUND(ID), 0 ms]
    (10) typed CpxTrs
    (11) RewriteLemmaProof [LOWER BOUND(ID), 479 ms]
    (12) BOUNDS(1, INF)
(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(14) TRS for Loop Detection
(15) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
(16) CpxTRS
(17) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms]
(18) CpxRelTRS
    (19) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
    (20) CpxRelTRS
    (21) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (22) CpxWeightedTrs
        (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
        (24) CpxTypedWeightedTrs
        (25) CompletionProof [UPPER BOUND(ID), 0 ms]
        (26) CpxTypedWeightedCompleteTrs
            (27) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
            (28) CpxTypedWeightedCompleteTrs
            (29) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
            (30) CpxRNTS
            (31) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
            (32) CpxRNTS
        (33) CompletionProof [UPPER BOUND(ID), 0 ms]
        (34) CpxTypedWeightedCompleteTrs
            (35) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 5 ms]
            (36) CpxRNTS
    (37) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
    (38) CdtProblem
        (39) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
        (40) CdtProblem
        (41) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
        (42) CdtProblem
        (43) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
        (44) CdtProblem
        (45) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
        (46) CdtProblem
        (47) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (48) CdtProblem
        (49) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (50) CdtProblem
        (51) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (52) CdtProblem
        (53) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (54) CdtProblem
        (55) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (56) CdtProblem
        (57) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
        (58) CdtProblem
        (59) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (60) CdtProblem
        (61) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (62) CdtProblem
        (63) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (64) CdtProblem
        (65) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (66) CdtProblem
        (67) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (68) CdtProblem
        (69) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (70) CdtProblem
        (71) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (72) CdtProblem
        (73) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (74) CdtProblem
        (75) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
        (76) CdtProblem
        (77) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (78) CdtProblem
        (79) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms]
        (80) CdtProblem
        (81) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 0 ms]
        (82) CdtProblem
        (83) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (84) CdtProblem
        (85) CdtRewritingProof [BOTH BOUNDS(ID, ID), 4 ms]
        (86) CdtProblem
        (87) CdtForwardInstantiationProof [BOTH BOUNDS(ID, ID), 15 ms]
        (88) CdtProblem
        (89) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (90) CdtProblem
        (91) CdtRewritingProof [BOTH BOUNDS(ID, ID), 15 ms]
        (92) CdtProblem
        (93) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (94) CdtProblem
        (95) CdtRewritingProof [BOTH BOUNDS(ID, ID), 0 ms]
        (96) CdtProblem
        (97) CdtRewritingProof [BOTH BOUNDS(ID, ID), 23 ms]
        (98) CdtProblem
        (99) CdtRewritingProof [BOTH BOUNDS(ID, ID), 12 ms]
        (100) CdtProblem
        (101) CdtRewritingProof [BOTH BOUNDS(ID, ID), 38 ms]
        (102) CdtProblem
        (103) CdtRewritingProof [BOTH BOUNDS(ID, ID), 9 ms]
        (104) CdtProblem
        (105) CdtRewritingProof [BOTH BOUNDS(ID, ID), 32 ms]
        (106) CdtProblem
        (107) CdtRewritingProof [BOTH BOUNDS(ID, ID), 28 ms]
        (108) CdtProblem
        (109) CdtRewritingProof [BOTH BOUNDS(ID, ID), 14 ms]
        (110) CdtProblem


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

(0)
Obligation:
The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))

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

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))


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

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


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

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

(4)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

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

(6)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

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

(8)
Obligation:
TRS:
Rules:
a(x1) -> x1
a(a(x1)) -> b(x1)
b(a(b(x1))) -> a(a(b(b(b(x1)))))
encArg(cons_a(x_1)) -> a(encArg(x_1))
encArg(cons_b(x_1)) -> b(encArg(x_1))
encode_a(x_1) -> a(encArg(x_1))
encode_b(x_1) -> b(encArg(x_1))

Types:
a :: a:b:encArg:encode_a:encode_b -> a:b:encArg:encode_a:encode_b
b :: a:b:encArg:encode_a:encode_b -> a:b:encArg:encode_a:encode_b
encArg :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
cons_a :: cons_a:cons_b -> cons_a:cons_b
cons_b :: cons_a:cons_b -> cons_a:cons_b
encode_a :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
encode_b :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
hole_a:b:encArg:encode_a:encode_b1_0 :: a:b:encArg:encode_a:encode_b
hole_cons_a:cons_b2_0 :: cons_a:cons_b
gen_cons_a:cons_b3_0 :: Nat -> cons_a:cons_b

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

(9) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
a, b, encArg

They will be analysed ascendingly in the following order:
a = b
a < encArg
b < encArg

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

(10)
Obligation:
TRS:
Rules:
a(x1) -> x1
a(a(x1)) -> b(x1)
b(a(b(x1))) -> a(a(b(b(b(x1)))))
encArg(cons_a(x_1)) -> a(encArg(x_1))
encArg(cons_b(x_1)) -> b(encArg(x_1))
encode_a(x_1) -> a(encArg(x_1))
encode_b(x_1) -> b(encArg(x_1))

Types:
a :: a:b:encArg:encode_a:encode_b -> a:b:encArg:encode_a:encode_b
b :: a:b:encArg:encode_a:encode_b -> a:b:encArg:encode_a:encode_b
encArg :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
cons_a :: cons_a:cons_b -> cons_a:cons_b
cons_b :: cons_a:cons_b -> cons_a:cons_b
encode_a :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
encode_b :: cons_a:cons_b -> a:b:encArg:encode_a:encode_b
hole_a:b:encArg:encode_a:encode_b1_0 :: a:b:encArg:encode_a:encode_b
hole_cons_a:cons_b2_0 :: cons_a:cons_b
gen_cons_a:cons_b3_0 :: Nat -> cons_a:cons_b


Generator Equations:
gen_cons_a:cons_b3_0(0) <=> hole_cons_a:cons_b2_0
gen_cons_a:cons_b3_0(+(x, 1)) <=> cons_a(gen_cons_a:cons_b3_0(x))


The following defined symbols remain to be analysed:
b, a, encArg

They will be analysed ascendingly in the following order:
a = b
a < encArg
b < encArg

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_cons_a:cons_b3_0(+(1, n13_0))) -> *4_0, rt in Omega(0)

Induction Base:
encArg(gen_cons_a:cons_b3_0(+(1, 0)))

Induction Step:
encArg(gen_cons_a:cons_b3_0(+(1, +(n13_0, 1)))) ->_R^Omega(0)
a(encArg(gen_cons_a:cons_b3_0(+(1, n13_0)))) ->_IH
a(*4_0)

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

(12)
BOUNDS(1, INF)

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

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

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

The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))

Rewrite Strategy: FULL
----------------------------------------

(15) RelTrsToTrsProof (UPPER BOUND(ID))
transformed relative TRS to TRS
----------------------------------------

(16)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(a(x1)) -> b(x1)
   b(a(b(x1))) -> a(a(b(b(b(x1)))))
   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))

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

(17) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

(18)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1
   a(c_a(x1)) -> b(x1)
   b(c_a(c_b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))
   a(x0) -> c_a(x0)
   b(x0) -> c_b(x0)

Rewrite Strategy: FULL
----------------------------------------

(19) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   a(x1) -> x1
   a(c_a(x1)) -> b(x1)
   b(c_a(c_b(x1))) -> a(a(b(b(b(x1)))))

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

   encArg(cons_a(x_1)) -> a(encArg(x_1))
   encArg(cons_b(x_1)) -> b(encArg(x_1))
   encode_a(x_1) -> a(encArg(x_1))
   encode_b(x_1) -> b(encArg(x_1))
   a(x0) -> c_a(x0)
   b(x0) -> c_b(x0)

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

(21) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

(22)
Obligation:
The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, INF).


The TRS R consists of the following rules:

   a(x1) -> x1 [1]
   a(c_a(x1)) -> b(x1) [1]
   b(c_a(c_b(x1))) -> a(a(b(b(b(x1))))) [1]
   encArg(cons_a(x_1)) -> a(encArg(x_1)) [0]
   encArg(cons_b(x_1)) -> b(encArg(x_1)) [0]
   encode_a(x_1) -> a(encArg(x_1)) [0]
   encode_b(x_1) -> b(encArg(x_1)) [0]
   a(x0) -> c_a(x0) [0]
   b(x0) -> c_b(x0) [0]

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

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

(24)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   a(x1) -> x1 [1]
   a(c_a(x1)) -> b(x1) [1]
   b(c_a(c_b(x1))) -> a(a(b(b(b(x1))))) [1]
   encArg(cons_a(x_1)) -> a(encArg(x_1)) [0]
   encArg(cons_b(x_1)) -> b(encArg(x_1)) [0]
   encode_a(x_1) -> a(encArg(x_1)) [0]
   encode_b(x_1) -> b(encArg(x_1)) [0]
   a(x0) -> c_a(x0) [0]
   b(x0) -> c_b(x0) [0]

The TRS has the following type information:
a :: c_a:c_b -> c_a:c_b
c_a :: c_a:c_b -> c_a:c_b
b :: c_a:c_b -> c_a:c_b
c_b :: c_a:c_b -> c_a:c_b
encArg :: cons_a:cons_b -> c_a:c_b
cons_a :: cons_a:cons_b -> cons_a:cons_b
cons_b :: cons_a:cons_b -> cons_a:cons_b
encode_a :: cons_a:cons_b -> c_a:c_b
encode_b :: cons_a:cons_b -> c_a:c_b

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

(25) CompletionProof (UPPER BOUND(ID))
The transformation into a RNTS is sound, since:

(a) The obligation is a constructor system where every type has a constant constructor,

(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
none

(c) The following functions are completely defined:

   encArg_1
   encode_a_1
   encode_b_1
   a_1
   b_1

Due to the following rules being added:

   encArg(v0) -> const [0]
   encode_a(v0) -> const [0]
   encode_b(v0) -> const [0]
   a(v0) -> const [0]
   b(v0) -> const [0]

And the following fresh constants:    const, const1

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

(26)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   a(x1) -> x1 [1]
   a(c_a(x1)) -> b(x1) [1]
   b(c_a(c_b(x1))) -> a(a(b(b(b(x1))))) [1]
   encArg(cons_a(x_1)) -> a(encArg(x_1)) [0]
   encArg(cons_b(x_1)) -> b(encArg(x_1)) [0]
   encode_a(x_1) -> a(encArg(x_1)) [0]
   encode_b(x_1) -> b(encArg(x_1)) [0]
   a(x0) -> c_a(x0) [0]
   b(x0) -> c_b(x0) [0]
   encArg(v0) -> const [0]
   encode_a(v0) -> const [0]
   encode_b(v0) -> const [0]
   a(v0) -> const [0]
   b(v0) -> const [0]

The TRS has the following type information:
a :: c_a:c_b:const -> c_a:c_b:const
c_a :: c_a:c_b:const -> c_a:c_b:const
b :: c_a:c_b:const -> c_a:c_b:const
c_b :: c_a:c_b:const -> c_a:c_b:const
encArg :: cons_a:cons_b -> c_a:c_b:const
cons_a :: cons_a:cons_b -> cons_a:cons_b
cons_b :: cons_a:cons_b -> cons_a:cons_b
encode_a :: cons_a:cons_b -> c_a:c_b:const
encode_b :: cons_a:cons_b -> c_a:c_b:const
const :: c_a:c_b:const
const1 :: cons_a:cons_b

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

(27) N