Logic Programming pair #487529365

details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	1.78057694435 seconds
cpu usage	4.264312129
max memory	2.92036608E8

stage attributes

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

inorder(g,a)

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

(0) Prolog
(1) PrologToPiTRSProof [SOUND, 0 ms]
(2) PiTRS
(3) DependencyPairsProof [EQUIVALENT, 0 ms]
(4) PiDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) PiDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) PiDP
        (10) PiDPToQDPProof [SOUND, 0 ms]
        (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) PiDP
        (15) PiDPToQDPProof [SOUND, 0 ms]
        (16) QDP
        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (18) YES


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

(0)
Obligation:
Clauses:

inorder(nil, []).
inorder(tree(L, V, R), I) :- ','(inorder(L, LI), ','(inorder(R, RI), append(LI, .(V, RI), I))).
append([], X, X).
append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs).


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

(1) PrologToPiTRSProof (SOUND)
We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:

inorder_in_2: (b,f)

append_in_3: (b,b,f)

Transforming Prolog into the following Term Rewriting System:

Pi-finite rewrite system:
The TRS R consists of the following rules:

   inorder_in_ga(nil, []) -> inorder_out_ga(nil, [])
   inorder_in_ga(tree(L, V, R), I) -> U1_ga(L, V, R, I, inorder_in_ga(L, LI))
   U1_ga(L, V, R, I, inorder_out_ga(L, LI)) -> U2_ga(L, V, R, I, LI, inorder_in_ga(R, RI))
   U2_ga(L, V, R, I, LI, inorder_out_ga(R, RI)) -> U3_ga(L, V, R, I, append_in_gga(LI, .(V, RI), I))
   append_in_gga([], X, X) -> append_out_gga([], X, X)
   append_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U4_gga(X, Xs, Ys, Zs, append_in_gga(Xs, Ys, Zs))
   U4_gga(X, Xs, Ys, Zs, append_out_gga(Xs, Ys, Zs)) -> append_out_gga(.(X, Xs), Ys, .(X, Zs))
   U3_ga(L, V, R, I, append_out_gga(LI, .(V, RI), I)) -> inorder_out_ga(tree(L, V, R), I)

The argument filtering Pi contains the following mapping:
inorder_in_ga(x1, x2)  =  inorder_in_ga(x1)

nil  =  nil

inorder_out_ga(x1, x2)  =  inorder_out_ga(x1, x2)

tree(x1, x2, x3)  =  tree(x1, x2, x3)

U1_ga(x1, x2, x3, x4, x5)  =  U1_ga(x1, x2, x3, x5)

U2_ga(x1, x2, x3, x4, x5, x6)  =  U2_ga(x1, x2, x3, x5, x6)

U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x1, x2, x3, x5)

append_in_gga(x1, x2, x3)  =  append_in_gga(x1, x2)

[]  =  []

append_out_gga(x1, x2, x3)  =  append_out_gga(x1, x2, x3)

.(x1, x2)  =  .(x1, x2)

U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)

popout

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

job log

popout

actions all output return to Logic Programming