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


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


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


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

(0) CpxTRS
(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) typed CpxTrs
(5) OrderProof [LOWER BOUND(ID), 0 ms]
(6) typed CpxTrs
(7) RewriteLemmaProof [LOWER BOUND(ID), 18.3 s]
(8) BEST
    (9) proven lower bound
        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
        (11) BOUNDS(n^1, INF)
    (12) typed CpxTrs
        (13) RewriteLemmaProof [LOWER BOUND(ID), 1281 ms]
        (14) typed CpxTrs
        (15) RewriteLemmaProof [LOWER BOUND(ID), 2108 ms]
        (16) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   0(#) -> #
   +(#, x) -> x
   +(x, #) -> x
   +(0(x), 0(y)) -> 0(+(x, y))
   +(0(x), 1(y)) -> 1(+(x, y))
   +(1(x), 0(y)) -> 1(+(x, y))
   +(0(x), j(y)) -> j(+(x, y))
   +(j(x), 0(y)) -> j(+(x, y))
   +(1(x), 1(y)) -> j(+(+(x, y), 1(#)))
   +(j(x), j(y)) -> 1(+(+(x, y), j(#)))
   +(1(x), j(y)) -> 0(+(x, y))
   +(j(x), 1(y)) -> 0(+(x, y))
   +(+(x, y), z) -> +(x, +(y, z))
   opp(#) -> #
   opp(0(x)) -> 0(opp(x))
   opp(1(x)) -> j(opp(x))
   opp(j(x)) -> 1(opp(x))
   -(x, y) -> +(x, opp(y))
   *(#, x) -> #
   *(0(x), y) -> 0(*(x, y))
   *(1(x), y) -> +(0(*(x, y)), y)
   *(j(x), y) -> -(0(*(x, y)), y)
   *(*(x, y), z) -> *(x, *(y, z))
   *(+(x, y), z) -> +(*(x, z), *(y, z))
   *(x, +(y, z)) -> +(*(x, y), *(x, z))

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

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

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


The TRS R consists of the following rules:

   0(#) -> #
   +'(#, x) -> x
   +'(x, #) -> x
   +'(0(x), 0(y)) -> 0(+'(x, y))
   +'(0(x), 1(y)) -> 1(+'(x, y))
   +'(1(x), 0(y)) -> 1(+'(x, y))
   +'(0(x), j(y)) -> j(+'(x, y))
   +'(j(x), 0(y)) -> j(+'(x, y))
   +'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
   +'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
   +'(1(x), j(y)) -> 0(+'(x, y))
   +'(j(x), 1(y)) -> 0(+'(x, y))
   +'(+'(x, y), z) -> +'(x, +'(y, z))
   opp(#) -> #
   opp(0(x)) -> 0(opp(x))
   opp(1(x)) -> j(opp(x))
   opp(j(x)) -> 1(opp(x))
   -(x, y) -> +'(x, opp(y))
   *'(#, x) -> #
   *'(0(x), y) -> 0(*'(x, y))
   *'(1(x), y) -> +'(0(*'(x, y)), y)
   *'(j(x), y) -> -(0(*'(x, y)), y)
   *'(*'(x, y), z) -> *'(x, *'(y, z))
   *'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
   *'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

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

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

(4)
Obligation:
TRS:
Rules:
0(#) -> #
+'(#, x) -> x
+'(x, #) -> x
+'(0(x), 0(y)) -> 0(+'(x, y))
+'(0(x), 1(y)) -> 1(+'(x, y))
+'(1(x), 0(y)) -> 1(+'(x, y))
+'(0(x), j(y)) -> j(+'(x, y))
+'(j(x), 0(y)) -> j(+'(x, y))
+'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
+'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
+'(1(x), j(y)) -> 0(+'(x, y))
+'(j(x), 1(y)) -> 0(+'(x, y))
+'(+'(x, y), z) -> +'(x, +'(y, z))
opp(#) -> #
opp(0(x)) -> 0(opp(x))
opp(1(x)) -> j(opp(x))
opp(j(x)) -> 1(opp(x))
-(x, y) -> +'(x, opp(y))
*'(#, x) -> #
*'(0(x), y) -> 0(*'(x, y))
*'(1(x), y) -> +'(0(*'(x, y)), y)
*'(j(x), y) -> -(0(*'(x, y)), y)
*'(*'(x, y), z) -> *'(x, *'(y, z))
*'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
*'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

