7.99/3.00 YES 8.23/3.05 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 8.23/3.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.23/3.05 8.23/3.05 8.23/3.05 Left Termination of the query pattern 8.23/3.05 8.23/3.05 cnfequiv(g,a) 8.23/3.05 8.23/3.05 w.r.t. the given Prolog program could successfully be proven: 8.23/3.05 8.23/3.05 (0) Prolog 8.23/3.05 (1) PrologToPiTRSProof [SOUND, 0 ms] 8.23/3.05 (2) PiTRS 8.23/3.05 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.23/3.05 (4) PiDP 8.23/3.05 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.23/3.05 (6) AND 8.23/3.05 (7) PiDP 8.23/3.05 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.23/3.05 (9) PiDP 8.23/3.05 (10) PiDPToQDPProof [SOUND, 12 ms] 8.23/3.05 (11) QDP 8.23/3.05 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.23/3.05 (13) YES 8.23/3.05 (14) PiDP 8.23/3.05 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.23/3.05 (16) PiDP 8.23/3.05 (17) PiDPToQDPProof [SOUND, 0 ms] 8.23/3.05 (18) QDP 8.23/3.05 (19) QDPOrderProof [EQUIVALENT, 95 ms] 8.23/3.05 (20) QDP 8.23/3.05 (21) PisEmptyProof [EQUIVALENT, 0 ms] 8.23/3.05 (22) YES 8.23/3.05 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (0) 8.23/3.05 Obligation: 8.23/3.05 Clauses: 8.23/3.05 8.23/3.05 cnfequiv(X, Y) :- ','(transform(X, Z), cnfequiv(Z, Y)). 8.23/3.05 cnfequiv(X, X). 8.23/3.05 transform(n(n(X)), X). 8.23/3.05 transform(n(a(X, Y)), o(n(X), n(Y))). 8.23/3.05 transform(n(o(X, Y)), a(n(X), n(Y))). 8.23/3.05 transform(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))). 8.23/3.05 transform(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))). 8.23/3.05 transform(o(X1, Y), o(X2, Y)) :- transform(X1, X2). 8.23/3.05 transform(o(X, Y1), o(X, Y2)) :- transform(Y1, Y2). 8.23/3.05 transform(a(X1, Y), a(X2, Y)) :- transform(X1, X2). 8.23/3.05 transform(a(X, Y1), a(X, Y2)) :- transform(Y1, Y2). 8.23/3.05 transform(n(X1), n(X2)) :- transform(X1, X2). 8.23/3.05 8.23/3.05 8.23/3.05 Query: cnfequiv(g,a) 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (1) PrologToPiTRSProof (SOUND) 8.23/3.05 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.23/3.05 8.23/3.05 cnfequiv_in_2: (b,f) 8.23/3.05 8.23/3.05 transform_in_2: (b,f) 8.23/3.05 8.23/3.05 Transforming Prolog into the following Term Rewriting System: 8.23/3.05 8.23/3.05 Pi-finite rewrite system: 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 8.23/3.05 8.23/3.05 8.23/3.05 8.23/3.05 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.23/3.05 8.23/3.05 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (2) 8.23/3.05 Obligation: 8.23/3.05 Pi-finite rewrite system: 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (3) DependencyPairsProof (EQUIVALENT) 8.23/3.05 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> U1_GA(X, Y, transform_in_ga(X, Z)) 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> TRANSFORM_IN_GA(X, Z) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> U3_GA(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> U4_GA(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> U5_GA(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> U6_GA(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> U7_GA(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> U2_GA(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> CNFEQUIV_IN_GA(Z, Y) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(x1, x2) = CNFEQUIV_IN_GA(x1) 8.23/3.05 8.23/3.05 U1_GA(x1, x2, x3) = U1_GA(x3) 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(x1, x2) = TRANSFORM_IN_GA(x1) 8.23/3.05 8.23/3.05 U3_GA(x1, x2, x3, x4) = U3_GA(x2, x4) 8.23/3.05 8.23/3.05 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) 8.23/3.05 8.23/3.05 U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) 8.23/3.05 8.23/3.05 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) 8.23/3.05 8.23/3.05 U7_GA(x1, x2, x3) = U7_GA(x3) 8.23/3.05 8.23/3.05 U2_GA(x1, x2, x3) = U2_GA(x3) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (4) 8.23/3.05 Obligation: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> U1_GA(X, Y, transform_in_ga(X, Z)) 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> TRANSFORM_IN_GA(X, Z) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> U3_GA(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> U4_GA(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> U5_GA(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> U6_GA(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> U7_GA(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> U2_GA(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> CNFEQUIV_IN_GA(Z, Y) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(x1, x2) = CNFEQUIV_IN_GA(x1) 8.23/3.05 8.23/3.05 U1_GA(x1, x2, x3) = U1_GA(x3) 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(x1, x2) = TRANSFORM_IN_GA(x1) 8.23/3.05 8.23/3.05 U3_GA(x1, x2, x3, x4) = U3_GA(x2, x4) 8.23/3.05 8.23/3.05 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) 8.23/3.05 8.23/3.05 U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) 8.23/3.05 8.23/3.05 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) 8.23/3.05 8.23/3.05 U7_GA(x1, x2, x3) = U7_GA(x3) 8.23/3.05 8.23/3.05 U2_GA(x1, x2, x3) = U2_GA(x3) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (5) DependencyGraphProof (EQUIVALENT) 8.23/3.05 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 7 less nodes. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (6) 8.23/3.05 Complex Obligation (AND) 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (7) 8.23/3.05 Obligation: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(x1, x2) = TRANSFORM_IN_GA(x1) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (8) UsableRulesProof (EQUIVALENT) 8.23/3.05 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (9) 8.23/3.05 Obligation: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1), o(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y), o(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y), a(X2, Y)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1), a(X, Y2)) -> TRANSFORM_IN_GA(Y1, Y2) 8.23/3.05 TRANSFORM_IN_GA(n(X1), n(X2)) -> TRANSFORM_IN_GA(X1, X2) 8.23/3.05 8.23/3.05 R is empty. 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(x1, x2) = TRANSFORM_IN_GA(x1) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (10) PiDPToQDPProof (SOUND) 8.23/3.05 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (11) 8.23/3.05 Obligation: 8.23/3.05 Q DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 TRANSFORM_IN_GA(o(X, Y1)) -> TRANSFORM_IN_GA(Y1) 8.23/3.05 TRANSFORM_IN_GA(o(X1, Y)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 TRANSFORM_IN_GA(a(X1, Y)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 TRANSFORM_IN_GA(a(X, Y1)) -> TRANSFORM_IN_GA(Y1) 8.23/3.05 TRANSFORM_IN_GA(n(X1)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 8.23/3.05 R is empty. 8.23/3.05 Q is empty. 8.23/3.05 We have to consider all (P,Q,R)-chains. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (12) QDPSizeChangeProof (EQUIVALENT) 8.23/3.05 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. 8.23/3.05 8.23/3.05 From the DPs we obtained the following set of size-change graphs: 8.23/3.05 *TRANSFORM_IN_GA(o(X, Y1)) -> TRANSFORM_IN_GA(Y1) 8.23/3.05 The graph contains the following edges 1 > 1 8.23/3.05 8.23/3.05 8.23/3.05 *TRANSFORM_IN_GA(o(X1, Y)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 The graph contains the following edges 1 > 1 8.23/3.05 8.23/3.05 8.23/3.05 *TRANSFORM_IN_GA(a(X1, Y)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 The graph contains the following edges 1 > 1 8.23/3.05 8.23/3.05 8.23/3.05 *TRANSFORM_IN_GA(a(X, Y1)) -> TRANSFORM_IN_GA(Y1) 8.23/3.05 The graph contains the following edges 1 > 1 8.23/3.05 8.23/3.05 8.23/3.05 *TRANSFORM_IN_GA(n(X1)) -> TRANSFORM_IN_GA(X1) 8.23/3.05 The graph contains the following edges 1 > 1 8.23/3.05 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (13) 8.23/3.05 YES 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (14) 8.23/3.05 Obligation: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> CNFEQUIV_IN_GA(Z, Y) 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> U1_GA(X, Y, transform_in_ga(X, Z)) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 cnfequiv_in_ga(X, Y) -> U1_ga(X, Y, transform_in_ga(X, Z)) 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U1_ga(X, Y, transform_out_ga(X, Z)) -> U2_ga(X, Y, cnfequiv_in_ga(Z, Y)) 8.23/3.05 cnfequiv_in_ga(X, X) -> cnfequiv_out_ga(X, X) 8.23/3.05 U2_ga(X, Y, cnfequiv_out_ga(Z, Y)) -> cnfequiv_out_ga(X, Y) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 cnfequiv_in_ga(x1, x2) = cnfequiv_in_ga(x1) 8.23/3.05 8.23/3.05 U1_ga(x1, x2, x3) = U1_ga(x3) 8.23/3.05 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 U2_ga(x1, x2, x3) = U2_ga(x3) 8.23/3.05 8.23/3.05 cnfequiv_out_ga(x1, x2) = cnfequiv_out_ga(x2) 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(x1, x2) = CNFEQUIV_IN_GA(x1) 8.23/3.05 8.23/3.05 U1_GA(x1, x2, x3) = U1_GA(x3) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (15) UsableRulesProof (EQUIVALENT) 8.23/3.05 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (16) 8.23/3.05 Obligation: 8.23/3.05 Pi DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 U1_GA(X, Y, transform_out_ga(X, Z)) -> CNFEQUIV_IN_GA(Z, Y) 8.23/3.05 CNFEQUIV_IN_GA(X, Y) -> U1_GA(X, Y, transform_in_ga(X, Z)) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 transform_in_ga(n(n(X)), X) -> transform_out_ga(n(n(X)), X) 8.23/3.05 transform_in_ga(n(a(X, Y)), o(n(X), n(Y))) -> transform_out_ga(n(a(X, Y)), o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y)), a(n(X), n(Y))) -> transform_out_ga(n(o(X, Y)), a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) -> transform_out_ga(o(X, a(Y, Z)), a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) -> transform_out_ga(o(a(X, Y), Z), a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y), o(X2, Y)) -> U3_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(o(X, Y1), o(X, Y2)) -> U4_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(a(X1, Y), a(X2, Y)) -> U5_ga(X1, Y, X2, transform_in_ga(X1, X2)) 8.23/3.05 transform_in_ga(a(X, Y1), a(X, Y2)) -> U6_ga(X, Y1, Y2, transform_in_ga(Y1, Y2)) 8.23/3.05 transform_in_ga(n(X1), n(X2)) -> U7_ga(X1, X2, transform_in_ga(X1, X2)) 8.23/3.05 U3_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(o(X1, Y), o(X2, Y)) 8.23/3.05 U4_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(o(X, Y1), o(X, Y2)) 8.23/3.05 U5_ga(X1, Y, X2, transform_out_ga(X1, X2)) -> transform_out_ga(a(X1, Y), a(X2, Y)) 8.23/3.05 U6_ga(X, Y1, Y2, transform_out_ga(Y1, Y2)) -> transform_out_ga(a(X, Y1), a(X, Y2)) 8.23/3.05 U7_ga(X1, X2, transform_out_ga(X1, X2)) -> transform_out_ga(n(X1), n(X2)) 8.23/3.05 8.23/3.05 The argument filtering Pi contains the following mapping: 8.23/3.05 transform_in_ga(x1, x2) = transform_in_ga(x1) 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1, x2) = transform_out_ga(x2) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) 8.23/3.05 8.23/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x1, x4) 8.23/3.05 8.23/3.05 U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) 8.23/3.05 8.23/3.05 U6_ga(x1, x2, x3, x4) = U6_ga(x1, x4) 8.23/3.05 8.23/3.05 U7_ga(x1, x2, x3) = U7_ga(x3) 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(x1, x2) = CNFEQUIV_IN_GA(x1) 8.23/3.05 8.23/3.05 U1_GA(x1, x2, x3) = U1_GA(x3) 8.23/3.05 8.23/3.05 8.23/3.05 We have to consider all (P,R,Pi)-chains 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (17) PiDPToQDPProof (SOUND) 8.23/3.05 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (18) 8.23/3.05 Obligation: 8.23/3.05 Q DP problem: 8.23/3.05 The TRS P consists of the following rules: 8.23/3.05 8.23/3.05 U1_GA(transform_out_ga(Z)) -> CNFEQUIV_IN_GA(Z) 8.23/3.05 CNFEQUIV_IN_GA(X) -> U1_GA(transform_in_ga(X)) 8.23/3.05 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 transform_in_ga(n(n(X))) -> transform_out_ga(X) 8.23/3.05 transform_in_ga(n(a(X, Y))) -> transform_out_ga(o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y))) -> transform_out_ga(a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z))) -> transform_out_ga(a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z)) -> transform_out_ga(a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y)) -> U3_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(o(X, Y1)) -> U4_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(a(X1, Y)) -> U5_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(a(X, Y1)) -> U6_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(n(X1)) -> U7_ga(transform_in_ga(X1)) 8.23/3.05 U3_ga(Y, transform_out_ga(X2)) -> transform_out_ga(o(X2, Y)) 8.23/3.05 U4_ga(X, transform_out_ga(Y2)) -> transform_out_ga(o(X, Y2)) 8.23/3.05 U5_ga(Y, transform_out_ga(X2)) -> transform_out_ga(a(X2, Y)) 8.23/3.05 U6_ga(X, transform_out_ga(Y2)) -> transform_out_ga(a(X, Y2)) 8.23/3.05 U7_ga(transform_out_ga(X2)) -> transform_out_ga(n(X2)) 8.23/3.05 8.23/3.05 The set Q consists of the following terms: 8.23/3.05 8.23/3.05 transform_in_ga(x0) 8.23/3.05 U3_ga(x0, x1) 8.23/3.05 U4_ga(x0, x1) 8.23/3.05 U5_ga(x0, x1) 8.23/3.05 U6_ga(x0, x1) 8.23/3.05 U7_ga(x0) 8.23/3.05 8.23/3.05 We have to consider all (P,Q,R)-chains. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (19) QDPOrderProof (EQUIVALENT) 8.23/3.05 We use the reduction pair processor [LPAR04,JAR06]. 8.23/3.05 8.23/3.05 8.23/3.05 The following pairs can be oriented strictly and are deleted. 8.23/3.05 8.23/3.05 U1_GA(transform_out_ga(Z)) -> CNFEQUIV_IN_GA(Z) 8.23/3.05 CNFEQUIV_IN_GA(X) -> U1_GA(transform_in_ga(X)) 8.23/3.05 The remaining pairs can at least be oriented weakly. 8.23/3.05 Used ordering: Combined order from the following AFS and order. 8.23/3.05 U1_GA(x1) = U1_GA(x1) 8.23/3.05 8.23/3.05 transform_out_ga(x1) = transform_out_ga(x1) 8.23/3.05 8.23/3.05 CNFEQUIV_IN_GA(x1) = CNFEQUIV_IN_GA(x1) 8.23/3.05 8.23/3.05 transform_in_ga(x1) = x1 8.23/3.05 8.23/3.05 n(x1) = n(x1) 8.23/3.05 8.23/3.05 a(x1, x2) = a(x1, x2) 8.23/3.05 8.23/3.05 o(x1, x2) = o(x1, x2) 8.23/3.05 8.23/3.05 U3_ga(x1, x2) = U3_ga(x1, x2) 8.23/3.05 8.23/3.05 U4_ga(x1, x2) = U4_ga(x1, x2) 8.23/3.05 8.23/3.05 U5_ga(x1, x2) = U5_ga(x1, x2) 8.23/3.05 8.23/3.05 U6_ga(x1, x2) = U6_ga(x1, x2) 8.23/3.05 8.23/3.05 U7_ga(x1) = U7_ga(x1) 8.23/3.05 8.23/3.05 8.23/3.05 Recursive path order with status [RPO]. 8.23/3.05 Quasi-Precedence: [n_1, U7_ga_1] > [o_2, U3_ga_2, U4_ga_2] > [a_2, U5_ga_2, U6_ga_2] > transform_out_ga_1 > CNFEQUIV_IN_GA_1 > U1_GA_1 8.23/3.05 8.23/3.05 Status: U1_GA_1: multiset status 8.23/3.05 transform_out_ga_1: multiset status 8.23/3.05 CNFEQUIV_IN_GA_1: multiset status 8.23/3.05 n_1: [1] 8.23/3.05 a_2: [2,1] 8.23/3.05 o_2: multiset status 8.23/3.05 U3_ga_2: multiset status 8.23/3.05 U4_ga_2: multiset status 8.23/3.05 U5_ga_2: [1,2] 8.23/3.05 U6_ga_2: [2,1] 8.23/3.05 U7_ga_1: [1] 8.23/3.05 8.23/3.05 8.23/3.05 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.23/3.05 8.23/3.05 transform_in_ga(n(n(X))) -> transform_out_ga(X) 8.23/3.05 transform_in_ga(n(a(X, Y))) -> transform_out_ga(o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y))) -> transform_out_ga(a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z))) -> transform_out_ga(a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z)) -> transform_out_ga(a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y)) -> U3_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(o(X, Y1)) -> U4_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(a(X1, Y)) -> U5_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(a(X, Y1)) -> U6_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(n(X1)) -> U7_ga(transform_in_ga(X1)) 8.23/3.05 U4_ga(X, transform_out_ga(Y2)) -> transform_out_ga(o(X, Y2)) 8.23/3.05 U3_ga(Y, transform_out_ga(X2)) -> transform_out_ga(o(X2, Y)) 8.23/3.05 U5_ga(Y, transform_out_ga(X2)) -> transform_out_ga(a(X2, Y)) 8.23/3.05 U6_ga(X, transform_out_ga(Y2)) -> transform_out_ga(a(X, Y2)) 8.23/3.05 U7_ga(transform_out_ga(X2)) -> transform_out_ga(n(X2)) 8.23/3.05 8.23/3.05 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (20) 8.23/3.05 Obligation: 8.23/3.05 Q DP problem: 8.23/3.05 P is empty. 8.23/3.05 The TRS R consists of the following rules: 8.23/3.05 8.23/3.05 transform_in_ga(n(n(X))) -> transform_out_ga(X) 8.23/3.05 transform_in_ga(n(a(X, Y))) -> transform_out_ga(o(n(X), n(Y))) 8.23/3.05 transform_in_ga(n(o(X, Y))) -> transform_out_ga(a(n(X), n(Y))) 8.23/3.05 transform_in_ga(o(X, a(Y, Z))) -> transform_out_ga(a(o(X, Y), o(X, Z))) 8.23/3.05 transform_in_ga(o(a(X, Y), Z)) -> transform_out_ga(a(o(X, Z), o(Y, Z))) 8.23/3.05 transform_in_ga(o(X1, Y)) -> U3_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(o(X, Y1)) -> U4_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(a(X1, Y)) -> U5_ga(Y, transform_in_ga(X1)) 8.23/3.05 transform_in_ga(a(X, Y1)) -> U6_ga(X, transform_in_ga(Y1)) 8.23/3.05 transform_in_ga(n(X1)) -> U7_ga(transform_in_ga(X1)) 8.23/3.05 U3_ga(Y, transform_out_ga(X2)) -> transform_out_ga(o(X2, Y)) 8.23/3.05 U4_ga(X, transform_out_ga(Y2)) -> transform_out_ga(o(X, Y2)) 8.23/3.05 U5_ga(Y, transform_out_ga(X2)) -> transform_out_ga(a(X2, Y)) 8.23/3.05 U6_ga(X, transform_out_ga(Y2)) -> transform_out_ga(a(X, Y2)) 8.23/3.05 U7_ga(transform_out_ga(X2)) -> transform_out_ga(n(X2)) 8.23/3.05 8.23/3.05 The set Q consists of the following terms: 8.23/3.05 8.23/3.05 transform_in_ga(x0) 8.23/3.05 U3_ga(x0, x1) 8.23/3.05 U4_ga(x0, x1) 8.23/3.05 U5_ga(x0, x1) 8.23/3.05 U6_ga(x0, x1) 8.23/3.05 U7_ga(x0) 8.23/3.05 8.23/3.05 We have to consider all (P,Q,R)-chains. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (21) PisEmptyProof (EQUIVALENT) 8.23/3.05 The TRS P is empty. Hence, there is no (P,Q,R) chain. 8.23/3.05 ---------------------------------------- 8.23/3.05 8.23/3.05 (22) 8.23/3.05 YES 8.44/3.11 EOF