4.86/2.06 YES 4.86/2.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.86/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.86/2.07 4.86/2.07 4.86/2.07 Left Termination of the query pattern 4.86/2.07 4.86/2.07 log(g,a) 4.86/2.07 4.86/2.07 w.r.t. the given Prolog program could successfully be proven: 4.86/2.07 4.86/2.07 (0) Prolog 4.86/2.07 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.86/2.07 (2) PiTRS 4.86/2.07 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.86/2.07 (4) PiDP 4.86/2.07 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.86/2.07 (6) AND 4.86/2.07 (7) PiDP 4.86/2.07 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.86/2.07 (9) PiDP 4.86/2.07 (10) PiDPToQDPProof [SOUND, 0 ms] 4.86/2.07 (11) QDP 4.86/2.07 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.86/2.07 (13) YES 4.86/2.07 (14) PiDP 4.86/2.07 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.86/2.07 (16) PiDP 4.86/2.07 (17) PiDPToQDPProof [SOUND, 0 ms] 4.86/2.07 (18) QDP 4.86/2.07 (19) MRRProof [EQUIVALENT, 1 ms] 4.86/2.07 (20) QDP 4.86/2.07 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 4.86/2.07 (22) TRUE 4.86/2.07 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (0) 4.86/2.07 Obligation: 4.86/2.07 Clauses: 4.86/2.07 4.86/2.07 half(0, 0). 4.86/2.07 half(s(0), 0). 4.86/2.07 half(s(s(X)), s(Y)) :- half(X, Y). 4.86/2.07 log(0, s(0)). 4.86/2.07 log(s(X), s(Y)) :- ','(half(s(X), Z), log(Z, Y)). 4.86/2.07 4.86/2.07 4.86/2.07 Query: log(g,a) 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (1) PrologToPiTRSProof (SOUND) 4.86/2.07 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.86/2.07 4.86/2.07 log_in_2: (b,f) 4.86/2.07 4.86/2.07 half_in_2: (b,f) 4.86/2.07 4.86/2.07 Transforming Prolog into the following Term Rewriting System: 4.86/2.07 4.86/2.07 Pi-finite rewrite system: 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 4.86/2.07 4.86/2.07 4.86/2.07 4.86/2.07 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.86/2.07 4.86/2.07 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (2) 4.86/2.07 Obligation: 4.86/2.07 Pi-finite rewrite system: 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (3) DependencyPairsProof (EQUIVALENT) 4.86/2.07 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> U2_GA(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> HALF_IN_GA(s(X), Z) 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> U1_GA(X, Y, half_in_ga(X, Y)) 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> U3_GA(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> LOG_IN_GA(Z, Y) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 LOG_IN_GA(x1, x2) = LOG_IN_GA(x1) 4.86/2.07 4.86/2.07 U2_GA(x1, x2, x3) = U2_GA(x3) 4.86/2.07 4.86/2.07 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 4.86/2.07 4.86/2.07 U1_GA(x1, x2, x3) = U1_GA(x3) 4.86/2.07 4.86/2.07 U3_GA(x1, x2, x3) = U3_GA(x3) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (4) 4.86/2.07 Obligation: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> U2_GA(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> HALF_IN_GA(s(X), Z) 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> U1_GA(X, Y, half_in_ga(X, Y)) 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> U3_GA(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> LOG_IN_GA(Z, Y) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 LOG_IN_GA(x1, x2) = LOG_IN_GA(x1) 4.86/2.07 4.86/2.07 U2_GA(x1, x2, x3) = U2_GA(x3) 4.86/2.07 4.86/2.07 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 4.86/2.07 4.86/2.07 U1_GA(x1, x2, x3) = U1_GA(x3) 4.86/2.07 4.86/2.07 U3_GA(x1, x2, x3) = U3_GA(x3) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (5) DependencyGraphProof (EQUIVALENT) 4.86/2.07 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (6) 4.86/2.07 Complex Obligation (AND) 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (7) 4.86/2.07 Obligation: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (8) UsableRulesProof (EQUIVALENT) 4.86/2.07 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (9) 4.86/2.07 Obligation: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 HALF_IN_GA(s(s(X)), s(Y)) -> HALF_IN_GA(X, Y) 4.86/2.07 4.86/2.07 R is empty. 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 HALF_IN_GA(x1, x2) = HALF_IN_GA(x1) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (10) PiDPToQDPProof (SOUND) 4.86/2.07 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (11) 4.86/2.07 Obligation: 4.86/2.07 Q DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 HALF_IN_GA(s(s(X))) -> HALF_IN_GA(X) 4.86/2.07 4.86/2.07 R is empty. 4.86/2.07 Q is empty. 4.86/2.07 We have to consider all (P,Q,R)-chains. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (12) QDPSizeChangeProof (EQUIVALENT) 4.86/2.07 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.86/2.07 4.86/2.07 From the DPs we obtained the following set of size-change graphs: 4.86/2.07 *HALF_IN_GA(s(s(X))) -> HALF_IN_GA(X) 4.86/2.07 The graph contains the following edges 1 > 1 4.86/2.07 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (13) 4.86/2.07 YES 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (14) 4.86/2.07 Obligation: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> LOG_IN_GA(Z, Y) 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> U2_GA(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 log_in_ga(0, s(0)) -> log_out_ga(0, s(0)) 4.86/2.07 log_in_ga(s(X), s(Y)) -> U2_ga(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 U2_ga(X, Y, half_out_ga(s(X), Z)) -> U3_ga(X, Y, log_in_ga(Z, Y)) 4.86/2.07 U3_ga(X, Y, log_out_ga(Z, Y)) -> log_out_ga(s(X), s(Y)) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 log_in_ga(x1, x2) = log_in_ga(x1) 4.86/2.07 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 log_out_ga(x1, x2) = log_out_ga(x2) 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 U2_ga(x1, x2, x3) = U2_ga(x3) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 U3_ga(x1, x2, x3) = U3_ga(x3) 4.86/2.07 4.86/2.07 LOG_IN_GA(x1, x2) = LOG_IN_GA(x1) 4.86/2.07 4.86/2.07 U2_GA(x1, x2, x3) = U2_GA(x3) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (15) UsableRulesProof (EQUIVALENT) 4.86/2.07 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (16) 4.86/2.07 Obligation: 4.86/2.07 Pi DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 U2_GA(X, Y, half_out_ga(s(X), Z)) -> LOG_IN_GA(Z, Y) 4.86/2.07 LOG_IN_GA(s(X), s(Y)) -> U2_GA(X, Y, half_in_ga(s(X), Z)) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 half_in_ga(s(0), 0) -> half_out_ga(s(0), 0) 4.86/2.07 half_in_ga(s(s(X)), s(Y)) -> U1_ga(X, Y, half_in_ga(X, Y)) 4.86/2.07 U1_ga(X, Y, half_out_ga(X, Y)) -> half_out_ga(s(s(X)), s(Y)) 4.86/2.07 half_in_ga(0, 0) -> half_out_ga(0, 0) 4.86/2.07 4.86/2.07 The argument filtering Pi contains the following mapping: 4.86/2.07 0 = 0 4.86/2.07 4.86/2.07 s(x1) = s(x1) 4.86/2.07 4.86/2.07 half_in_ga(x1, x2) = half_in_ga(x1) 4.86/2.07 4.86/2.07 half_out_ga(x1, x2) = half_out_ga(x2) 4.86/2.07 4.86/2.07 U1_ga(x1, x2, x3) = U1_ga(x3) 4.86/2.07 4.86/2.07 LOG_IN_GA(x1, x2) = LOG_IN_GA(x1) 4.86/2.07 4.86/2.07 U2_GA(x1, x2, x3) = U2_GA(x3) 4.86/2.07 4.86/2.07 4.86/2.07 We have to consider all (P,R,Pi)-chains 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (17) PiDPToQDPProof (SOUND) 4.86/2.07 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (18) 4.86/2.07 Obligation: 4.86/2.07 Q DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 U2_GA(half_out_ga(Z)) -> LOG_IN_GA(Z) 4.86/2.07 LOG_IN_GA(s(X)) -> U2_GA(half_in_ga(s(X))) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 half_in_ga(s(0)) -> half_out_ga(0) 4.86/2.07 half_in_ga(s(s(X))) -> U1_ga(half_in_ga(X)) 4.86/2.07 U1_ga(half_out_ga(Y)) -> half_out_ga(s(Y)) 4.86/2.07 half_in_ga(0) -> half_out_ga(0) 4.86/2.07 4.86/2.07 The set Q consists of the following terms: 4.86/2.07 4.86/2.07 half_in_ga(x0) 4.86/2.07 U1_ga(x0) 4.86/2.07 4.86/2.07 We have to consider all (P,Q,R)-chains. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (19) MRRProof (EQUIVALENT) 4.86/2.07 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. 4.86/2.07 4.86/2.07 4.86/2.07 Strictly oriented rules of the TRS R: 4.86/2.07 4.86/2.07 half_in_ga(s(0)) -> half_out_ga(0) 4.86/2.07 half_in_ga(s(s(X))) -> U1_ga(half_in_ga(X)) 4.86/2.07 4.86/2.07 Used ordering: Polynomial interpretation [POLO]: 4.86/2.07 4.86/2.07 POL(0) = 0 4.86/2.07 POL(LOG_IN_GA(x_1)) = 2*x_1 4.86/2.07 POL(U1_ga(x_1)) = 2 + x_1 4.86/2.07 POL(U2_GA(x_1)) = x_1 4.86/2.07 POL(half_in_ga(x_1)) = 2*x_1 4.86/2.07 POL(half_out_ga(x_1)) = 2*x_1 4.86/2.07 POL(s(x_1)) = 1 + x_1 4.86/2.07 4.86/2.07 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (20) 4.86/2.07 Obligation: 4.86/2.07 Q DP problem: 4.86/2.07 The TRS P consists of the following rules: 4.86/2.07 4.86/2.07 U2_GA(half_out_ga(Z)) -> LOG_IN_GA(Z) 4.86/2.07 LOG_IN_GA(s(X)) -> U2_GA(half_in_ga(s(X))) 4.86/2.07 4.86/2.07 The TRS R consists of the following rules: 4.86/2.07 4.86/2.07 U1_ga(half_out_ga(Y)) -> half_out_ga(s(Y)) 4.86/2.07 half_in_ga(0) -> half_out_ga(0) 4.86/2.07 4.86/2.07 The set Q consists of the following terms: 4.86/2.07 4.86/2.07 half_in_ga(x0) 4.86/2.07 U1_ga(x0) 4.86/2.07 4.86/2.07 We have to consider all (P,Q,R)-chains. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (21) DependencyGraphProof (EQUIVALENT) 4.86/2.07 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 4.86/2.07 ---------------------------------------- 4.86/2.07 4.86/2.07 (22) 4.86/2.07 TRUE 5.06/2.11 EOF