/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), O(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, n^1).

(0) CpxTRS
(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
    (4) CpxTRS
    (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
    (6) CpxTRS
    (7) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms]
    (8) BOUNDS(1, n^1)
(9) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(10) CpxTRS
    (11) SlicingProof [LOWER BOUND(ID), 0 ms]
    (12) CpxTRS
    (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) typed CpxTrs
    (15) OrderProof [LOWER BOUND(ID), 0 ms]
    (16) typed CpxTrs
    (17) RewriteLemmaProof [LOWER BOUND(ID), 259 ms]
    (18) BEST
        (19) proven lower bound
            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
            (21) BOUNDS(n^1, INF)
        (22) typed CpxTrs


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

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


The TRS R consists of the following rules:

   rev(nil) -> nil
   rev(rev(x)) -> x
   rev(++(x, y)) -> ++(rev(y), rev(x))
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(x, ++(y, z)) -> ++(++(x, y), z)
   make(x) -> .(x, nil)

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

(1) DependencyGraphProof (UPPER BOUND(ID))
The following rules are not reachable from basic terms in the dependency graph and can be removed:

rev(rev(x)) -> x
rev(++(x, y)) -> ++(rev(y), rev(x))

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

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


The TRS R consists of the following rules:

   rev(nil) -> nil
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(x, ++(y, z)) -> ++(++(x, y), z)
   make(x) -> .(x, nil)

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

(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
The TRS does not nest defined symbols.
Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
++(x, ++(y, z)) -> ++(++(x, y), z)

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

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


The TRS R consists of the following rules:

   rev(nil) -> nil
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   make(x) -> .(x, nil)

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

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

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


The TRS R consists of the following rules:

   rev(nil) -> nil
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   make(x) -> .(x, nil)

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

(7) CpxTrsMatchBoundsTAProof (FINISHED)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 1. 

The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
final states : [1, 2, 3]
transitions: 
nil0() -> 0
.0(0, 0) -> 0
rev0(0) -> 1
++0(0, 0) -> 2
make0(0) -> 3
nil1() -> 1
++1(0, 0) -> 4
.1(0, 4) -> 2
nil1() -> 5
.1(0, 5) -> 3
.1(0, 4) -> 4
0 -> 2
0 -> 4

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

(8)
BOUNDS(1, n^1)

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

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

(10)
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:

   rev(nil) -> nil
   rev(rev(x)) -> x
   rev(++(x, y)) -> ++(rev(y), rev(x))
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(x, y), z) -> .(x, ++(y, z))
   ++(x, ++(y, z)) -> ++(++(x, y), z)
   make(x) -> .(x, nil)

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

(11) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
./0
make/0

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

(12)
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:

   rev(nil) -> nil
   rev(rev(x)) -> x
   rev(++(x, y)) -> ++(rev(y), rev(x))
   ++(nil, y) -> y
   ++(x, nil) -> x
   ++(.(y), z) -> .(++(y, z))
   ++(x, ++(y, z)) -> ++(++(x, y), z)
   make -> .(nil)

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

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

(14)
Obligation:
TRS:
Rules:
rev(nil) -> nil
rev(rev(x)) -> x
rev(++(x, y)) -> ++(rev(y), rev(x))
++(nil, y) -> y
++(x, nil) -> x
++(.(y), z) -> .(++(y, z))
++(x, ++(y, z)) -> ++(++(x, y), z)
make -> .(nil)

Types:
rev :: nil:. -> nil:.
nil :: nil:.
++ :: nil:. -> nil:. -> nil:.
. :: nil:. -> nil:.
make :: nil:.
hole_nil:.1_0 :: nil:.
gen_nil:.2_0 :: Nat -> nil:.

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

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

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

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

(16)
Obligation:
TRS:
Rules:
rev(nil) -> nil
rev(rev(x)) -> x
rev(++(x, y)) -> ++(rev(y), rev(x))
++(nil, y) -> y
++(x, nil) -> x
++(.(y), z) -> .(++(y, z))
++(x, ++(y, z)) -> ++(++(x, y), z)
make -> .(nil)

Types:
rev :: nil:. -> nil:.
nil :: nil:.
++ :: nil:. -> nil:. -> nil:.
. :: nil:. -> nil:.
make :: nil:.
hole_nil:.1_0 :: nil:.
gen_nil:.2_0 :: Nat -> nil:.


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


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

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

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

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

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

Induction Step:
++(gen_nil:.2_0(+(n4_0, 1)), gen_nil:.2_0(b)) ->_R^Omega(1)
.(++(gen_nil:.2_0(n4_0), gen_nil:.2_0(b))) ->_IH
.(gen_nil:.2_0(+(b, c5_0)))

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

(18)
Complex Obligation (BEST)

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

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

TRS:
Rules:
rev(nil) -> nil
rev(rev(x)) -> x
rev(++(x, y)) -> ++(rev(y), rev(x))
++(nil, y) -> y
++(x, nil) -> x
++(.(y), z) -> .(++(y, z))
++(x, ++(y, z)) -> ++(++(x, y), z)
make -> .(nil)

Types:
rev :: nil:. -> nil:.
nil :: nil:.
++ :: nil:. -> nil:. -> nil:.
. :: nil:. -> nil:.
make :: nil:.
hole_nil:.1_0 :: nil:.
gen_nil:.2_0 :: Nat -> nil:.


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


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

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

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

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
TRS:
Rules:
rev(nil) -> nil
rev(rev(x)) -> x
rev(++(x, y)) -> ++(rev(y), rev(x))
++(nil, y) -> y
++(x, nil) -> x
++(.(y), z) -> .(++(y, z))
++(x, ++(y, z)) -> ++(++(x, y), z)
make -> .(nil)

Types:
rev :: nil:. -> nil:.
nil :: nil:.
++ :: nil:. -> nil:. -> nil:.
. :: nil:. -> nil:.
make :: nil:.
hole_nil:.1_0 :: nil:.
gen_nil:.2_0 :: Nat -> nil:.


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


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


The following defined symbols remain to be analysed:
rev