5.36/2.28 YES 5.61/2.30 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.61/2.30 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.61/2.30 5.61/2.30 5.61/2.30 Left Termination of the query pattern 5.61/2.30 5.61/2.30 times(g,g,a) 5.61/2.30 5.61/2.30 w.r.t. the given Prolog program could successfully be proven: 5.61/2.30 5.61/2.30 (0) Prolog 5.61/2.30 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.61/2.30 (2) PiTRS 5.61/2.30 (3) DependencyPairsProof [EQUIVALENT, 5 ms] 5.61/2.30 (4) PiDP 5.61/2.30 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.61/2.30 (6) AND 5.61/2.30 (7) PiDP 5.61/2.30 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.61/2.30 (9) PiDP 5.61/2.30 (10) PiDPToQDPProof [SOUND, 0 ms] 5.61/2.30 (11) QDP 5.61/2.30 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.61/2.30 (13) YES 5.61/2.30 (14) PiDP 5.61/2.30 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.61/2.30 (16) PiDP 5.61/2.30 (17) PiDPToQDPProof [SOUND, 0 ms] 5.61/2.30 (18) QDP 5.61/2.30 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.61/2.30 (20) YES 5.61/2.30 (21) PiDP 5.61/2.30 (22) UsableRulesProof [EQUIVALENT, 0 ms] 5.61/2.30 (23) PiDP 5.61/2.30 (24) PiDPToQDPProof [SOUND, 0 ms] 5.61/2.30 (25) QDP 5.61/2.30 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.61/2.30 (27) YES 5.61/2.30 (28) PiDP 5.61/2.30 (29) UsableRulesProof [EQUIVALENT, 0 ms] 5.61/2.30 (30) PiDP 5.61/2.30 (31) PiDPToQDPProof [SOUND, 0 ms] 5.61/2.30 (32) QDP 5.61/2.30 (33) MRRProof [EQUIVALENT, 66 ms] 5.61/2.30 (34) QDP 5.61/2.30 (35) DependencyGraphProof [EQUIVALENT, 0 ms] 5.61/2.30 (36) TRUE 5.61/2.30 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (0) 5.61/2.30 Obligation: 5.61/2.30 Clauses: 5.61/2.30 5.61/2.30 even(0, true). 5.61/2.30 even(s(0), false). 5.61/2.30 even(s(s(X)), B) :- even(X, B). 5.61/2.30 half(0, 0). 5.61/2.30 half(s(s(X)), s(Y)) :- half(X, Y). 5.61/2.30 plus(0, Y, Y). 5.61/2.30 plus(s(X), Y, s(Z)) :- plus(X, Y, Z). 5.61/2.30 times(0, Y, 0). 5.61/2.30 times(s(X), Y, Z) :- ','(even(s(X), B), if(B, s(X), Y, Z)). 5.61/2.30 if(true, s(X), Y, Z) :- ','(half(s(X), X1), ','(times(X1, Y, Y1), plus(Y1, Y1, Z))). 5.61/2.30 if(false, s(X), Y, Z) :- ','(times(X, Y, U), plus(Y, U, Z)). 5.61/2.30 5.61/2.30 5.61/2.30 Query: times(g,g,a) 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (1) PrologToPiTRSProof (SOUND) 5.61/2.30 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.61/2.30 5.61/2.30 times_in_3: (b,b,f) 5.61/2.30 5.61/2.30 even_in_2: (b,f) 5.61/2.30 5.61/2.30 if_in_4: (b,b,b,f) 5.61/2.30 5.61/2.30 half_in_2: (b,f) 5.61/2.30 5.61/2.30 plus_in_3: (b,b,f) 5.61/2.30 5.61/2.30 Transforming Prolog into the following Term Rewriting System: 5.61/2.30 5.61/2.30 Pi-finite rewrite system: 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 5.61/2.30 5.61/2.30 5.61/2.30 5.61/2.30 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.61/2.30 5.61/2.30 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (2) 5.61/2.30 Obligation: 5.61/2.30 Pi-finite rewrite system: 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (3) DependencyPairsProof (EQUIVALENT) 5.61/2.30 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 TIMES_IN_GGA(s(X), Y, Z) -> U4_GGA(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 TIMES_IN_GGA(s(X), Y, Z) -> EVEN_IN_GA(s(X), B) 5.61/2.30 EVEN_IN_GA(s(s(X)), B) -> U1_GA(X, B, even_in_ga(X, B)) 5.61/2.30 EVEN_IN_GA(s(s(X)), B) -> EVEN_IN_GA(X, B) 5.61/2.30 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> U5_GGA(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> IF_IN_GGGA(B, s(X), Y, Z) 5.61/2.30 IF_IN_GGGA(true, s(X), Y, Z) -> U6_GGGA(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 IF_IN_GGGA(true, s(X), Y, Z) -> HALF_IN_GA(s(X), X1) 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> U2_GA(X, Y, half_in_ga(X, Y)) 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 5.61/2.30 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> U7_GGGA(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> TIMES_IN_GGA(X1, Y, Y1) 5.61/2.30 U7_GGGA(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_GGGA(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 U7_GGGA(X, Y, Z, times_out_gga(X1, Y, Y1)) -> PLUS_IN_GGA(Y1, Y1, Z) 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> U3_GGA(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) 5.61/2.30 IF_IN_GGGA(false, s(X), Y, Z) -> U9_GGGA(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 IF_IN_GGGA(false, s(X), Y, Z) -> TIMES_IN_GGA(X, Y, U) 5.61/2.30 U9_GGGA(X, Y, Z, times_out_gga(X, Y, U)) -> U10_GGGA(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U9_GGGA(X, Y, Z, times_out_gga(X, Y, U)) -> PLUS_IN_GGA(Y, U, Z) 5.61/2.30 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 TIMES_IN_GGA(x1, x2, x3) = TIMES_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) 5.61/2.30 5.61/2.30 EVEN_IN_GA(x1, x2) = EVEN_IN_GA(x1) 5.61/2.30 5.61/2.30 U1_GA(x1, x2, x3) = U1_GA(x3) 5.61/2.30 5.61/2.30 U5_GGA(x1, x2, x3, x4) = U5_GGA(x4) 5.61/2.30 5.61/2.30 IF_IN_GGGA(x1, x2, x3, x4) = IF_IN_GGGA(x1, x2, x3) 5.61/2.30 5.61/2.30 U6_GGGA(x1, x2, x3, x4) = U6_GGGA(x2, x4) 5.61/2.30 5.61/2.30 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 5.61/2.30 5.61/2.30 U2_GA(x1, x2, x3) = U2_GA(x3) 5.61/2.30 5.61/2.30 U7_GGGA(x1, x2, x3, x4) = U7_GGGA(x4) 5.61/2.30 5.61/2.30 U8_GGGA(x1, x2, x3, x4) = U8_GGGA(x4) 5.61/2.30 5.61/2.30 PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 5.61/2.30 5.61/2.30 U9_GGGA(x1, x2, x3, x4) = U9_GGGA(x2, x4) 5.61/2.30 5.61/2.30 U10_GGGA(x1, x2, x3, x4) = U10_GGGA(x4) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (4) 5.61/2.30 Obligation: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 TIMES_IN_GGA(s(X), Y, Z) -> U4_GGA(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 TIMES_IN_GGA(s(X), Y, Z) -> EVEN_IN_GA(s(X), B) 5.61/2.30 EVEN_IN_GA(s(s(X)), B) -> U1_GA(X, B, even_in_ga(X, B)) 5.61/2.30 EVEN_IN_GA(s(s(X)), B) -> EVEN_IN_GA(X, B) 5.61/2.30 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> U5_GGA(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> IF_IN_GGGA(B, s(X), Y, Z) 5.61/2.30 IF_IN_GGGA(true, s(X), Y, Z) -> U6_GGGA(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 IF_IN_GGGA(true, s(X), Y, Z) -> HALF_IN_GA(s(X), X1) 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> U2_GA(X, Y, half_in_ga(X, Y)) 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 5.61/2.30 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> U7_GGGA(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> TIMES_IN_GGA(X1, Y, Y1) 5.61/2.30 U7_GGGA(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_GGGA(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 U7_GGGA(X, Y, Z, times_out_gga(X1, Y, Y1)) -> PLUS_IN_GGA(Y1, Y1, Z) 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> U3_GGA(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) 5.61/2.30 IF_IN_GGGA(false, s(X), Y, Z) -> U9_GGGA(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 IF_IN_GGGA(false, s(X), Y, Z) -> TIMES_IN_GGA(X, Y, U) 5.61/2.30 U9_GGGA(X, Y, Z, times_out_gga(X, Y, U)) -> U10_GGGA(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U9_GGGA(X, Y, Z, times_out_gga(X, Y, U)) -> PLUS_IN_GGA(Y, U, Z) 5.61/2.30 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 TIMES_IN_GGA(x1, x2, x3) = TIMES_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) 5.61/2.30 5.61/2.30 EVEN_IN_GA(x1, x2) = EVEN_IN_GA(x1) 5.61/2.30 5.61/2.30 U1_GA(x1, x2, x3) = U1_GA(x3) 5.61/2.30 5.61/2.30 U5_GGA(x1, x2, x3, x4) = U5_GGA(x4) 5.61/2.30 5.61/2.30 IF_IN_GGGA(x1, x2, x3, x4) = IF_IN_GGGA(x1, x2, x3) 5.61/2.30 5.61/2.30 U6_GGGA(x1, x2, x3, x4) = U6_GGGA(x2, x4) 5.61/2.30 5.61/2.30 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 5.61/2.30 5.61/2.30 U2_GA(x1, x2, x3) = U2_GA(x3) 5.61/2.30 5.61/2.30 U7_GGGA(x1, x2, x3, x4) = U7_GGGA(x4) 5.61/2.30 5.61/2.30 U8_GGGA(x1, x2, x3, x4) = U8_GGGA(x4) 5.61/2.30 5.61/2.30 PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 U3_GGA(x1, x2, x3, x4) = U3_GGA(x4) 5.61/2.30 5.61/2.30 U9_GGGA(x1, x2, x3, x4) = U9_GGGA(x2, x4) 5.61/2.30 5.61/2.30 U10_GGGA(x1, x2, x3, x4) = U10_GGGA(x4) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (5) DependencyGraphProof (EQUIVALENT) 5.61/2.30 The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 12 less nodes. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (6) 5.61/2.30 Complex Obligation (AND) 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (7) 5.61/2.30 Obligation: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) 5.61/2.30 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (8) UsableRulesProof (EQUIVALENT) 5.61/2.30 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (9) 5.61/2.30 Obligation: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 PLUS_IN_GGA(s(X), Y, s(Z)) -> PLUS_IN_GGA(X, Y, Z) 5.61/2.30 5.61/2.30 R is empty. 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 PLUS_IN_GGA(x1, x2, x3) = PLUS_IN_GGA(x1, x2) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (10) PiDPToQDPProof (SOUND) 5.61/2.30 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (11) 5.61/2.30 Obligation: 5.61/2.30 Q DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 PLUS_IN_GGA(s(X), Y) -> PLUS_IN_GGA(X, Y) 5.61/2.30 5.61/2.30 R is empty. 5.61/2.30 Q is empty. 5.61/2.30 We have to consider all (P,Q,R)-chains. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (12) QDPSizeChangeProof (EQUIVALENT) 5.61/2.30 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. 5.61/2.30 5.61/2.30 From the DPs we obtained the following set of size-change graphs: 5.61/2.30 *PLUS_IN_GGA(s(X), Y) -> PLUS_IN_GGA(X, Y) 5.61/2.30 The graph contains the following edges 1 > 1, 2 >= 2 5.61/2.30 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (13) 5.61/2.30 YES 5.61/2.30 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (14) 5.61/2.30 Obligation: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 5.61/2.30 5.61/2.30 The TRS R consists of the following rules: 5.61/2.30 5.61/2.30 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.30 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.30 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.30 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.30 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.30 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.30 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.30 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.30 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.30 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.30 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.30 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.30 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.30 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.30 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.30 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.30 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.30 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.30 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.30 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.30 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.30 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.30 5.61/2.30 0 = 0 5.61/2.30 5.61/2.30 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.30 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.30 5.61/2.30 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.30 5.61/2.30 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.30 5.61/2.30 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.30 5.61/2.30 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.30 5.61/2.30 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.30 5.61/2.30 true = true 5.61/2.30 5.61/2.30 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.30 5.61/2.30 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.30 5.61/2.30 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.30 5.61/2.30 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.30 5.61/2.30 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.30 5.61/2.30 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.30 5.61/2.30 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.30 5.61/2.30 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.30 5.61/2.30 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.30 5.61/2.30 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.30 5.61/2.30 false = false 5.61/2.30 5.61/2.30 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.30 5.61/2.30 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.30 5.61/2.30 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (15) UsableRulesProof (EQUIVALENT) 5.61/2.30 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (16) 5.61/2.30 Obligation: 5.61/2.30 Pi DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 5.61/2.30 5.61/2.30 R is empty. 5.61/2.30 The argument filtering Pi contains the following mapping: 5.61/2.30 s(x1) = s(x1) 5.61/2.30 5.61/2.30 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 5.61/2.30 5.61/2.30 5.61/2.30 We have to consider all (P,R,Pi)-chains 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (17) PiDPToQDPProof (SOUND) 5.61/2.30 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.61/2.30 ---------------------------------------- 5.61/2.30 5.61/2.30 (18) 5.61/2.30 Obligation: 5.61/2.30 Q DP problem: 5.61/2.30 The TRS P consists of the following rules: 5.61/2.30 5.61/2.30 HALF_IN_GA(s(s(X))) -> HALF_IN_GA(X) 5.61/2.30 5.61/2.31 R is empty. 5.61/2.31 Q is empty. 5.61/2.31 We have to consider all (P,Q,R)-chains. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (19) QDPSizeChangeProof (EQUIVALENT) 5.61/2.31 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. 5.61/2.31 5.61/2.31 From the DPs we obtained the following set of size-change graphs: 5.61/2.31 *HALF_IN_GA(s(s(X))) -> HALF_IN_GA(X) 5.61/2.31 The graph contains the following edges 1 > 1 5.61/2.31 5.61/2.31 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (20) 5.61/2.31 YES 5.61/2.31 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (21) 5.61/2.31 Obligation: 5.61/2.31 Pi DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 EVEN_IN_GA(s(s(X)), B) -> EVEN_IN_GA(X, B) 5.61/2.31 5.61/2.31 The TRS R consists of the following rules: 5.61/2.31 5.61/2.31 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.31 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.31 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.31 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.31 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.31 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.31 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.31 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.31 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.31 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.31 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.31 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.31 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.31 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.31 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.31 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.31 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.31 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.31 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.31 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.31 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.31 5.61/2.31 The argument filtering Pi contains the following mapping: 5.61/2.31 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.31 5.61/2.31 0 = 0 5.61/2.31 5.61/2.31 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.31 5.61/2.31 s(x1) = s(x1) 5.61/2.31 5.61/2.31 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.31 5.61/2.31 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.31 5.61/2.31 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.31 5.61/2.31 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.31 5.61/2.31 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.31 5.61/2.31 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.31 5.61/2.31 true = true 5.61/2.31 5.61/2.31 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.31 5.61/2.31 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.31 5.61/2.31 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.31 5.61/2.31 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.31 5.61/2.31 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.31 5.61/2.31 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.31 5.61/2.31 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.31 5.61/2.31 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.31 5.61/2.31 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.31 5.61/2.31 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.31 5.61/2.31 false = false 5.61/2.31 5.61/2.31 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.31 5.61/2.31 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.31 5.61/2.31 EVEN_IN_GA(x1, x2) = EVEN_IN_GA(x1) 5.61/2.31 5.61/2.31 5.61/2.31 We have to consider all (P,R,Pi)-chains 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (22) UsableRulesProof (EQUIVALENT) 5.61/2.31 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (23) 5.61/2.31 Obligation: 5.61/2.31 Pi DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 EVEN_IN_GA(s(s(X)), B) -> EVEN_IN_GA(X, B) 5.61/2.31 5.61/2.31 R is empty. 5.61/2.31 The argument filtering Pi contains the following mapping: 5.61/2.31 s(x1) = s(x1) 5.61/2.31 5.61/2.31 EVEN_IN_GA(x1, x2) = EVEN_IN_GA(x1) 5.61/2.31 5.61/2.31 5.61/2.31 We have to consider all (P,R,Pi)-chains 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (24) PiDPToQDPProof (SOUND) 5.61/2.31 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (25) 5.61/2.31 Obligation: 5.61/2.31 Q DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 EVEN_IN_GA(s(s(X))) -> EVEN_IN_GA(X) 5.61/2.31 5.61/2.31 R is empty. 5.61/2.31 Q is empty. 5.61/2.31 We have to consider all (P,Q,R)-chains. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (26) QDPSizeChangeProof (EQUIVALENT) 5.61/2.31 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. 5.61/2.31 5.61/2.31 From the DPs we obtained the following set of size-change graphs: 5.61/2.31 *EVEN_IN_GA(s(s(X))) -> EVEN_IN_GA(X) 5.61/2.31 The graph contains the following edges 1 > 1 5.61/2.31 5.61/2.31 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (27) 5.61/2.31 YES 5.61/2.31 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (28) 5.61/2.31 Obligation: 5.61/2.31 Pi DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> IF_IN_GGGA(B, s(X), Y, Z) 5.61/2.31 IF_IN_GGGA(true, s(X), Y, Z) -> U6_GGGA(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.31 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> TIMES_IN_GGA(X1, Y, Y1) 5.61/2.31 TIMES_IN_GGA(s(X), Y, Z) -> U4_GGA(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.31 IF_IN_GGGA(false, s(X), Y, Z) -> TIMES_IN_GGA(X, Y, U) 5.61/2.31 5.61/2.31 The TRS R consists of the following rules: 5.61/2.31 5.61/2.31 times_in_gga(0, Y, 0) -> times_out_gga(0, Y, 0) 5.61/2.31 times_in_gga(s(X), Y, Z) -> U4_gga(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.31 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.31 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.31 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.31 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.31 U4_gga(X, Y, Z, even_out_ga(s(X), B)) -> U5_gga(X, Y, Z, if_in_ggga(B, s(X), Y, Z)) 5.61/2.31 if_in_ggga(true, s(X), Y, Z) -> U6_ggga(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.31 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.31 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.31 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.31 U6_ggga(X, Y, Z, half_out_ga(s(X), X1)) -> U7_ggga(X, Y, Z, times_in_gga(X1, Y, Y1)) 5.61/2.31 U7_ggga(X, Y, Z, times_out_gga(X1, Y, Y1)) -> U8_ggga(X, Y, Z, plus_in_gga(Y1, Y1, Z)) 5.61/2.31 plus_in_gga(0, Y, Y) -> plus_out_gga(0, Y, Y) 5.61/2.31 plus_in_gga(s(X), Y, s(Z)) -> U3_gga(X, Y, Z, plus_in_gga(X, Y, Z)) 5.61/2.31 U3_gga(X, Y, Z, plus_out_gga(X, Y, Z)) -> plus_out_gga(s(X), Y, s(Z)) 5.61/2.31 U8_ggga(X, Y, Z, plus_out_gga(Y1, Y1, Z)) -> if_out_ggga(true, s(X), Y, Z) 5.61/2.31 if_in_ggga(false, s(X), Y, Z) -> U9_ggga(X, Y, Z, times_in_gga(X, Y, U)) 5.61/2.31 U9_ggga(X, Y, Z, times_out_gga(X, Y, U)) -> U10_ggga(X, Y, Z, plus_in_gga(Y, U, Z)) 5.61/2.31 U10_ggga(X, Y, Z, plus_out_gga(Y, U, Z)) -> if_out_ggga(false, s(X), Y, Z) 5.61/2.31 U5_gga(X, Y, Z, if_out_ggga(B, s(X), Y, Z)) -> times_out_gga(s(X), Y, Z) 5.61/2.31 5.61/2.31 The argument filtering Pi contains the following mapping: 5.61/2.31 times_in_gga(x1, x2, x3) = times_in_gga(x1, x2) 5.61/2.31 5.61/2.31 0 = 0 5.61/2.31 5.61/2.31 times_out_gga(x1, x2, x3) = times_out_gga(x3) 5.61/2.31 5.61/2.31 s(x1) = s(x1) 5.61/2.31 5.61/2.31 U4_gga(x1, x2, x3, x4) = U4_gga(x1, x2, x4) 5.61/2.31 5.61/2.31 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.31 5.61/2.31 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.31 5.61/2.31 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.31 5.61/2.31 U5_gga(x1, x2, x3, x4) = U5_gga(x4) 5.61/2.31 5.61/2.31 if_in_ggga(x1, x2, x3, x4) = if_in_ggga(x1, x2, x3) 5.61/2.31 5.61/2.31 true = true 5.61/2.31 5.61/2.31 U6_ggga(x1, x2, x3, x4) = U6_ggga(x2, x4) 5.61/2.31 5.61/2.31 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.31 5.61/2.31 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.31 5.61/2.31 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.31 5.61/2.31 U7_ggga(x1, x2, x3, x4) = U7_ggga(x4) 5.61/2.31 5.61/2.31 U8_ggga(x1, x2, x3, x4) = U8_ggga(x4) 5.61/2.31 5.61/2.31 plus_in_gga(x1, x2, x3) = plus_in_gga(x1, x2) 5.61/2.31 5.61/2.31 plus_out_gga(x1, x2, x3) = plus_out_gga(x3) 5.61/2.31 5.61/2.31 U3_gga(x1, x2, x3, x4) = U3_gga(x4) 5.61/2.31 5.61/2.31 if_out_ggga(x1, x2, x3, x4) = if_out_ggga(x4) 5.61/2.31 5.61/2.31 false = false 5.61/2.31 5.61/2.31 U9_ggga(x1, x2, x3, x4) = U9_ggga(x2, x4) 5.61/2.31 5.61/2.31 U10_ggga(x1, x2, x3, x4) = U10_ggga(x4) 5.61/2.31 5.61/2.31 TIMES_IN_GGA(x1, x2, x3) = TIMES_IN_GGA(x1, x2) 5.61/2.31 5.61/2.31 U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) 5.61/2.31 5.61/2.31 IF_IN_GGGA(x1, x2, x3, x4) = IF_IN_GGGA(x1, x2, x3) 5.61/2.31 5.61/2.31 U6_GGGA(x1, x2, x3, x4) = U6_GGGA(x2, x4) 5.61/2.31 5.61/2.31 5.61/2.31 We have to consider all (P,R,Pi)-chains 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (29) UsableRulesProof (EQUIVALENT) 5.61/2.31 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (30) 5.61/2.31 Obligation: 5.61/2.31 Pi DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 U4_GGA(X, Y, Z, even_out_ga(s(X), B)) -> IF_IN_GGGA(B, s(X), Y, Z) 5.61/2.31 IF_IN_GGGA(true, s(X), Y, Z) -> U6_GGGA(X, Y, Z, half_in_ga(s(X), X1)) 5.61/2.31 U6_GGGA(X, Y, Z, half_out_ga(s(X), X1)) -> TIMES_IN_GGA(X1, Y, Y1) 5.61/2.31 TIMES_IN_GGA(s(X), Y, Z) -> U4_GGA(X, Y, Z, even_in_ga(s(X), B)) 5.61/2.31 IF_IN_GGGA(false, s(X), Y, Z) -> TIMES_IN_GGA(X, Y, U) 5.61/2.31 5.61/2.31 The TRS R consists of the following rules: 5.61/2.31 5.61/2.31 half_in_ga(s(s(X)), s(Y)) -> U2_ga(X, Y, half_in_ga(X, Y)) 5.61/2.31 even_in_ga(s(0), false) -> even_out_ga(s(0), false) 5.61/2.31 even_in_ga(s(s(X)), B) -> U1_ga(X, B, even_in_ga(X, B)) 5.61/2.31 U2_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 5.61/2.31 U1_ga(X, B, even_out_ga(X, B)) -> even_out_ga(s(s(X)), B) 5.61/2.31 half_in_ga(0, 0) -> half_out_ga(0, 0) 5.61/2.31 even_in_ga(0, true) -> even_out_ga(0, true) 5.61/2.31 5.61/2.31 The argument filtering Pi contains the following mapping: 5.61/2.31 0 = 0 5.61/2.31 5.61/2.31 s(x1) = s(x1) 5.61/2.31 5.61/2.31 even_in_ga(x1, x2) = even_in_ga(x1) 5.61/2.31 5.61/2.31 even_out_ga(x1, x2) = even_out_ga(x2) 5.61/2.31 5.61/2.31 U1_ga(x1, x2, x3) = U1_ga(x3) 5.61/2.31 5.61/2.31 true = true 5.61/2.31 5.61/2.31 half_in_ga(x1, x2) = half_in_ga(x1) 5.61/2.31 5.61/2.31 half_out_ga(x1, x2) = half_out_ga(x2) 5.61/2.31 5.61/2.31 U2_ga(x1, x2, x3) = U2_ga(x3) 5.61/2.31 5.61/2.31 false = false 5.61/2.31 5.61/2.31 TIMES_IN_GGA(x1, x2, x3) = TIMES_IN_GGA(x1, x2) 5.61/2.31 5.61/2.31 U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) 5.61/2.31 5.61/2.31 IF_IN_GGGA(x1, x2, x3, x4) = IF_IN_GGGA(x1, x2, x3) 5.61/2.31 5.61/2.31 U6_GGGA(x1, x2, x3, x4) = U6_GGGA(x2, x4) 5.61/2.31 5.61/2.31 5.61/2.31 We have to consider all (P,R,Pi)-chains 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (31) PiDPToQDPProof (SOUND) 5.61/2.31 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (32) 5.61/2.31 Obligation: 5.61/2.31 Q DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 U4_GGA(X, Y, even_out_ga(B)) -> IF_IN_GGGA(B, s(X), Y) 5.61/2.31 IF_IN_GGGA(true, s(X), Y) -> U6_GGGA(Y, half_in_ga(s(X))) 5.61/2.31 U6_GGGA(Y, half_out_ga(X1)) -> TIMES_IN_GGA(X1, Y) 5.61/2.31 TIMES_IN_GGA(s(X), Y) -> U4_GGA(X, Y, even_in_ga(s(X))) 5.61/2.31 IF_IN_GGGA(false, s(X), Y) -> TIMES_IN_GGA(X, Y) 5.61/2.31 5.61/2.31 The TRS R consists of the following rules: 5.61/2.31 5.61/2.31 half_in_ga(s(s(X))) -> U2_ga(half_in_ga(X)) 5.61/2.31 even_in_ga(s(0)) -> even_out_ga(false) 5.61/2.31 even_in_ga(s(s(X))) -> U1_ga(even_in_ga(X)) 5.61/2.31 U2_ga(half_out_ga(Y)) -> half_out_ga(s(Y)) 5.61/2.31 U1_ga(even_out_ga(B)) -> even_out_ga(B) 5.61/2.31 half_in_ga(0) -> half_out_ga(0) 5.61/2.31 even_in_ga(0) -> even_out_ga(true) 5.61/2.31 5.61/2.31 The set Q consists of the following terms: 5.61/2.31 5.61/2.31 half_in_ga(x0) 5.61/2.31 even_in_ga(x0) 5.61/2.31 U2_ga(x0) 5.61/2.31 U1_ga(x0) 5.61/2.31 5.61/2.31 We have to consider all (P,Q,R)-chains. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (33) MRRProof (EQUIVALENT) 5.61/2.31 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.61/2.31 5.61/2.31 Strictly oriented dependency pairs: 5.61/2.31 5.61/2.31 IF_IN_GGGA(false, s(X), Y) -> TIMES_IN_GGA(X, Y) 5.61/2.31 5.61/2.31 Strictly oriented rules of the TRS R: 5.61/2.31 5.61/2.31 half_in_ga(s(s(X))) -> U2_ga(half_in_ga(X)) 5.61/2.31 even_in_ga(s(0)) -> even_out_ga(false) 5.61/2.31 even_in_ga(s(s(X))) -> U1_ga(even_in_ga(X)) 5.61/2.31 5.61/2.31 Used ordering: Polynomial interpretation [POLO]: 5.61/2.31 5.61/2.31 POL(0) = 0 5.61/2.31 POL(IF_IN_GGGA(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 5.61/2.31 POL(TIMES_IN_GGA(x_1, x_2)) = 2*x_1 + x_2 5.61/2.31 POL(U1_ga(x_1)) = x_1 5.61/2.31 POL(U2_ga(x_1)) = 2 + 2*x_1 5.61/2.31 POL(U4_GGA(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + x_3 5.61/2.31 POL(U6_GGGA(x_1, x_2)) = x_1 + x_2 5.61/2.31 POL(even_in_ga(x_1)) = x_1 5.61/2.31 POL(even_out_ga(x_1)) = 2*x_1 5.61/2.31 POL(false) = 0 5.61/2.31 POL(half_in_ga(x_1)) = x_1 5.61/2.31 POL(half_out_ga(x_1)) = 2*x_1 5.61/2.31 POL(s(x_1)) = 1 + 2*x_1 5.61/2.31 POL(true) = 0 5.61/2.31 5.61/2.31 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (34) 5.61/2.31 Obligation: 5.61/2.31 Q DP problem: 5.61/2.31 The TRS P consists of the following rules: 5.61/2.31 5.61/2.31 U4_GGA(X, Y, even_out_ga(B)) -> IF_IN_GGGA(B, s(X), Y) 5.61/2.31 IF_IN_GGGA(true, s(X), Y) -> U6_GGGA(Y, half_in_ga(s(X))) 5.61/2.31 U6_GGGA(Y, half_out_ga(X1)) -> TIMES_IN_GGA(X1, Y) 5.61/2.31 TIMES_IN_GGA(s(X), Y) -> U4_GGA(X, Y, even_in_ga(s(X))) 5.61/2.31 5.61/2.31 The TRS R consists of the following rules: 5.61/2.31 5.61/2.31 U2_ga(half_out_ga(Y)) -> half_out_ga(s(Y)) 5.61/2.31 U1_ga(even_out_ga(B)) -> even_out_ga(B) 5.61/2.31 half_in_ga(0) -> half_out_ga(0) 5.61/2.31 even_in_ga(0) -> even_out_ga(true) 5.61/2.31 5.61/2.31 The set Q consists of the following terms: 5.61/2.31 5.61/2.31 half_in_ga(x0) 5.61/2.31 even_in_ga(x0) 5.61/2.31 U2_ga(x0) 5.61/2.31 U1_ga(x0) 5.61/2.31 5.61/2.31 We have to consider all (P,Q,R)-chains. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (35) DependencyGraphProof (EQUIVALENT) 5.61/2.31 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. 5.61/2.31 ---------------------------------------- 5.61/2.31 5.61/2.31 (36) 5.61/2.31 TRUE 5.61/2.34 EOF