3.67/1.71 YES 3.67/1.72 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 3.67/1.72 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.67/1.72 3.67/1.72 3.67/1.72 Left Termination of the query pattern 3.67/1.72 3.67/1.72 map(g,a) 3.67/1.72 3.67/1.72 w.r.t. the given Prolog program could successfully be proven: 3.67/1.72 3.67/1.72 (0) Prolog 3.67/1.72 (1) PrologToPiTRSProof [SOUND, 0 ms] 3.67/1.72 (2) PiTRS 3.67/1.72 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 3.67/1.72 (4) PiDP 3.67/1.72 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.67/1.72 (6) PiDP 3.67/1.72 (7) UsableRulesProof [EQUIVALENT, 0 ms] 3.67/1.72 (8) PiDP 3.67/1.72 (9) PiDPToQDPProof [SOUND, 0 ms] 3.67/1.72 (10) QDP 3.67/1.72 (11) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.67/1.72 (12) YES 3.67/1.72 3.67/1.72 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (0) 3.67/1.72 Obligation: 3.67/1.72 Clauses: 3.67/1.72 3.67/1.72 p(X, Y). 3.67/1.72 map(.(X, Xs), .(Y, Ys)) :- ','(p(X, Y), map(Xs, Ys)). 3.67/1.72 map([], []). 3.67/1.72 3.67/1.72 3.67/1.72 Query: map(g,a) 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (1) PrologToPiTRSProof (SOUND) 3.67/1.72 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.67/1.72 3.67/1.72 map_in_2: (b,f) 3.67/1.72 3.67/1.72 Transforming Prolog into the following Term Rewriting System: 3.67/1.72 3.67/1.72 Pi-finite rewrite system: 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 map_in_ga(.(X, Xs), .(Y, Ys)) -> U1_ga(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 U1_ga(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_ga(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 map_in_ga([], []) -> map_out_ga([], []) 3.67/1.72 U2_ga(X, Xs, Y, Ys, map_out_ga(Xs, Ys)) -> map_out_ga(.(X, Xs), .(Y, Ys)) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 map_in_ga(x1, x2) = map_in_ga(x1) 3.67/1.72 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x2, x5) 3.67/1.72 3.67/1.72 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) 3.67/1.72 3.67/1.72 [] = [] 3.67/1.72 3.67/1.72 map_out_ga(x1, x2) = map_out_ga(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 3.67/1.72 3.67/1.72 3.67/1.72 3.67/1.72 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 3.67/1.72 3.67/1.72 3.67/1.72 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (2) 3.67/1.72 Obligation: 3.67/1.72 Pi-finite rewrite system: 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 map_in_ga(.(X, Xs), .(Y, Ys)) -> U1_ga(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 U1_ga(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_ga(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 map_in_ga([], []) -> map_out_ga([], []) 3.67/1.72 U2_ga(X, Xs, Y, Ys, map_out_ga(Xs, Ys)) -> map_out_ga(.(X, Xs), .(Y, Ys)) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 map_in_ga(x1, x2) = map_in_ga(x1) 3.67/1.72 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x2, x5) 3.67/1.72 3.67/1.72 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) 3.67/1.72 3.67/1.72 [] = [] 3.67/1.72 3.67/1.72 map_out_ga(x1, x2) = map_out_ga(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 3.67/1.72 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (3) DependencyPairsProof (EQUIVALENT) 3.67/1.72 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 3.67/1.72 Pi DP problem: 3.67/1.72 The TRS P consists of the following rules: 3.67/1.72 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> U1_GA(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> P_IN_AA(X, Y) 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_GA(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> MAP_IN_GA(Xs, Ys) 3.67/1.72 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 map_in_ga(.(X, Xs), .(Y, Ys)) -> U1_ga(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 U1_ga(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_ga(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 map_in_ga([], []) -> map_out_ga([], []) 3.67/1.72 U2_ga(X, Xs, Y, Ys, map_out_ga(Xs, Ys)) -> map_out_ga(.(X, Xs), .(Y, Ys)) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 map_in_ga(x1, x2) = map_in_ga(x1) 3.67/1.72 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x2, x5) 3.67/1.72 3.67/1.72 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) 3.67/1.72 3.67/1.72 [] = [] 3.67/1.72 3.67/1.72 map_out_ga(x1, x2) = map_out_ga(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 MAP_IN_GA(x1, x2) = MAP_IN_GA(x1) 3.67/1.72 3.67/1.72 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x2, x5) 3.67/1.72 3.67/1.72 P_IN_AA(x1, x2) = P_IN_AA 3.67/1.72 3.67/1.72 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x5) 3.67/1.72 3.67/1.72 3.67/1.72 We have to consider all (P,R,Pi)-chains 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (4) 3.67/1.72 Obligation: 3.67/1.72 Pi DP problem: 3.67/1.72 The TRS P consists of the following rules: 3.67/1.72 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> U1_GA(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> P_IN_AA(X, Y) 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_GA(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> MAP_IN_GA(Xs, Ys) 3.67/1.72 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 map_in_ga(.(X, Xs), .(Y, Ys)) -> U1_ga(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 U1_ga(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_ga(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 map_in_ga([], []) -> map_out_ga([], []) 3.67/1.72 U2_ga(X, Xs, Y, Ys, map_out_ga(Xs, Ys)) -> map_out_ga(.(X, Xs), .(Y, Ys)) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 map_in_ga(x1, x2) = map_in_ga(x1) 3.67/1.72 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x2, x5) 3.67/1.72 3.67/1.72 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) 3.67/1.72 3.67/1.72 [] = [] 3.67/1.72 3.67/1.72 map_out_ga(x1, x2) = map_out_ga(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 MAP_IN_GA(x1, x2) = MAP_IN_GA(x1) 3.67/1.72 3.67/1.72 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x2, x5) 3.67/1.72 3.67/1.72 P_IN_AA(x1, x2) = P_IN_AA 3.67/1.72 3.67/1.72 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x5) 3.67/1.72 3.67/1.72 3.67/1.72 We have to consider all (P,R,Pi)-chains 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (5) DependencyGraphProof (EQUIVALENT) 3.67/1.72 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (6) 3.67/1.72 Obligation: 3.67/1.72 Pi DP problem: 3.67/1.72 The TRS P consists of the following rules: 3.67/1.72 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> MAP_IN_GA(Xs, Ys) 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> U1_GA(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 map_in_ga(.(X, Xs), .(Y, Ys)) -> U1_ga(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 U1_ga(X, Xs, Y, Ys, p_out_aa(X, Y)) -> U2_ga(X, Xs, Y, Ys, map_in_ga(Xs, Ys)) 3.67/1.72 map_in_ga([], []) -> map_out_ga([], []) 3.67/1.72 U2_ga(X, Xs, Y, Ys, map_out_ga(Xs, Ys)) -> map_out_ga(.(X, Xs), .(Y, Ys)) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 map_in_ga(x1, x2) = map_in_ga(x1) 3.67/1.72 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x2, x5) 3.67/1.72 3.67/1.72 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) 3.67/1.72 3.67/1.72 [] = [] 3.67/1.72 3.67/1.72 map_out_ga(x1, x2) = map_out_ga(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 MAP_IN_GA(x1, x2) = MAP_IN_GA(x1) 3.67/1.72 3.67/1.72 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x2, x5) 3.67/1.72 3.67/1.72 3.67/1.72 We have to consider all (P,R,Pi)-chains 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (7) UsableRulesProof (EQUIVALENT) 3.67/1.72 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (8) 3.67/1.72 Obligation: 3.67/1.72 Pi DP problem: 3.67/1.72 The TRS P consists of the following rules: 3.67/1.72 3.67/1.72 U1_GA(X, Xs, Y, Ys, p_out_aa(X, Y)) -> MAP_IN_GA(Xs, Ys) 3.67/1.72 MAP_IN_GA(.(X, Xs), .(Y, Ys)) -> U1_GA(X, Xs, Y, Ys, p_in_aa(X, Y)) 3.67/1.72 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 p_in_aa(X, Y) -> p_out_aa(X, Y) 3.67/1.72 3.67/1.72 The argument filtering Pi contains the following mapping: 3.67/1.72 .(x1, x2) = .(x2) 3.67/1.72 3.67/1.72 p_in_aa(x1, x2) = p_in_aa 3.67/1.72 3.67/1.72 p_out_aa(x1, x2) = p_out_aa 3.67/1.72 3.67/1.72 MAP_IN_GA(x1, x2) = MAP_IN_GA(x1) 3.67/1.72 3.67/1.72 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x2, x5) 3.67/1.72 3.67/1.72 3.67/1.72 We have to consider all (P,R,Pi)-chains 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (9) PiDPToQDPProof (SOUND) 3.67/1.72 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (10) 3.67/1.72 Obligation: 3.67/1.72 Q DP problem: 3.67/1.72 The TRS P consists of the following rules: 3.67/1.72 3.67/1.72 U1_GA(Xs, p_out_aa) -> MAP_IN_GA(Xs) 3.67/1.72 MAP_IN_GA(.(Xs)) -> U1_GA(Xs, p_in_aa) 3.67/1.72 3.67/1.72 The TRS R consists of the following rules: 3.67/1.72 3.67/1.72 p_in_aa -> p_out_aa 3.67/1.72 3.67/1.72 The set Q consists of the following terms: 3.67/1.72 3.67/1.72 p_in_aa 3.67/1.72 3.67/1.72 We have to consider all (P,Q,R)-chains. 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (11) QDPSizeChangeProof (EQUIVALENT) 3.67/1.72 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 3.67/1.72 3.67/1.72 From the DPs we obtained the following set of size-change graphs: 3.67/1.72 *MAP_IN_GA(.(Xs)) -> U1_GA(Xs, p_in_aa) 3.67/1.72 The graph contains the following edges 1 > 1 3.67/1.72 3.67/1.72 3.67/1.72 *U1_GA(Xs, p_out_aa) -> MAP_IN_GA(Xs) 3.67/1.72 The graph contains the following edges 1 >= 1 3.67/1.72 3.67/1.72 3.67/1.72 ---------------------------------------- 3.67/1.72 3.67/1.72 (12) 3.67/1.72 YES 3.67/1.75 EOF