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