Types:
0 :: #:1:j -> #:1:j
# :: #:1:j
+' :: #:1:j -> #:1:j -> #:1:j
1 :: #:1:j -> #:1:j
j :: #:1:j -> #:1:j
opp :: #:1:j -> #:1:j
- :: #:1:j -> #:1:j -> #:1:j
*' :: #:1:j -> #:1:j -> #:1:j
hole_#:1:j1_2 :: #:1:j
gen_#:1:j2_2 :: Nat -> #:1:j

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

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
+', opp, *'

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

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

(6)
Obligation:
TRS:
Rules:
0(#) -> #
+'(#, x) -> x
+'(x, #) -> x
+'(0(x), 0(y)) -> 0(+'(x, y))
+'(0(x), 1(y)) -> 1(+'(x, y))
+'(1(x), 0(y)) -> 1(+'(x, y))
+'(0(x), j(y)) -> j(+'(x, y))
+'(j(x), 0(y)) -> j(+'(x, y))
+'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
+'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
+'(1(x), j(y)) -> 0(+'(x, y))
+'(j(x), 1(y)) -> 0(+'(x, y))
+'(+'(x, y), z) -> +'(x, +'(y, z))
opp(#) -> #
opp(0(x)) -> 0(opp(x))
opp(1(x)) -> j(opp(x))
opp(j(x)) -> 1(opp(x))
-(x, y) -> +'(x, opp(y))
*'(#, x) -> #
*'(0(x), y) -> 0(*'(x, y))
*'(1(x), y) -> +'(0(*'(x, y)), y)
*'(j(x), y) -> -(0(*'(x, y)), y)
*'(*'(x, y), z) -> *'(x, *'(y, z))
*'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
*'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

Types:
0 :: #:1:j -> #:1:j
# :: #:1:j
+' :: #:1:j -> #:1:j -> #:1:j
1 :: #:1:j -> #:1:j
j :: #:1:j -> #:1:j
opp :: #:1:j -> #:1:j
- :: #:1:j -> #:1:j -> #:1:j
*' :: #:1:j -> #:1:j -> #:1:j
hole_#:1:j1_2 :: #:1:j
gen_#:1:j2_2 :: Nat -> #:1:j


Generator Equations:
gen_#:1:j2_2(0) <=> #
gen_#:1:j2_2(+(x, 1)) <=> 1(gen_#:1:j2_2(x))


The following defined symbols remain to be analysed:
+', opp, *'

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

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

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
+'(gen_#:1:j2_2(+(1, n4_2)), gen_#:1:j2_2(+(1, n4_2))) -> *3_2, rt in Omega(n4_2)

Induction Base:
+'(gen_#:1:j2_2(+(1, 0)), gen_#:1:j2_2(+(1, 0)))

