TRS Conditional pair #487562964

details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	2.12616896629 seconds
cpu usage	5.341532591
max memory	3.43158784E8

stage attributes

key	value
output-size	20902
starexec-result	YES

output

/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


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


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


Quasi decreasingness of the given CTRS could be proven:

(0) CTRS
(1) CTRSToQTRSProof [SOUND, 0 ms]
(2) QTRS
(3) Overlay + Local Confluence [EQUIVALENT, 0 ms]
(4) QTRS
(5) DependencyPairsProof [EQUIVALENT, 15 ms]
(6) QDP
(7) DependencyGraphProof [EQUIVALENT, 0 ms]
(8) AND
    (9) QDP
        (10) UsableRulesProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) QReductionProof [EQUIVALENT, 0 ms]
        (13) QDP
        (14) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (15) YES
    (16) QDP
        (17) UsableRulesProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) QReductionProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (22) YES
    (23) QDP
        (24) UsableRulesProof [EQUIVALENT, 0 ms]
        (25) QDP
        (26) QReductionProof [EQUIVALENT, 0 ms]
        (27) QDP
        (28) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (29) YES
    (30) QDP
        (31) UsableRulesProof [EQUIVALENT, 0 ms]
        (32) QDP
        (33) QReductionProof [EQUIVALENT, 0 ms]
        (34) QDP
        (35) QDPOrderProof [EQUIVALENT, 13 ms]
        (36) QDP
        (37) PisEmptyProof [EQUIVALENT, 0 ms]
        (38) YES


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

(0)
Obligation:
Conditional term rewrite system:
The TRS R consists of the following rules:

   le(0, x) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, x) -> x
   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
   split(x, nil) -> pair(nil, nil)
   qsort(nil) -> nil

The conditional TRS C consists of the following conditional rules:

   split(x, cons(y, ys)) -> pair(xs, cons(y, zs)) <= split(x, ys) -> pairs(xs, zs), le(x, y) -> true
   split(x, cons(y, ys)) -> pair(cons(y, xs), zs) <= split(x, ys) -> pairs(xs, zs), le(x, y) -> false
   qsort(cons(x, xs)) -> app(qsort(ys), cons(x, qsort(zs))) <= split(x, xs) -> pair(ys, zs)


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

(1) CTRSToQTRSProof (SOUND)
The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   split(x, cons(y, ys)) -> U1(split(x, ys), x, y)
   U1(pairs(xs, zs), x, y) -> U2(le(x, y), y, xs, zs)
   U2(false, y, xs, zs) -> pair(cons(y, xs), zs)
   U2(true, y, xs, zs) -> pair(xs, cons(y, zs))
   qsort(cons(x, xs)) -> U3(split(x, xs), x)
   U3(pair(ys, zs), x) -> app(qsort(ys), cons(x, qsort(zs)))
   le(0, x) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, x) -> x
   app(cons(x, xs), ys) -> cons(x, app(xs, ys))
   split(x, nil) -> pair(nil, nil)
   qsort(nil) -> nil

popout

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

job log

popout

actions all output return to TRS Conditional