Runti Compl Inner Rewri 22807 pair #381904662

details

property	value
status	complete
benchmark	overlap.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n077.star.cs.uiowa.edu
space	Frederiksen_Glenstrup

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.487604141 seconds
cpu usage	329.350886128
max memory	5.705183232E9

stage attributes

key	value
output-size	34489
starexec-result	WORST_CASE(Omega(n^1), O(n^2))

output

/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^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxRelTRS
(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 155 ms]
(2) CpxRelTRS
(3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) CompleteCoflocoProof [FINISHED, 578 ms]
    (12) BOUNDS(1, n^2)
(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxRelTRS
    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) typed CpxTrs
    (17) OrderProof [LOWER BOUND(ID), 0 ms]
    (18) typed CpxTrs
    (19) RewriteLemmaProof [LOWER BOUND(ID), 271 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 1 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
            (28) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   overlap(Cons(x, xs), ys) -> overlap[Ite][True][Ite](member(x, ys), Cons(x, xs), ys)
   overlap(Nil, ys) -> False
   member(x', Cons(x, xs)) -> member[Ite][True][Ite](!EQ(x, x'), x', Cons(x, xs))
   member(x, Nil) -> False
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   goal(xs, ys) -> overlap(xs, ys)

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

   !EQ(S(x), S(y)) -> !EQ(x, y)
   !EQ(0, S(y)) -> False
   !EQ(S(x), 0) -> False
   !EQ(0, 0) -> True
   overlap[Ite][True][Ite](False, Cons(x, xs), ys) -> overlap(xs, ys)
   member[Ite][True][Ite](False, x', Cons(x, xs)) -> member(x', xs)
   overlap[Ite][True][Ite](True, xs, ys) -> True
   member[Ite][True][Ite](True, x, xs) -> True

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

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

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


The TRS R consists of the following rules:

   overlap(Cons(x, xs), ys) -> overlap[Ite][True][Ite](member(x, ys), Cons(x, xs), ys)
   overlap(Nil, ys) -> False
   member(x', Cons(x, xs)) -> member[Ite][True][Ite](!EQ(x, x'), x', Cons(x, xs))
   member(x, Nil) -> False
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   goal(xs, ys) -> overlap(xs, ys)

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

   !EQ(S(x), S(y)) -> !EQ(x, y)
   !EQ(0, S(y)) -> False
   !EQ(S(x), 0) -> False
   !EQ(0, 0) -> True

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to Runti Compl Inner Rewri 22807