Induction Step:
+'(gen_#:1:j2_2(+(1, +(n4_2, 1))), gen_#:1:j2_2(+(1, +(n4_2, 1)))) ->_R^Omega(1)
j(+'(+'(gen_#:1:j2_2(+(1, n4_2)), gen_#:1:j2_2(+(1, n4_2))), 1(#))) ->_IH
j(+'(*3_2, 1(#)))

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

(8)
Complex Obligation (BEST)

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

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

TRS:
Rules:
0(#) -> #
+'(#, x) -> x
+'(x, #) -> x
+'(0(x), 0(y)) -> 0(+'(x, y))
+'(0(x), 1(y)) -> 1(+'(x, y))
+'(1(x), 0(y)) -> 1(+'(x, y))
+'(0(x), j(y)) -> j(+'(x, y))
+'(j(x), 0(y)) -> j(+'(x, y))
+'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
+'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
+'(1(x), j(y)) -> 0(+'(x, y))
+'(j(x), 1(y)) -> 0(+'(x, y))
+'(+'(x, y), z) -> +'(x, +'(y, z))
opp(#) -> #
opp(0(x)) -> 0(opp(x))
opp(1(x)) -> j(opp(x))
opp(j(x)) -> 1(opp(x))
-(x, y) -> +'(x, opp(y))
*'(#, x) -> #
*'(0(x), y) -> 0(*'(x, y))
*'(1(x), y) -> +'(0(*'(x, y)), y)
*'(j(x), y) -> -(0(*'(x, y)), y)
*'(*'(x, y), z) -> *'(x, *'(y, z))
*'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
*'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

Types:
0 :: #:1:j -> #:1:j
# :: #:1:j
+' :: #:1:j -> #:1:j -> #:1:j
1 :: #:1:j -> #:1:j
j :: #:1:j -> #:1:j
opp :: #:1:j -> #:1:j
- :: #:1:j -> #:1:j -> #:1:j
*' :: #:1:j -> #:1:j -> #:1:j
hole_#:1:j1_2 :: #:1:j
gen_#:1:j2_2 :: Nat -> #:1:j


Generator Equations:
gen_#:1:j2_2(0) <=> #
gen_#:1:j2_2(+(x, 1)) <=> 1(gen_#:1:j2_2(x))


The following defined symbols remain to be analysed:
+', opp, *'

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

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

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

(11)
BOUNDS(n^1, INF)

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

(12)
Obligation:
TRS:
Rules:
0(#) -> #
+'(#, x) -> x
+'(x, #) -> x
+'(0(x), 0(y)) -> 0(+'(x, y))
+'(0(x), 1(y)) -> 1(+'(x, y))
+'(1(x), 0(y)) -> 1(+'(x, y))
+'(0(x), j(y)) -> j(+'(x, y))
+'(j(x), 0(y)) -> j(+'(x, y))
+'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
+'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
+'(1(x), j(y)) -> 0(+'(x, y))
+'(j(x), 1(y)) -> 0(+'(x, y))
+'(+'(x, y), z) -> +'(x, +'(y, z))
opp(#) -> #
opp(0(x)) -> 0(opp(x))
opp(1(x)) -> j(opp(x))
opp(j(x)) -> 1(opp(x))
-(x, y) -> +'(x, opp(y))
*'(#, x) -> #
*'(0(x), y) -> 0(*'(x, y))
*'(1(x), y) -> +'(0(*'(x, y)), y)
*'(j(x), y) -> -(0(*'(x, y)), y)
*'(*'(x, y), z) -> *'(x, *'(y, z))
*'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
*'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

Types:
0 :: #:1:j -> #:1:j
# :: #:1:j
+' :: #:1:j -> #:1:j -> #:1:j
1 :: #:1:j -> #:1:j
j :: #:1:j -> #:1:j
opp :: #:1:j -> #:1:j
- :: #:1:j -> #:1:j -> #:1:j
*' :: #:1:j -> #:1:j -> #:1:j
hole_#:1:j1_2 :: #:1:j
gen_#:1:j2_2 :: Nat -> #:1:j


Lemmas:
+'(gen_#:1:j2_2(+(1, n4_2)), gen_#:1:j2_2(+(1, n4_2))) -> *3_2, rt in Omega(n4_2)


Generator Equations:
gen_#:1:j2_2(0) <=> #
gen_#:1:j2_2(+(x, 1)) <=> 1(gen_#:1:j2_2(x))


The following defined symbols remain to be analysed:
opp, *'
----------------------------------------

