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


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


WORST_CASE(?, O(1))
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxTRS
(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(2) CdtProblem
(3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CdtProblem
(5) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) BOUNDS(1, 1)


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

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


The TRS R consists of the following rules:

   f(x, y, z) -> g(<=(x, y), x, y, z)
   g(true, x, y, z) -> z
   g(false, x, y, z) -> f(f(p(x), y, z), f(p(y), z, x), f(p(z), x, y))
   p(0) -> 0
   p(s(x)) -> x

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

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

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   f(z0, z1, z2) -> g(<=(z0, z1), z0, z1, z2)
   g(true, z0, z1, z2) -> z2
   g(false, z0, z1, z2) -> f(f(p(z0), z1, z2), f(p(z1), z2, z0), f(p(z2), z0, z1))
   p(0) -> 0
   p(s(z0)) -> z0
Tuples:
   F(z0, z1, z2) -> c(G(<=(z0, z1), z0, z1, z2))
   G(true, z0, z1, z2) -> c1
   G(false, z0, z1, z2) -> c2(F(f(p(z0), z1, z2), f(p(z1), z2, z0), f(p(z2), z0, z1)), F(p(z0), z1, z2), P(z0), F(p(z1), z2, z0), P(z1), F(p(z2), z0, z1), P(z2))
   P(0) -> c3
   P(s(z0)) -> c4
S tuples:
   F(z0, z1, z2) -> c(G(<=(z0, z1), z0, z1, z2))
   G(true, z0, z1, z2) -> c1
   G(false, z0, z1, z2) -> c2(F(f(p(z0), z1, z2), f(p(z1), z2, z0), f(p(z2), z0, z1)), F(p(z0), z1, z2), P(z0), F(p(z1), z2, z0), P(z1), F(p(z2), z0, z1), P(z2))
   P(0) -> c3
   P(s(z0)) -> c4
K tuples:none
Defined Rule Symbols:   f_3, g_4, p_1

Defined Pair Symbols:   F_3, G_4, P_1

Compound Symbols:   c_1, c1, c2_7, c3, c4


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

(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 5 trailing nodes:
   F(z0, z1, z2) -> c(G(<=(z0, z1), z0, z1, z2))
   G(false, z0, z1, z2) -> c2(F(f(p(z0), z1, z2), f(p(z1), z2, z0), f(p(z2), z0, z1)), F(p(z0), z1, z2), P(z0), F(p(z1), z2, z0), P(z1), F(p(z2), z0, z1), P(z2))
   P(s(z0)) -> c4
   P(0) -> c3
   G(true, z0, z1, z2) -> c1

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

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   f(z0, z1, z2) -> g(<=(z0, z1), z0, z1, z2)
   g(true, z0, z1, z2) -> z2
   g(false, z0, z1, z2) -> f(f(p(z0), z1, z2), f(p(z1), z2, z0), f(p(z2), z0, z1))
   p(0) -> 0
   p(s(z0)) -> z0
Tuples:none
S tuples:none
K tuples:none
Defined Rule Symbols:   f_3, g_4, p_1

Defined Pair Symbols:none

Compound Symbols:none


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

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

(6)
BOUNDS(1, 1)