Logic Programming pair #487529113

details

property	value
status	complete
benchmark	mergesort.pl
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n147.star.cs.uiowa.edu
space	talp_apt

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	4.69260191917 seconds
cpu usage	14.575432748
max memory	1.57237248E9

stage attributes

key	value
output-size	101548
starexec-result	YES

output

/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files


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


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


Left Termination of the query pattern

mergesort(g,a)

w.r.t. the given Prolog program could successfully be proven:

(0) Prolog
(1) PrologToTRSTransformerProof [SOUND, 32 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 0 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES
    (17) QDP
        (18) QDPOrderProof [EQUIVALENT, 18 ms]
        (19) QDP
        (20) DependencyGraphProof [EQUIVALENT, 0 ms]
        (21) TRUE
    (22) QDP
        (23) UsableRulesProof [EQUIVALENT, 0 ms]
        (24) QDP
        (25) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (26) YES
    (27) QDP
        (28) QDPOrderProof [EQUIVALENT, 220 ms]
        (29) QDP
        (30) DependencyGraphProof [EQUIVALENT, 0 ms]
        (31) TRUE


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

(0)
Obligation:
Clauses:

mergesort([], []).
mergesort(.(X, []), .(X, [])).
mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))).
split([], [], []).
split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys).
merge([], Xs, Xs).
merge(Xs, [], Xs).
merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(le(X, Y), merge(Xs, .(Y, Ys), Zs)).
merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(gt(X, Y), merge(.(X, Xs), Ys, Zs)).
gt(s(X), s(Y)) :- gt(X, Y).
gt(s(X), 0).
le(s(X), s(Y)) :- le(X, Y).
le(0, s(Y)).
le(0, 0).


Query: mergesort(g,a)
----------------------------------------

(1) PrologToTRSTransformerProof (SOUND)
Transformed Prolog program to TRS.

{
    "root": 56,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(mergesort ([]) ([]))",
                null
            ],
            [
                "(mergesort (. X ([])) (. X ([])))",
                null
            ],
            [
                "(mergesort (. X (. Y Xs)) Ys)",
                "(',' (split (. X (. Y Xs)) X1s X2s) (',' (mergesort X1s Y1s) (',' (mergesort X2s Y2s) (merge Y1s Y2s Ys))))"
            ],
            [
                "(split ([]) ([]) ([]))",
                null
            ],

popout

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

job log

popout

actions all output return to Logic Programming