(13) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
opp(gen_#:1:j2_2(+(1, n6450904_2))) -> *3_2, rt in Omega(n6450904_2)

Induction Base:
opp(gen_#:1:j2_2(+(1, 0)))

Induction Step:
opp(gen_#:1:j2_2(+(1, +(n6450904_2, 1)))) ->_R^Omega(1)
j(opp(gen_#:1:j2_2(+(1, n6450904_2)))) ->_IH
j(*3_2)

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

(14)
Obligation:
TRS:
Rules:
0(#) -> #
+'(#, x) -> x
+'(x, #) -> x
+'(0(x), 0(y)) -> 0(+'(x, y))
+'(0(x), 1(y)) -> 1(+'(x, y))
+'(1(x), 0(y)) -> 1(+'(x, y))
+'(0(x), j(y)) -> j(+'(x, y))
+'(j(x), 0(y)) -> j(+'(x, y))
+'(1(x), 1(y)) -> j(+'(+'(x, y), 1(#)))
+'(j(x), j(y)) -> 1(+'(+'(x, y), j(#)))
+'(1(x), j(y)) -> 0(+'(x, y))
+'(j(x), 1(y)) -> 0(+'(x, y))
+'(+'(x, y), z) -> +'(x, +'(y, z))
opp(#) -> #
opp(0(x)) -> 0(opp(x))
opp(1(x)) -> j(opp(x))
opp(j(x)) -> 1(opp(x))
-(x, y) -> +'(x, opp(y))
*'(#, x) -> #
*'(0(x), y) -> 0(*'(x, y))
*'(1(x), y) -> +'(0(*'(x, y)), y)
*'(j(x), y) -> -(0(*'(x, y)), y)
*'(*'(x, y), z) -> *'(x, *'(y, z))
*'(+'(x, y), z) -> +'(*'(x, z), *'(y, z))
*'(x, +'(y, z)) -> +'(*'(x, y), *'(x, z))

Types:
0 :: #:1:j -> #:1:j
# :: #:1:j
+' :: #:1:j -> #:1:j -> #:1:j
1 :: #:1:j -> #:1:j
j :: #:1:j -> #:1:j
opp :: #:1:j -> #:1:j
- :: #:1:j -> #:1:j -> #:1:j
*' :: #:1:j -> #:1:j -> #:1:j
hole_#:1:j1_2 :: #:1:j
gen_#:1:j2_2 :: Nat -> #:1:j


Lemmas:
+'(gen_#:1:j2_2(+(1, n4_2)), gen_#:1:j2_2(+(1, n4_2))) -> *3_2, rt in Omega(n4_2)
opp(gen_#:1:j2_2(+(1, n6450904_2))) -> *3_2, rt in Omega(n6450904_2)


Generator Equations:
gen_#:1:j2_2(0) <=> #
gen_#:1:j2_2(+(x, 1)) <=> 1(gen_#:1:j2_2(x))


The following defined symbols remain to be analysed:
*'
----------------------------------------

(15) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
*'(gen_#:1:j2_2(n6454045_2), gen_#:1:j2_2(0)) -> gen_#:1:j2_2(0), rt in Omega(1 + n6454045_2)

Induction Base:
*'(gen_#:1:j2_2(0), gen_#:1:j2_2(0)) ->_R^Omega(1)
#

Induction Step:
*'(gen_#:1:j2_2(+(n6454045_2, 1)), gen_#:1:j2_2(0)) ->_R^Omega(1)
+'(0(*'(gen_#:1:j2_2(n6454045_2), gen_#:1:j2_2(0))), gen_#:1:j2_2(0)) ->_IH
+'(0(gen_#:1:j2_2(0)), gen_#:1:j2_2(0)) ->_R^Omega(1)
+'(#, gen_#:1:j2_2(0)) ->_R^Omega(1)
gen_#:1:j2_2(0)

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

(16)
BOUNDS(1, INF)