Logic Progr 19030 pair #381920000

details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	1.98219490051 seconds
cpu usage	4.832603335
max memory	4.2012672E8

stage attributes

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

ordered(g)

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

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


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

(0)
Obligation:
Clauses:

ordered([]).
ordered(.(X, [])).
ordered(.(X, .(Y, Xs))) :- ','(le(X, Y), ordered(.(Y, Xs))).
le(s(X), s(Y)) :- le(X, Y).
le(0, s(0)).
le(0, 0).


Query: ordered(g)
----------------------------------------

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

ordered_in_1: (b)

le_in_2: (b,b)

Transforming Prolog into the following Term Rewriting System:

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

   ordered_in_g([]) -> ordered_out_g([])
   ordered_in_g(.(X, [])) -> ordered_out_g(.(X, []))
   ordered_in_g(.(X, .(Y, Xs))) -> U1_g(X, Y, Xs, le_in_gg(X, Y))
   le_in_gg(s(X), s(Y)) -> U3_gg(X, Y, le_in_gg(X, Y))
   le_in_gg(0, s(0)) -> le_out_gg(0, s(0))
   le_in_gg(0, 0) -> le_out_gg(0, 0)
   U3_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
   U1_g(X, Y, Xs, le_out_gg(X, Y)) -> U2_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
   U2_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs)))

The argument filtering Pi contains the following mapping:
ordered_in_g(x1)  =  ordered_in_g(x1)

[]  =  []

ordered_out_g(x1)  =  ordered_out_g

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

U1_g(x1, x2, x3, x4)  =  U1_g(x2, x3, x4)

le_in_gg(x1, x2)  =  le_in_gg(x1, x2)

s(x1)  =  s(x1)

U3_gg(x1, x2, x3)  =  U3_gg(x3)

0  =  0

popout

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

job log

popout

actions all output return to Logic Progr 19030