/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern add(a,a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 31 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 46 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 1 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES ---------------------------------------- (0) Obligation: Clauses: add(b, b, b). add(X, b, X) :- binaryZ(X). add(b, Y, Y) :- binaryZ(Y). add(X, Y, Z) :- addz(X, Y, Z). addx(one(X), b, one(X)) :- binary(X). addx(zero(X), b, zero(X)) :- binaryZ(X). addx(X, Y, Z) :- addz(X, Y, Z). addy(b, one(Y), one(Y)) :- binary(Y). addy(b, zero(Y), zero(Y)) :- binaryZ(Y). addy(X, Y, Z) :- addz(X, Y, Z). addz(zero(X), zero(Y), zero(Z)) :- addz(X, Y, Z). addz(zero(X), one(Y), one(Z)) :- addx(X, Y, Z). addz(one(X), zero(Y), one(Z)) :- addy(X, Y, Z). addz(one(X), one(Y), zero(Z)) :- addc(X, Y, Z). addc(b, b, one(b)). addc(X, b, Z) :- succZ(X, Z). addc(b, Y, Z) :- succZ(Y, Z). addc(X, Y, Z) :- addC(X, Y, Z). addX(zero(X), b, one(X)) :- binaryZ(X). addX(one(X), b, zero(Z)) :- succ(X, Z). addX(X, Y, Z) :- addC(X, Y, Z). addY(b, zero(Y), one(Y)) :- binaryZ(Y). addY(b, one(Y), zero(Z)) :- succ(Y, Z). addY(X, Y, Z) :- addC(X, Y, Z). addC(zero(X), zero(Y), one(Z)) :- addz(X, Y, Z). addC(zero(X), one(Y), zero(Z)) :- addX(X, Y, Z). addC(one(X), zero(Y), zero(Z)) :- addY(X, Y, Z). addC(one(X), one(Y), one(Z)) :- addc(X, Y, Z). binary(b). binary(zero(X)) :- binaryZ(X). binary(one(X)) :- binary(X). binaryZ(zero(X)) :- binaryZ(X). binaryZ(one(X)) :- binary(X). succ(b, one(b)). succ(zero(X), one(X)) :- binaryZ(X). succ(one(X), zero(Z)) :- succ(X, Z). succZ(zero(X), one(X)) :- binaryZ(X). succZ(one(X), zero(Z)) :- succ(X, Z). times(one(b), X, X). times(zero(R), S, zero(RS)) :- times(R, S, RS). times(one(R), S, RSS) :- ','(times(R, S, RS), add(S, zero(RS), RSS)). Query: add(a,a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: add_in_3: (f,f,b) binaryZ_in_1: (b) binary_in_1: (b) addz_in_3: (f,f,b) addx_in_3: (f,f,b) addy_in_3: (f,f,b) addc_in_3: (f,f,b) succZ_in_2: (f,b) succ_in_2: (f,b) addC_in_3: (f,f,b) addX_in_3: (f,f,b) addY_in_3: (f,f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: ADD_IN_AAG(X, b, X) -> U1_AAG(X, binaryZ_in_g(X)) ADD_IN_AAG(X, b, X) -> BINARYZ_IN_G(X) BINARYZ_IN_G(zero(X)) -> U29_G(X, binaryZ_in_g(X)) BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARYZ_IN_G(one(X)) -> U30_G(X, binary_in_g(X)) BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) BINARY_IN_G(zero(X)) -> U27_G(X, binaryZ_in_g(X)) BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARY_IN_G(one(X)) -> U28_G(X, binary_in_g(X)) BINARY_IN_G(one(X)) -> BINARY_IN_G(X) ADD_IN_AAG(b, Y, Y) -> U2_AAG(Y, binaryZ_in_g(Y)) ADD_IN_AAG(b, Y, Y) -> BINARYZ_IN_G(Y) ADD_IN_AAG(X, Y, Z) -> U3_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADD_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> U10_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> U11_AAG(X, Y, Z, addx_in_aag(X, Y, Z)) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> ADDX_IN_AAG(X, Y, Z) ADDX_IN_AAG(one(X), b, one(X)) -> U4_AAG(X, binary_in_g(X)) ADDX_IN_AAG(one(X), b, one(X)) -> BINARY_IN_G(X) ADDX_IN_AAG(zero(X), b, zero(X)) -> U5_AAG(X, binaryZ_in_g(X)) ADDX_IN_AAG(zero(X), b, zero(X)) -> BINARYZ_IN_G(X) ADDX_IN_AAG(X, Y, Z) -> U6_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDX_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> U12_AAG(X, Y, Z, addy_in_aag(X, Y, Z)) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> ADDY_IN_AAG(X, Y, Z) ADDY_IN_AAG(b, one(Y), one(Y)) -> U7_AAG(Y, binary_in_g(Y)) ADDY_IN_AAG(b, one(Y), one(Y)) -> BINARY_IN_G(Y) ADDY_IN_AAG(b, zero(Y), zero(Y)) -> U8_AAG(Y, binaryZ_in_g(Y)) ADDY_IN_AAG(b, zero(Y), zero(Y)) -> BINARYZ_IN_G(Y) ADDY_IN_AAG(X, Y, Z) -> U9_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDY_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> U13_AAG(X, Y, Z, addc_in_aag(X, Y, Z)) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> ADDC_IN_AAG(X, Y, Z) ADDC_IN_AAG(X, b, Z) -> U14_AAG(X, Z, succZ_in_ag(X, Z)) ADDC_IN_AAG(X, b, Z) -> SUCCZ_IN_AG(X, Z) SUCCZ_IN_AG(zero(X), one(X)) -> U33_AG(X, binaryZ_in_g(X)) SUCCZ_IN_AG(zero(X), one(X)) -> BINARYZ_IN_G(X) SUCCZ_IN_AG(one(X), zero(Z)) -> U34_AG(X, Z, succ_in_ag(X, Z)) SUCCZ_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) SUCC_IN_AG(zero(X), one(X)) -> U31_AG(X, binaryZ_in_g(X)) SUCC_IN_AG(zero(X), one(X)) -> BINARYZ_IN_G(X) SUCC_IN_AG(one(X), zero(Z)) -> U32_AG(X, Z, succ_in_ag(X, Z)) SUCC_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) ADDC_IN_AAG(b, Y, Z) -> U15_AAG(Y, Z, succZ_in_ag(Y, Z)) ADDC_IN_AAG(b, Y, Z) -> SUCCZ_IN_AG(Y, Z) ADDC_IN_AAG(X, Y, Z) -> U16_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDC_IN_AAG(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> U23_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> U24_AAG(X, Y, Z, addX_in_aag(X, Y, Z)) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> ADDX_IN_AAG^1(X, Y, Z) ADDX_IN_AAG^1(zero(X), b, one(X)) -> U17_AAG(X, binaryZ_in_g(X)) ADDX_IN_AAG^1(zero(X), b, one(X)) -> BINARYZ_IN_G(X) ADDX_IN_AAG^1(one(X), b, zero(Z)) -> U18_AAG(X, Z, succ_in_ag(X, Z)) ADDX_IN_AAG^1(one(X), b, zero(Z)) -> SUCC_IN_AG(X, Z) ADDX_IN_AAG^1(X, Y, Z) -> U19_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDX_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> U25_AAG(X, Y, Z, addY_in_aag(X, Y, Z)) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> ADDY_IN_AAG^1(X, Y, Z) ADDY_IN_AAG^1(b, zero(Y), one(Y)) -> U20_AAG(Y, binaryZ_in_g(Y)) ADDY_IN_AAG^1(b, zero(Y), one(Y)) -> BINARYZ_IN_G(Y) ADDY_IN_AAG^1(b, one(Y), zero(Z)) -> U21_AAG(Y, Z, succ_in_ag(Y, Z)) ADDY_IN_AAG^1(b, one(Y), zero(Z)) -> SUCC_IN_AG(Y, Z) ADDY_IN_AAG^1(X, Y, Z) -> U22_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDY_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> U26_AAG(X, Y, Z, addc_in_aag(X, Y, Z)) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> ADDC_IN_AAG(X, Y, Z) The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) ADD_IN_AAG(x1, x2, x3) = ADD_IN_AAG(x3) U1_AAG(x1, x2) = U1_AAG(x1, x2) BINARYZ_IN_G(x1) = BINARYZ_IN_G(x1) U29_G(x1, x2) = U29_G(x2) U30_G(x1, x2) = U30_G(x2) BINARY_IN_G(x1) = BINARY_IN_G(x1) U27_G(x1, x2) = U27_G(x2) U28_G(x1, x2) = U28_G(x2) U2_AAG(x1, x2) = U2_AAG(x1, x2) U3_AAG(x1, x2, x3, x4) = U3_AAG(x4) ADDZ_IN_AAG(x1, x2, x3) = ADDZ_IN_AAG(x3) U10_AAG(x1, x2, x3, x4) = U10_AAG(x4) U11_AAG(x1, x2, x3, x4) = U11_AAG(x4) ADDX_IN_AAG(x1, x2, x3) = ADDX_IN_AAG(x3) U4_AAG(x1, x2) = U4_AAG(x1, x2) U5_AAG(x1, x2) = U5_AAG(x1, x2) U6_AAG(x1, x2, x3, x4) = U6_AAG(x4) U12_AAG(x1, x2, x3, x4) = U12_AAG(x4) ADDY_IN_AAG(x1, x2, x3) = ADDY_IN_AAG(x3) U7_AAG(x1, x2) = U7_AAG(x1, x2) U8_AAG(x1, x2) = U8_AAG(x1, x2) U9_AAG(x1, x2, x3, x4) = U9_AAG(x4) U13_AAG(x1, x2, x3, x4) = U13_AAG(x4) ADDC_IN_AAG(x1, x2, x3) = ADDC_IN_AAG(x3) U14_AAG(x1, x2, x3) = U14_AAG(x3) SUCCZ_IN_AG(x1, x2) = SUCCZ_IN_AG(x2) U33_AG(x1, x2) = U33_AG(x1, x2) U34_AG(x1, x2, x3) = U34_AG(x3) SUCC_IN_AG(x1, x2) = SUCC_IN_AG(x2) U31_AG(x1, x2) = U31_AG(x1, x2) U32_AG(x1, x2, x3) = U32_AG(x3) U15_AAG(x1, x2, x3) = U15_AAG(x3) U16_AAG(x1, x2, x3, x4) = U16_AAG(x4) ADDC_IN_AAG^1(x1, x2, x3) = ADDC_IN_AAG^1(x3) U23_AAG(x1, x2, x3, x4) = U23_AAG(x4) U24_AAG(x1, x2, x3, x4) = U24_AAG(x4) ADDX_IN_AAG^1(x1, x2, x3) = ADDX_IN_AAG^1(x3) U17_AAG(x1, x2) = U17_AAG(x1, x2) U18_AAG(x1, x2, x3) = U18_AAG(x3) U19_AAG(x1, x2, x3, x4) = U19_AAG(x4) U25_AAG(x1, x2, x3, x4) = U25_AAG(x4) ADDY_IN_AAG^1(x1, x2, x3) = ADDY_IN_AAG^1(x3) U20_AAG(x1, x2) = U20_AAG(x1, x2) U21_AAG(x1, x2, x3) = U21_AAG(x3) U22_AAG(x1, x2, x3, x4) = U22_AAG(x4) U26_AAG(x1, x2, x3, x4) = U26_AAG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: ADD_IN_AAG(X, b, X) -> U1_AAG(X, binaryZ_in_g(X)) ADD_IN_AAG(X, b, X) -> BINARYZ_IN_G(X) BINARYZ_IN_G(zero(X)) -> U29_G(X, binaryZ_in_g(X)) BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARYZ_IN_G(one(X)) -> U30_G(X, binary_in_g(X)) BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) BINARY_IN_G(zero(X)) -> U27_G(X, binaryZ_in_g(X)) BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARY_IN_G(one(X)) -> U28_G(X, binary_in_g(X)) BINARY_IN_G(one(X)) -> BINARY_IN_G(X) ADD_IN_AAG(b, Y, Y) -> U2_AAG(Y, binaryZ_in_g(Y)) ADD_IN_AAG(b, Y, Y) -> BINARYZ_IN_G(Y) ADD_IN_AAG(X, Y, Z) -> U3_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADD_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> U10_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> U11_AAG(X, Y, Z, addx_in_aag(X, Y, Z)) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> ADDX_IN_AAG(X, Y, Z) ADDX_IN_AAG(one(X), b, one(X)) -> U4_AAG(X, binary_in_g(X)) ADDX_IN_AAG(one(X), b, one(X)) -> BINARY_IN_G(X) ADDX_IN_AAG(zero(X), b, zero(X)) -> U5_AAG(X, binaryZ_in_g(X)) ADDX_IN_AAG(zero(X), b, zero(X)) -> BINARYZ_IN_G(X) ADDX_IN_AAG(X, Y, Z) -> U6_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDX_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> U12_AAG(X, Y, Z, addy_in_aag(X, Y, Z)) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> ADDY_IN_AAG(X, Y, Z) ADDY_IN_AAG(b, one(Y), one(Y)) -> U7_AAG(Y, binary_in_g(Y)) ADDY_IN_AAG(b, one(Y), one(Y)) -> BINARY_IN_G(Y) ADDY_IN_AAG(b, zero(Y), zero(Y)) -> U8_AAG(Y, binaryZ_in_g(Y)) ADDY_IN_AAG(b, zero(Y), zero(Y)) -> BINARYZ_IN_G(Y) ADDY_IN_AAG(X, Y, Z) -> U9_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDY_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> U13_AAG(X, Y, Z, addc_in_aag(X, Y, Z)) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> ADDC_IN_AAG(X, Y, Z) ADDC_IN_AAG(X, b, Z) -> U14_AAG(X, Z, succZ_in_ag(X, Z)) ADDC_IN_AAG(X, b, Z) -> SUCCZ_IN_AG(X, Z) SUCCZ_IN_AG(zero(X), one(X)) -> U33_AG(X, binaryZ_in_g(X)) SUCCZ_IN_AG(zero(X), one(X)) -> BINARYZ_IN_G(X) SUCCZ_IN_AG(one(X), zero(Z)) -> U34_AG(X, Z, succ_in_ag(X, Z)) SUCCZ_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) SUCC_IN_AG(zero(X), one(X)) -> U31_AG(X, binaryZ_in_g(X)) SUCC_IN_AG(zero(X), one(X)) -> BINARYZ_IN_G(X) SUCC_IN_AG(one(X), zero(Z)) -> U32_AG(X, Z, succ_in_ag(X, Z)) SUCC_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) ADDC_IN_AAG(b, Y, Z) -> U15_AAG(Y, Z, succZ_in_ag(Y, Z)) ADDC_IN_AAG(b, Y, Z) -> SUCCZ_IN_AG(Y, Z) ADDC_IN_AAG(X, Y, Z) -> U16_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDC_IN_AAG(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> U23_AAG(X, Y, Z, addz_in_aag(X, Y, Z)) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> U24_AAG(X, Y, Z, addX_in_aag(X, Y, Z)) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> ADDX_IN_AAG^1(X, Y, Z) ADDX_IN_AAG^1(zero(X), b, one(X)) -> U17_AAG(X, binaryZ_in_g(X)) ADDX_IN_AAG^1(zero(X), b, one(X)) -> BINARYZ_IN_G(X) ADDX_IN_AAG^1(one(X), b, zero(Z)) -> U18_AAG(X, Z, succ_in_ag(X, Z)) ADDX_IN_AAG^1(one(X), b, zero(Z)) -> SUCC_IN_AG(X, Z) ADDX_IN_AAG^1(X, Y, Z) -> U19_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDX_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> U25_AAG(X, Y, Z, addY_in_aag(X, Y, Z)) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> ADDY_IN_AAG^1(X, Y, Z) ADDY_IN_AAG^1(b, zero(Y), one(Y)) -> U20_AAG(Y, binaryZ_in_g(Y)) ADDY_IN_AAG^1(b, zero(Y), one(Y)) -> BINARYZ_IN_G(Y) ADDY_IN_AAG^1(b, one(Y), zero(Z)) -> U21_AAG(Y, Z, succ_in_ag(Y, Z)) ADDY_IN_AAG^1(b, one(Y), zero(Z)) -> SUCC_IN_AG(Y, Z) ADDY_IN_AAG^1(X, Y, Z) -> U22_AAG(X, Y, Z, addC_in_aag(X, Y, Z)) ADDY_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> U26_AAG(X, Y, Z, addc_in_aag(X, Y, Z)) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> ADDC_IN_AAG(X, Y, Z) The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) ADD_IN_AAG(x1, x2, x3) = ADD_IN_AAG(x3) U1_AAG(x1, x2) = U1_AAG(x1, x2) BINARYZ_IN_G(x1) = BINARYZ_IN_G(x1) U29_G(x1, x2) = U29_G(x2) U30_G(x1, x2) = U30_G(x2) BINARY_IN_G(x1) = BINARY_IN_G(x1) U27_G(x1, x2) = U27_G(x2) U28_G(x1, x2) = U28_G(x2) U2_AAG(x1, x2) = U2_AAG(x1, x2) U3_AAG(x1, x2, x3, x4) = U3_AAG(x4) ADDZ_IN_AAG(x1, x2, x3) = ADDZ_IN_AAG(x3) U10_AAG(x1, x2, x3, x4) = U10_AAG(x4) U11_AAG(x1, x2, x3, x4) = U11_AAG(x4) ADDX_IN_AAG(x1, x2, x3) = ADDX_IN_AAG(x3) U4_AAG(x1, x2) = U4_AAG(x1, x2) U5_AAG(x1, x2) = U5_AAG(x1, x2) U6_AAG(x1, x2, x3, x4) = U6_AAG(x4) U12_AAG(x1, x2, x3, x4) = U12_AAG(x4) ADDY_IN_AAG(x1, x2, x3) = ADDY_IN_AAG(x3) U7_AAG(x1, x2) = U7_AAG(x1, x2) U8_AAG(x1, x2) = U8_AAG(x1, x2) U9_AAG(x1, x2, x3, x4) = U9_AAG(x4) U13_AAG(x1, x2, x3, x4) = U13_AAG(x4) ADDC_IN_AAG(x1, x2, x3) = ADDC_IN_AAG(x3) U14_AAG(x1, x2, x3) = U14_AAG(x3) SUCCZ_IN_AG(x1, x2) = SUCCZ_IN_AG(x2) U33_AG(x1, x2) = U33_AG(x1, x2) U34_AG(x1, x2, x3) = U34_AG(x3) SUCC_IN_AG(x1, x2) = SUCC_IN_AG(x2) U31_AG(x1, x2) = U31_AG(x1, x2) U32_AG(x1, x2, x3) = U32_AG(x3) U15_AAG(x1, x2, x3) = U15_AAG(x3) U16_AAG(x1, x2, x3, x4) = U16_AAG(x4) ADDC_IN_AAG^1(x1, x2, x3) = ADDC_IN_AAG^1(x3) U23_AAG(x1, x2, x3, x4) = U23_AAG(x4) U24_AAG(x1, x2, x3, x4) = U24_AAG(x4) ADDX_IN_AAG^1(x1, x2, x3) = ADDX_IN_AAG^1(x3) U17_AAG(x1, x2) = U17_AAG(x1, x2) U18_AAG(x1, x2, x3) = U18_AAG(x3) U19_AAG(x1, x2, x3, x4) = U19_AAG(x4) U25_AAG(x1, x2, x3, x4) = U25_AAG(x4) ADDY_IN_AAG^1(x1, x2, x3) = ADDY_IN_AAG^1(x3) U20_AAG(x1, x2) = U20_AAG(x1, x2) U21_AAG(x1, x2, x3) = U21_AAG(x3) U22_AAG(x1, x2, x3, x4) = U22_AAG(x4) U26_AAG(x1, x2, x3, x4) = U26_AAG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 50 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARY_IN_G(one(X)) -> BINARY_IN_G(X) The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) BINARYZ_IN_G(x1) = BINARYZ_IN_G(x1) BINARY_IN_G(x1) = BINARY_IN_G(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARY_IN_G(one(X)) -> BINARY_IN_G(X) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) BINARY_IN_G(one(X)) -> BINARY_IN_G(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *BINARY_IN_G(zero(X)) -> BINARYZ_IN_G(X) The graph contains the following edges 1 > 1 *BINARY_IN_G(one(X)) -> BINARY_IN_G(X) The graph contains the following edges 1 > 1 *BINARYZ_IN_G(zero(X)) -> BINARYZ_IN_G(X) The graph contains the following edges 1 > 1 *BINARYZ_IN_G(one(X)) -> BINARY_IN_G(X) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: SUCC_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) SUCC_IN_AG(x1, x2) = SUCC_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: SUCC_IN_AG(one(X), zero(Z)) -> SUCC_IN_AG(X, Z) R is empty. The argument filtering Pi contains the following mapping: zero(x1) = zero(x1) one(x1) = one(x1) SUCC_IN_AG(x1, x2) = SUCC_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: SUCC_IN_AG(zero(Z)) -> SUCC_IN_AG(Z) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *SUCC_IN_AG(zero(Z)) -> SUCC_IN_AG(Z) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDX_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> ADDX_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> ADDY_IN_AAG(X, Y, Z) ADDY_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> ADDC_IN_AAG(X, Y, Z) ADDC_IN_AAG(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> ADDX_IN_AAG^1(X, Y, Z) ADDX_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> ADDY_IN_AAG^1(X, Y, Z) ADDY_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> ADDC_IN_AAG(X, Y, Z) The TRS R consists of the following rules: add_in_aag(b, b, b) -> add_out_aag(b, b, b) add_in_aag(X, b, X) -> U1_aag(X, binaryZ_in_g(X)) binaryZ_in_g(zero(X)) -> U29_g(X, binaryZ_in_g(X)) binaryZ_in_g(one(X)) -> U30_g(X, binary_in_g(X)) binary_in_g(b) -> binary_out_g(b) binary_in_g(zero(X)) -> U27_g(X, binaryZ_in_g(X)) U27_g(X, binaryZ_out_g(X)) -> binary_out_g(zero(X)) binary_in_g(one(X)) -> U28_g(X, binary_in_g(X)) U28_g(X, binary_out_g(X)) -> binary_out_g(one(X)) U30_g(X, binary_out_g(X)) -> binaryZ_out_g(one(X)) U29_g(X, binaryZ_out_g(X)) -> binaryZ_out_g(zero(X)) U1_aag(X, binaryZ_out_g(X)) -> add_out_aag(X, b, X) add_in_aag(b, Y, Y) -> U2_aag(Y, binaryZ_in_g(Y)) U2_aag(Y, binaryZ_out_g(Y)) -> add_out_aag(b, Y, Y) add_in_aag(X, Y, Z) -> U3_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), zero(Y), zero(Z)) -> U10_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(zero(X), one(Y), one(Z)) -> U11_aag(X, Y, Z, addx_in_aag(X, Y, Z)) addx_in_aag(one(X), b, one(X)) -> U4_aag(X, binary_in_g(X)) U4_aag(X, binary_out_g(X)) -> addx_out_aag(one(X), b, one(X)) addx_in_aag(zero(X), b, zero(X)) -> U5_aag(X, binaryZ_in_g(X)) U5_aag(X, binaryZ_out_g(X)) -> addx_out_aag(zero(X), b, zero(X)) addx_in_aag(X, Y, Z) -> U6_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), zero(Y), one(Z)) -> U12_aag(X, Y, Z, addy_in_aag(X, Y, Z)) addy_in_aag(b, one(Y), one(Y)) -> U7_aag(Y, binary_in_g(Y)) U7_aag(Y, binary_out_g(Y)) -> addy_out_aag(b, one(Y), one(Y)) addy_in_aag(b, zero(Y), zero(Y)) -> U8_aag(Y, binaryZ_in_g(Y)) U8_aag(Y, binaryZ_out_g(Y)) -> addy_out_aag(b, zero(Y), zero(Y)) addy_in_aag(X, Y, Z) -> U9_aag(X, Y, Z, addz_in_aag(X, Y, Z)) addz_in_aag(one(X), one(Y), zero(Z)) -> U13_aag(X, Y, Z, addc_in_aag(X, Y, Z)) addc_in_aag(b, b, one(b)) -> addc_out_aag(b, b, one(b)) addc_in_aag(X, b, Z) -> U14_aag(X, Z, succZ_in_ag(X, Z)) succZ_in_ag(zero(X), one(X)) -> U33_ag(X, binaryZ_in_g(X)) U33_ag(X, binaryZ_out_g(X)) -> succZ_out_ag(zero(X), one(X)) succZ_in_ag(one(X), zero(Z)) -> U34_ag(X, Z, succ_in_ag(X, Z)) succ_in_ag(b, one(b)) -> succ_out_ag(b, one(b)) succ_in_ag(zero(X), one(X)) -> U31_ag(X, binaryZ_in_g(X)) U31_ag(X, binaryZ_out_g(X)) -> succ_out_ag(zero(X), one(X)) succ_in_ag(one(X), zero(Z)) -> U32_ag(X, Z, succ_in_ag(X, Z)) U32_ag(X, Z, succ_out_ag(X, Z)) -> succ_out_ag(one(X), zero(Z)) U34_ag(X, Z, succ_out_ag(X, Z)) -> succZ_out_ag(one(X), zero(Z)) U14_aag(X, Z, succZ_out_ag(X, Z)) -> addc_out_aag(X, b, Z) addc_in_aag(b, Y, Z) -> U15_aag(Y, Z, succZ_in_ag(Y, Z)) U15_aag(Y, Z, succZ_out_ag(Y, Z)) -> addc_out_aag(b, Y, Z) addc_in_aag(X, Y, Z) -> U16_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(zero(X), zero(Y), one(Z)) -> U23_aag(X, Y, Z, addz_in_aag(X, Y, Z)) U23_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), zero(Y), one(Z)) addC_in_aag(zero(X), one(Y), zero(Z)) -> U24_aag(X, Y, Z, addX_in_aag(X, Y, Z)) addX_in_aag(zero(X), b, one(X)) -> U17_aag(X, binaryZ_in_g(X)) U17_aag(X, binaryZ_out_g(X)) -> addX_out_aag(zero(X), b, one(X)) addX_in_aag(one(X), b, zero(Z)) -> U18_aag(X, Z, succ_in_ag(X, Z)) U18_aag(X, Z, succ_out_ag(X, Z)) -> addX_out_aag(one(X), b, zero(Z)) addX_in_aag(X, Y, Z) -> U19_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), zero(Y), zero(Z)) -> U25_aag(X, Y, Z, addY_in_aag(X, Y, Z)) addY_in_aag(b, zero(Y), one(Y)) -> U20_aag(Y, binaryZ_in_g(Y)) U20_aag(Y, binaryZ_out_g(Y)) -> addY_out_aag(b, zero(Y), one(Y)) addY_in_aag(b, one(Y), zero(Z)) -> U21_aag(Y, Z, succ_in_ag(Y, Z)) U21_aag(Y, Z, succ_out_ag(Y, Z)) -> addY_out_aag(b, one(Y), zero(Z)) addY_in_aag(X, Y, Z) -> U22_aag(X, Y, Z, addC_in_aag(X, Y, Z)) addC_in_aag(one(X), one(Y), one(Z)) -> U26_aag(X, Y, Z, addc_in_aag(X, Y, Z)) U26_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addC_out_aag(one(X), one(Y), one(Z)) U22_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addY_out_aag(X, Y, Z) U25_aag(X, Y, Z, addY_out_aag(X, Y, Z)) -> addC_out_aag(one(X), zero(Y), zero(Z)) U19_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addX_out_aag(X, Y, Z) U24_aag(X, Y, Z, addX_out_aag(X, Y, Z)) -> addC_out_aag(zero(X), one(Y), zero(Z)) U16_aag(X, Y, Z, addC_out_aag(X, Y, Z)) -> addc_out_aag(X, Y, Z) U13_aag(X, Y, Z, addc_out_aag(X, Y, Z)) -> addz_out_aag(one(X), one(Y), zero(Z)) U9_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addy_out_aag(X, Y, Z) U12_aag(X, Y, Z, addy_out_aag(X, Y, Z)) -> addz_out_aag(one(X), zero(Y), one(Z)) U6_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addx_out_aag(X, Y, Z) U11_aag(X, Y, Z, addx_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), one(Y), one(Z)) U10_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> addz_out_aag(zero(X), zero(Y), zero(Z)) U3_aag(X, Y, Z, addz_out_aag(X, Y, Z)) -> add_out_aag(X, Y, Z) The argument filtering Pi contains the following mapping: add_in_aag(x1, x2, x3) = add_in_aag(x3) b = b add_out_aag(x1, x2, x3) = add_out_aag(x1, x2) U1_aag(x1, x2) = U1_aag(x1, x2) binaryZ_in_g(x1) = binaryZ_in_g(x1) zero(x1) = zero(x1) U29_g(x1, x2) = U29_g(x2) one(x1) = one(x1) U30_g(x1, x2) = U30_g(x2) binary_in_g(x1) = binary_in_g(x1) binary_out_g(x1) = binary_out_g U27_g(x1, x2) = U27_g(x2) binaryZ_out_g(x1) = binaryZ_out_g U28_g(x1, x2) = U28_g(x2) U2_aag(x1, x2) = U2_aag(x1, x2) U3_aag(x1, x2, x3, x4) = U3_aag(x4) addz_in_aag(x1, x2, x3) = addz_in_aag(x3) U10_aag(x1, x2, x3, x4) = U10_aag(x4) U11_aag(x1, x2, x3, x4) = U11_aag(x4) addx_in_aag(x1, x2, x3) = addx_in_aag(x3) U4_aag(x1, x2) = U4_aag(x1, x2) addx_out_aag(x1, x2, x3) = addx_out_aag(x1, x2) U5_aag(x1, x2) = U5_aag(x1, x2) U6_aag(x1, x2, x3, x4) = U6_aag(x4) U12_aag(x1, x2, x3, x4) = U12_aag(x4) addy_in_aag(x1, x2, x3) = addy_in_aag(x3) U7_aag(x1, x2) = U7_aag(x1, x2) addy_out_aag(x1, x2, x3) = addy_out_aag(x1, x2) U8_aag(x1, x2) = U8_aag(x1, x2) U9_aag(x1, x2, x3, x4) = U9_aag(x4) U13_aag(x1, x2, x3, x4) = U13_aag(x4) addc_in_aag(x1, x2, x3) = addc_in_aag(x3) addc_out_aag(x1, x2, x3) = addc_out_aag(x1, x2) U14_aag(x1, x2, x3) = U14_aag(x3) succZ_in_ag(x1, x2) = succZ_in_ag(x2) U33_ag(x1, x2) = U33_ag(x1, x2) succZ_out_ag(x1, x2) = succZ_out_ag(x1) U34_ag(x1, x2, x3) = U34_ag(x3) succ_in_ag(x1, x2) = succ_in_ag(x2) succ_out_ag(x1, x2) = succ_out_ag(x1) U31_ag(x1, x2) = U31_ag(x1, x2) U32_ag(x1, x2, x3) = U32_ag(x3) U15_aag(x1, x2, x3) = U15_aag(x3) U16_aag(x1, x2, x3, x4) = U16_aag(x4) addC_in_aag(x1, x2, x3) = addC_in_aag(x3) U23_aag(x1, x2, x3, x4) = U23_aag(x4) addz_out_aag(x1, x2, x3) = addz_out_aag(x1, x2) addC_out_aag(x1, x2, x3) = addC_out_aag(x1, x2) U24_aag(x1, x2, x3, x4) = U24_aag(x4) addX_in_aag(x1, x2, x3) = addX_in_aag(x3) U17_aag(x1, x2) = U17_aag(x1, x2) addX_out_aag(x1, x2, x3) = addX_out_aag(x1, x2) U18_aag(x1, x2, x3) = U18_aag(x3) U19_aag(x1, x2, x3, x4) = U19_aag(x4) U25_aag(x1, x2, x3, x4) = U25_aag(x4) addY_in_aag(x1, x2, x3) = addY_in_aag(x3) U20_aag(x1, x2) = U20_aag(x1, x2) addY_out_aag(x1, x2, x3) = addY_out_aag(x1, x2) U21_aag(x1, x2, x3) = U21_aag(x3) U22_aag(x1, x2, x3, x4) = U22_aag(x4) U26_aag(x1, x2, x3, x4) = U26_aag(x4) ADDZ_IN_AAG(x1, x2, x3) = ADDZ_IN_AAG(x3) ADDX_IN_AAG(x1, x2, x3) = ADDX_IN_AAG(x3) ADDY_IN_AAG(x1, x2, x3) = ADDY_IN_AAG(x3) ADDC_IN_AAG(x1, x2, x3) = ADDC_IN_AAG(x3) ADDC_IN_AAG^1(x1, x2, x3) = ADDC_IN_AAG^1(x3) ADDX_IN_AAG^1(x1, x2, x3) = ADDX_IN_AAG^1(x3) ADDY_IN_AAG^1(x1, x2, x3) = ADDY_IN_AAG^1(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDX_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), zero(Y), zero(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(zero(X), one(Y), one(Z)) -> ADDX_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), zero(Y), one(Z)) -> ADDY_IN_AAG(X, Y, Z) ADDY_IN_AAG(X, Y, Z) -> ADDZ_IN_AAG(X, Y, Z) ADDZ_IN_AAG(one(X), one(Y), zero(Z)) -> ADDC_IN_AAG(X, Y, Z) ADDC_IN_AAG(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(zero(X), zero(Y), one(Z)) -> ADDZ_IN_AAG(X, Y, Z) ADDC_IN_AAG^1(zero(X), one(Y), zero(Z)) -> ADDX_IN_AAG^1(X, Y, Z) ADDX_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), zero(Y), zero(Z)) -> ADDY_IN_AAG^1(X, Y, Z) ADDY_IN_AAG^1(X, Y, Z) -> ADDC_IN_AAG^1(X, Y, Z) ADDC_IN_AAG^1(one(X), one(Y), one(Z)) -> ADDC_IN_AAG(X, Y, Z) R is empty. The argument filtering Pi contains the following mapping: zero(x1) = zero(x1) one(x1) = one(x1) ADDZ_IN_AAG(x1, x2, x3) = ADDZ_IN_AAG(x3) ADDX_IN_AAG(x1, x2, x3) = ADDX_IN_AAG(x3) ADDY_IN_AAG(x1, x2, x3) = ADDY_IN_AAG(x3) ADDC_IN_AAG(x1, x2, x3) = ADDC_IN_AAG(x3) ADDC_IN_AAG^1(x1, x2, x3) = ADDC_IN_AAG^1(x3) ADDX_IN_AAG^1(x1, x2, x3) = ADDX_IN_AAG^1(x3) ADDY_IN_AAG^1(x1, x2, x3) = ADDY_IN_AAG^1(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: ADDX_IN_AAG(Z) -> ADDZ_IN_AAG(Z) ADDZ_IN_AAG(zero(Z)) -> ADDZ_IN_AAG(Z) ADDZ_IN_AAG(one(Z)) -> ADDX_IN_AAG(Z) ADDZ_IN_AAG(one(Z)) -> ADDY_IN_AAG(Z) ADDY_IN_AAG(Z) -> ADDZ_IN_AAG(Z) ADDZ_IN_AAG(zero(Z)) -> ADDC_IN_AAG(Z) ADDC_IN_AAG(Z) -> ADDC_IN_AAG^1(Z) ADDC_IN_AAG^1(one(Z)) -> ADDZ_IN_AAG(Z) ADDC_IN_AAG^1(zero(Z)) -> ADDX_IN_AAG^1(Z) ADDX_IN_AAG^1(Z) -> ADDC_IN_AAG^1(Z) ADDC_IN_AAG^1(zero(Z)) -> ADDY_IN_AAG^1(Z) ADDY_IN_AAG^1(Z) -> ADDC_IN_AAG^1(Z) ADDC_IN_AAG^1(one(Z)) -> ADDC_IN_AAG(Z) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *ADDZ_IN_AAG(one(Z)) -> ADDX_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDZ_IN_AAG(zero(Z)) -> ADDZ_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDX_IN_AAG(Z) -> ADDZ_IN_AAG(Z) The graph contains the following edges 1 >= 1 *ADDY_IN_AAG(Z) -> ADDZ_IN_AAG(Z) The graph contains the following edges 1 >= 1 *ADDC_IN_AAG^1(one(Z)) -> ADDZ_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDZ_IN_AAG(one(Z)) -> ADDY_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDZ_IN_AAG(zero(Z)) -> ADDC_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDC_IN_AAG(Z) -> ADDC_IN_AAG^1(Z) The graph contains the following edges 1 >= 1 *ADDC_IN_AAG^1(one(Z)) -> ADDC_IN_AAG(Z) The graph contains the following edges 1 > 1 *ADDX_IN_AAG^1(Z) -> ADDC_IN_AAG^1(Z) The graph contains the following edges 1 >= 1 *ADDY_IN_AAG^1(Z) -> ADDC_IN_AAG^1(Z) The graph contains the following edges 1 >= 1 *ADDC_IN_AAG^1(zero(Z)) -> ADDX_IN_AAG^1(Z) The graph contains the following edges 1 > 1 *ADDC_IN_AAG^1(zero(Z)) -> ADDY_IN_AAG^1(Z) The graph contains the following edges 1 > 1 ---------------------------------------- (27) YES