4.00/1.88 YES 4.00/1.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.00/1.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.00/1.89 4.00/1.89 4.00/1.89 Left Termination of the query pattern 4.00/1.89 4.00/1.89 perm(g,a) 4.00/1.89 4.00/1.89 w.r.t. the given Prolog program could successfully be proven: 4.00/1.89 4.00/1.89 (0) Prolog 4.00/1.89 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.00/1.89 (2) PiTRS 4.00/1.89 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.00/1.89 (4) PiDP 4.00/1.89 (5) DependencyGraphProof [EQUIVALENT, 4 ms] 4.00/1.89 (6) AND 4.00/1.89 (7) PiDP 4.00/1.89 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.00/1.89 (9) PiDP 4.00/1.89 (10) PiDPToQDPProof [SOUND, 0 ms] 4.00/1.89 (11) QDP 4.00/1.89 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.00/1.89 (13) YES 4.00/1.89 (14) PiDP 4.00/1.89 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.00/1.89 (16) PiDP 4.00/1.89 (17) PiDPToQDPProof [SOUND, 0 ms] 4.00/1.89 (18) QDP 4.00/1.89 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.00/1.89 (20) YES 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (0) 4.00/1.89 Obligation: 4.00/1.89 Clauses: 4.00/1.89 4.00/1.89 perm([], []). 4.00/1.89 perm(.(X, L), Z) :- ','(perm(L, Y), insert(X, Y, Z)). 4.00/1.89 insert(X, [], .(X, [])). 4.00/1.89 insert(X, L, .(X, L)). 4.00/1.89 insert(X, .(H, L1), .(H, L2)) :- insert(X, L1, L2). 4.00/1.89 4.00/1.89 4.00/1.89 Query: perm(g,a) 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (1) PrologToPiTRSProof (SOUND) 4.00/1.89 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.00/1.89 4.00/1.89 perm_in_2: (b,f) 4.00/1.89 4.00/1.89 insert_in_3: (b,b,f) 4.00/1.89 4.00/1.89 Transforming Prolog into the following Term Rewriting System: 4.00/1.89 4.00/1.89 Pi-finite rewrite system: 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (2) 4.00/1.89 Obligation: 4.00/1.89 Pi-finite rewrite system: 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (3) DependencyPairsProof (EQUIVALENT) 4.00/1.89 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> U1_GA(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> PERM_IN_GA(L, Y) 4.00/1.89 U1_GA(X, L, Z, perm_out_ga(L, Y)) -> U2_GA(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 U1_GA(X, L, Z, perm_out_ga(L, Y)) -> INSERT_IN_GGA(X, Y, Z) 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> U3_GGA(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> INSERT_IN_GGA(X, L1, L2) 4.00/1.89 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.00/1.89 4.00/1.89 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.00/1.89 4.00/1.89 U2_GA(x1, x2, x3, x4) = U2_GA(x4) 4.00/1.89 4.00/1.89 INSERT_IN_GGA(x1, x2, x3) = INSERT_IN_GGA(x1, x2) 4.00/1.89 4.00/1.89 U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x2, x5) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (4) 4.00/1.89 Obligation: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> U1_GA(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> PERM_IN_GA(L, Y) 4.00/1.89 U1_GA(X, L, Z, perm_out_ga(L, Y)) -> U2_GA(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 U1_GA(X, L, Z, perm_out_ga(L, Y)) -> INSERT_IN_GGA(X, Y, Z) 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> U3_GGA(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> INSERT_IN_GGA(X, L1, L2) 4.00/1.89 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.00/1.89 4.00/1.89 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 4.00/1.89 4.00/1.89 U2_GA(x1, x2, x3, x4) = U2_GA(x4) 4.00/1.89 4.00/1.89 INSERT_IN_GGA(x1, x2, x3) = INSERT_IN_GGA(x1, x2) 4.00/1.89 4.00/1.89 U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x2, x5) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (5) DependencyGraphProof (EQUIVALENT) 4.00/1.89 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (6) 4.00/1.89 Complex Obligation (AND) 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (7) 4.00/1.89 Obligation: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> INSERT_IN_GGA(X, L1, L2) 4.00/1.89 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 INSERT_IN_GGA(x1, x2, x3) = INSERT_IN_GGA(x1, x2) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (8) UsableRulesProof (EQUIVALENT) 4.00/1.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (9) 4.00/1.89 Obligation: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 INSERT_IN_GGA(X, .(H, L1), .(H, L2)) -> INSERT_IN_GGA(X, L1, L2) 4.00/1.89 4.00/1.89 R is empty. 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 INSERT_IN_GGA(x1, x2, x3) = INSERT_IN_GGA(x1, x2) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (10) PiDPToQDPProof (SOUND) 4.00/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (11) 4.00/1.89 Obligation: 4.00/1.89 Q DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 INSERT_IN_GGA(X, .(H, L1)) -> INSERT_IN_GGA(X, L1) 4.00/1.89 4.00/1.89 R is empty. 4.00/1.89 Q is empty. 4.00/1.89 We have to consider all (P,Q,R)-chains. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (12) QDPSizeChangeProof (EQUIVALENT) 4.00/1.89 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. 4.00/1.89 4.00/1.89 From the DPs we obtained the following set of size-change graphs: 4.00/1.89 *INSERT_IN_GGA(X, .(H, L1)) -> INSERT_IN_GGA(X, L1) 4.00/1.89 The graph contains the following edges 1 >= 1, 2 > 2 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (13) 4.00/1.89 YES 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (14) 4.00/1.89 Obligation: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> PERM_IN_GA(L, Y) 4.00/1.89 4.00/1.89 The TRS R consists of the following rules: 4.00/1.89 4.00/1.89 perm_in_ga([], []) -> perm_out_ga([], []) 4.00/1.89 perm_in_ga(.(X, L), Z) -> U1_ga(X, L, Z, perm_in_ga(L, Y)) 4.00/1.89 U1_ga(X, L, Z, perm_out_ga(L, Y)) -> U2_ga(X, L, Z, insert_in_gga(X, Y, Z)) 4.00/1.89 insert_in_gga(X, [], .(X, [])) -> insert_out_gga(X, [], .(X, [])) 4.00/1.89 insert_in_gga(X, L, .(X, L)) -> insert_out_gga(X, L, .(X, L)) 4.00/1.89 insert_in_gga(X, .(H, L1), .(H, L2)) -> U3_gga(X, H, L1, L2, insert_in_gga(X, L1, L2)) 4.00/1.89 U3_gga(X, H, L1, L2, insert_out_gga(X, L1, L2)) -> insert_out_gga(X, .(H, L1), .(H, L2)) 4.00/1.89 U2_ga(X, L, Z, insert_out_gga(X, Y, Z)) -> perm_out_ga(.(X, L), Z) 4.00/1.89 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.00/1.89 4.00/1.89 [] = [] 4.00/1.89 4.00/1.89 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.00/1.89 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 4.00/1.89 4.00/1.89 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 4.00/1.89 4.00/1.89 insert_in_gga(x1, x2, x3) = insert_in_gga(x1, x2) 4.00/1.89 4.00/1.89 insert_out_gga(x1, x2, x3) = insert_out_gga(x3) 4.00/1.89 4.00/1.89 U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x5) 4.00/1.89 4.00/1.89 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (15) UsableRulesProof (EQUIVALENT) 4.00/1.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (16) 4.00/1.89 Obligation: 4.00/1.89 Pi DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 PERM_IN_GA(.(X, L), Z) -> PERM_IN_GA(L, Y) 4.00/1.89 4.00/1.89 R is empty. 4.00/1.89 The argument filtering Pi contains the following mapping: 4.00/1.89 .(x1, x2) = .(x1, x2) 4.00/1.89 4.00/1.89 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.00/1.89 4.00/1.89 4.00/1.89 We have to consider all (P,R,Pi)-chains 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (17) PiDPToQDPProof (SOUND) 4.00/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (18) 4.00/1.89 Obligation: 4.00/1.89 Q DP problem: 4.00/1.89 The TRS P consists of the following rules: 4.00/1.89 4.00/1.89 PERM_IN_GA(.(X, L)) -> PERM_IN_GA(L) 4.00/1.89 4.00/1.89 R is empty. 4.00/1.89 Q is empty. 4.00/1.89 We have to consider all (P,Q,R)-chains. 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (19) QDPSizeChangeProof (EQUIVALENT) 4.00/1.89 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. 4.00/1.89 4.00/1.89 From the DPs we obtained the following set of size-change graphs: 4.00/1.89 *PERM_IN_GA(.(X, L)) -> PERM_IN_GA(L) 4.00/1.89 The graph contains the following edges 1 > 1 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (20) 4.00/1.89 YES 4.00/1.91 EOF