Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Logic Progr 19030 pair #381919658
details
property
value
status
complete
benchmark
tautology.pl
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n034.star.cs.uiowa.edu
space
prolog_mixed
run statistics
property
value
solver
AProVE
configuration
standard
runtime (wallclock)
18.7050018311 seconds
cpu usage
69.689146652
max memory
7.339945984E9
stage attributes
key
value
output-size
86580
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern tautology(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 36 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 21 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, 34 ms] (18) QDP (19) QDPQMonotonicMRRProof [EQUIVALENT, 332 ms] (20) QDP (21) QDPQMonotonicMRRProof [EQUIVALENT, 319 ms] (22) QDP (23) QDPQMonotonicMRRProof [EQUIVALENT, 167 ms] (24) QDP (25) QDPQMonotonicMRRProof [EQUIVALENT, 108 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) TRUE ---------------------------------------- (0) Obligation: Clauses: tautology(F) :- reduce(sequent([], .(F, [])), sequent([], [])). reduce(sequent(.(if(A, B), Fs), Gs), NF) :- reduce(sequent(.(+(-(B), A), Fs), Gs), NF). reduce(sequent(.(iff(A, B), Fs), Gs), NF) :- reduce(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF). reduce(sequent(.(*(F1, F2), Fs), Gs), NF) :- reduce(sequent(.(F1, .(F2, Fs)), Gs), NF). reduce(sequent(.(+(F1, F2), Fs), Gs), NF) :- ','(reduce(sequent(.(F1, Fs), Gs), NF), reduce(sequent(.(F2, Fs), Gs), NF)). reduce(sequent(.(-(F1), Fs), Gs), NF) :- reduce(sequent(Fs, .(F1, Gs)), NF). reduce(sequent(Fs, .(if(A, B), Gs)), NF) :- reduce(sequent(Fs, .(+(-(B), A), Gs)), NF). reduce(sequent(Fs, .(iff(A, B), Gs)), NF) :- reduce(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF). reduce(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) :- reduce(sequent(Fs, Gs), sequent(.(p(V), Left), Right)). reduce(sequent(Fs, .(+(G1, G2), Gs)), NF) :- reduce(sequent(Fs, .(G1, .(G2, Gs))), NF). reduce(sequent(Fs, .(*(G1, G2), Gs)), NF) :- ','(reduce(sequent(Fs, .(G1, Gs)), NF), reduce(sequent(Fs, .(G2, Gs)), NF)). reduce(sequent(Fs, .(-(G1), Gs)), NF) :- reduce(sequent(.(G1, Fs), Gs), NF). reduce(sequent([], .(p(V), Gs)), sequent(Left, Right)) :- reduce(sequent([], Gs), sequent(Left, .(p(V), Right))). reduce(sequent([], []), sequent(F1, F2)) :- intersect(F1, F2). intersect(.(X, X1), .(X, X2)). intersect(Xs, .(X3, Ys)) :- intersect(Xs, Ys). intersect(.(X4, Xs), Ys) :- intersect(Xs, Ys). yes1 :- tautology(+(-(p(1)), p(1))). yes2 :- tautology(*(+(-(p(1)), p(1)), +(p(1), -(p(1))))). yes3 :- tautology(*(+(-(-(-(p(1)))), p(1)), +(-(-(p(1))), -(p(1))))). yes4 :- tautology(-(-(','(p(1), *), p(1)))). no1 :- tautology(-(','(p(1), *), p(1))). no2 :- tautology(+(-(+(p(1), -(p(1)))), p(2))). no3 :- tautology(*(+(-(+(-(p(1)), +(-(p(2)), p(3)))), +(-(+(p(1), p(2))), p(3))), +(-(p(1)), +(+(-(p(2)), p(3)), -(+(-(+(p(1), p(2))), p(3))))))). no4 :- tautology(+(-(+(*(p(1), *(p(2), p(3))), -(','(-(p(1)), *), -(','(p(2), *), p(3))))), *(+(-(p(1)), *(+(-(p(2)), p(3)), +(p(2), -(p(3))))), +(p(1), -(*(+(-(p(2)), p(3)), +(p(2), -(p(3))))))))). Query: tautology(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: tautology_in_1: (b) reduce_in_2: (b,b) intersect_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF))
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Logic Progr 19030