Logic Progr 19030 pair #381920197

details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	2.55219101906 seconds
cpu usage	6.60374416
max memory	4.08715264E8

stage attributes

key	value
output-size	70942
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

goal(g,a,a)

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

(0) Prolog
(1) PrologToIRSwTTransformerProof [SOUND, 37 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) TRUE
    (12) IRSwT
        (13) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (14) IRSwT
        (15) IntTRSCompressionProof [EQUIVALENT, 5 ms]
        (16) IRSwT
        (17) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (18) IRSwT
        (19) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms]
        (20) IRSwT
        (21) TempFilterProof [SOUND, 3 ms]
        (22) IRSwT
        (23) IRSwTToQDPProof [SOUND, 1 ms]
        (24) QDP
        (25) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (26) YES


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

(0)
Obligation:
Clauses:

goal(A, B, C) :- ','(s2l(A, D), applast(D, B, C)).
applast(L, X, Last) :- ','(app(L, .(X, []), LX), last(Last, LX)).
last(X, .(X, [])) :- !.
last(X, Y) :- ','(tail(Y, T), last(X, T)).
app([], Y, Z) :- ','(!, eq(Y, Z)).
app(X, Y, .(H, Z)) :- ','(head(X, H), ','(tail(X, T), app(T, Y, Z))).
s2l(0, L) :- ','(!, eq(L, [])).
s2l(X, .(X1, Xs)) :- ','(p(X, P), s2l(P, Xs)).
head([], X2).
head(.(X, X3), X).
tail([], []).
tail(.(X4, Xs), Xs).
p(0, 0).
p(s(X), X).
eq(X, X).


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

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

{
    "root": 1,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(goal A B C)",
                "(',' (s2l A D) (applast D B C))"
            ],
            [
                "(applast L X Last)",
                "(',' (app L (. X ([])) LX) (last Last LX))"
            ],
            [
                "(last X (. X ([])))",
                "(!)"
            ],
            [
                "(last X Y)",
                "(',' (tail Y T) (last X T))"
            ],
            [
                "(app ([]) Y Z)",
                "(',' (!) (eq Y Z))"
            ],

popout

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

job log

popout

actions all output return to Logic Progr 19030