Logic Progr 19030 pair #381919871

details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	2.94847106934 seconds
cpu usage	8.345214345
max memory	4.76532736E8

stage attributes

key	value
output-size	80997
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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Left Termination of the query pattern

extend(g,a)

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

(0) Prolog
(1) PrologToIRSwTTransformerProof [SOUND, 39 ms]
(2) AND
    (3) IRSwT
        (4) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (5) TRUE
    (6) IRSwT
        (7) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (8) TRUE
    (9) IRSwT
        (10) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (11) IRSwT
        (12) IntTRSCompressionProof [EQUIVALENT, 22 ms]
        (13) IRSwT
        (14) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (15) IRSwT
        (16) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms]
        (17) IRSwT
        (18) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (19) IRSwT
        (20) TempFilterProof [SOUND, 1 ms]
        (21) IRSwT
        (22) IRSwTToQDPProof [SOUND, 0 ms]
        (23) QDP
        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (25) YES


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

(0)
Obligation:
Clauses:

extend(In, Out) :- ','(min(In, Min), ','(max(In, Max), range(Min, Max, Out))).
range(Low, High, []) :- >(Low, High).
range(Low, High, Result) :- ','(=<(Low, High), ','(range(+(Low, 1), High, RecursiveResult), ','(is(Temp, Low), =(Result, .(Temp, RecursiveResult))))).
min(.(X, []), X).
min(.(X, Xs), X) :- ','(min(Xs, Y), =<(X, Y)).
min(.(X, Xs), Y) :- ','(min(Xs, Y), >(X, Y)).
max(.(X, []), X).
max(.(X, Xs), X) :- ','(max(Xs, Y), >=(X, Y)).
max(.(X, Xs), Y) :- ','(max(Xs, Y), <(X, Y)).


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

(1) PrologToIRSwTTransformerProof (SOUND)
Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert

{
    "root": 4,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(extend In Out)",
                "(',' (min In Min) (',' (max In Max) (range Min Max Out)))"
            ],
            [
                "(range Low High ([]))",
                "(> Low High)"
            ],
            [
                "(range Low High Result)",
                "(',' (=< Low High) (',' (range (+ Low (1)) High RecursiveResult) (',' (is Temp Low) (= Result (. Temp RecursiveResult)))))"
            ],
            [
                "(min (. X ([])) X)",
                null
            ],
            [
                "(min (. X Xs) X)",
                "(',' (min Xs Y) (=< X Y))"
            ],
            [
                "(min (. X Xs) Y)",
                "(',' (min Xs Y) (> X Y))"
            ],
            [
                "(max (. X ([])) X)",
                null

popout

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

job log

popout

actions all output return to Logic Progr 19030