4.87/2.20 YES 4.87/2.21 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.87/2.21 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.87/2.21 4.87/2.21 4.87/2.21 Left Termination of the query pattern 4.87/2.21 4.87/2.21 balance(g,a) 4.87/2.21 4.87/2.21 w.r.t. the given Prolog program could successfully be proven: 4.87/2.21 4.87/2.21 (0) Prolog 4.87/2.21 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.87/2.21 (2) PiTRS 4.87/2.21 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.87/2.21 (4) PiDP 4.87/2.21 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.87/2.21 (6) AND 4.87/2.21 (7) PiDP 4.87/2.21 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.87/2.21 (9) PiDP 4.87/2.21 (10) PiDPToQDPProof [SOUND, 9 ms] 4.87/2.21 (11) QDP 4.87/2.21 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.87/2.21 (13) YES 4.87/2.21 (14) PiDP 4.87/2.21 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.87/2.21 (16) PiDP 4.87/2.21 (17) PiDPToQDPProof [SOUND, 0 ms] 4.87/2.21 (18) QDP 4.87/2.21 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.87/2.21 (20) YES 4.87/2.21 4.87/2.21 4.87/2.21 ---------------------------------------- 4.87/2.21 4.87/2.21 (0) 4.87/2.21 Obligation: 4.87/2.21 Clauses: 4.87/2.21 4.87/2.21 balance(T, TB) :- balance55(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, []). 4.87/2.21 balance55(nil, C, T, T, A, B, A, B, X, X). 4.87/2.21 balance55(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) :- ','(balance55(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)), balance55(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)). 4.87/2.21 balance5(nil, C, T, T, A, B, A, B, X, X) :- balance55(nil, C, T, T, A, B, A, B, X, X). 4.87/2.21 balance5(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) :- balance55(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT). 4.87/2.21 balance(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) :- balance5(nil, C, T, T, A, B, A, B, X, X). 4.87/2.21 balance(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(.(','(nil, -(XX0, XX0)), XX1), NT)) :- balance5(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT). 4.87/2.21 4.87/2.21 4.87/2.21 Query: balance(g,a) 4.87/2.21 ---------------------------------------- 4.87/2.21 4.87/2.21 (1) PrologToPiTRSProof (SOUND) 4.87/2.21 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.87/2.21 4.87/2.21 balance_in_2: (b,f) 4.87/2.21 4.87/2.21 balance55_in_10: (b,f,f,b,f,b,f,f,f,b) (b,f,f,f,f,f,f,f,f,f) 4.87/2.21 4.87/2.21 Transforming Prolog into the following Term Rewriting System: 4.87/2.21 4.87/2.21 Pi-finite rewrite system: 4.87/2.21 The TRS R consists of the following rules: 4.87/2.21 4.87/2.21 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.21 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.21 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.21 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.21 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.21 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.21 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.21 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.21 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.21 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.21 4.87/2.21 The argument filtering Pi contains the following mapping: 4.87/2.21 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.21 4.87/2.21 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.21 4.87/2.21 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.21 4.87/2.21 nil = nil 4.87/2.21 4.87/2.21 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.21 4.87/2.21 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.21 4.87/2.21 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.21 4.87/2.21 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.21 4.87/2.21 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.21 4.87/2.21 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.21 4.87/2.21 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.21 4.87/2.21 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.21 4.87/2.21 [] = [] 4.87/2.21 4.87/2.21 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.21 4.87/2.21 4.87/2.21 4.87/2.21 4.87/2.21 4.87/2.21 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.87/2.21 4.87/2.21 4.87/2.21 4.87/2.21 ---------------------------------------- 4.87/2.21 4.87/2.21 (2) 4.87/2.21 Obligation: 4.87/2.21 Pi-finite rewrite system: 4.87/2.21 The TRS R consists of the following rules: 4.87/2.21 4.87/2.21 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.21 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.21 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.21 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.21 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.21 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.21 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.23 4.87/2.23 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.23 4.87/2.23 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.23 4.87/2.23 [] = [] 4.87/2.23 4.87/2.23 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.23 4.87/2.23 4.87/2.23 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (3) DependencyPairsProof (EQUIVALENT) 4.87/2.23 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 BALANCE_IN_GA(T, TB) -> U1_GA(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 BALANCE_IN_GA(T, TB) -> BALANCE55_IN_GAAGAGAAAG(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, []) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAAAAAAAA(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAGAGAAAG(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.23 4.87/2.23 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.23 4.87/2.23 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.23 4.87/2.23 [] = [] 4.87/2.23 4.87/2.23 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.23 4.87/2.23 BALANCE_IN_GA(x1, x2) = BALANCE_IN_GA(x1) 4.87/2.23 4.87/2.23 U1_GA(x1, x2, x3) = U1_GA(x3) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAGAGAAAG(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAGAGAAAG(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAAAAAAAA(x1) 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAAAAAAAA(x3, x19) 4.87/2.23 4.87/2.23 U3_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_GAAAAAAAAA(x19) 4.87/2.23 4.87/2.23 U3_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_GAAGAGAAAG(x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (4) 4.87/2.23 Obligation: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 BALANCE_IN_GA(T, TB) -> U1_GA(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 BALANCE_IN_GA(T, TB) -> BALANCE55_IN_GAAGAGAAAG(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, []) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAAAAAAAA(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAGAGAAAG(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.23 4.87/2.23 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.23 4.87/2.23 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.23 4.87/2.23 [] = [] 4.87/2.23 4.87/2.23 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.23 4.87/2.23 BALANCE_IN_GA(x1, x2) = BALANCE_IN_GA(x1) 4.87/2.23 4.87/2.23 U1_GA(x1, x2, x3) = U1_GA(x3) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAGAGAAAG(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAGAGAAAG(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAAAAAAAA(x1) 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAAAAAAAA(x3, x19) 4.87/2.23 4.87/2.23 U3_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_GAAAAAAAAA(x19) 4.87/2.23 4.87/2.23 U3_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_GAAGAGAAAG(x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (5) DependencyGraphProof (EQUIVALENT) 4.87/2.23 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (6) 4.87/2.23 Complex Obligation (AND) 4.87/2.23 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (7) 4.87/2.23 Obligation: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAAAAAAAA(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.23 4.87/2.23 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.23 4.87/2.23 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.23 4.87/2.23 [] = [] 4.87/2.23 4.87/2.23 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAAAAAAAA(x1) 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAAAAAAAA(x3, x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (8) UsableRulesProof (EQUIVALENT) 4.87/2.23 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (9) 4.87/2.23 Obligation: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAAAAAAAA(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAAAAAAAA(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> BALANCE55_IN_GAAAAAAAAA(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1)) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAAAAAAAA(x1) 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAAAAAAAA(x3, x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (10) PiDPToQDPProof (SOUND) 4.87/2.23 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (11) 4.87/2.23 Obligation: 4.87/2.23 Q DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAAAAAAAA(R, balance55_out_gaaaaaaaaa) -> BALANCE55_IN_GAAAAAAAAA(R) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R)) -> U2_GAAAAAAAAA(R, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 BALANCE55_IN_GAAAAAAAAA(tree(L, V, R)) -> BALANCE55_IN_GAAAAAAAAA(L) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(nil) -> balance55_out_gaaaaaaaaa 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R)) -> U2_gaaaaaaaaa(R, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 U2_gaaaaaaaaa(R, balance55_out_gaaaaaaaaa) -> U3_gaaaaaaaaa(balance55_in_gaaaaaaaaa(R)) 4.87/2.23 U3_gaaaaaaaaa(balance55_out_gaaaaaaaaa) -> balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 The set Q consists of the following terms: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x0) 4.87/2.23 U2_gaaaaaaaaa(x0, x1) 4.87/2.23 U3_gaaaaaaaaa(x0) 4.87/2.23 4.87/2.23 We have to consider all (P,Q,R)-chains. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (12) QDPSizeChangeProof (EQUIVALENT) 4.87/2.23 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.87/2.23 4.87/2.23 From the DPs we obtained the following set of size-change graphs: 4.87/2.23 *BALANCE55_IN_GAAAAAAAAA(tree(L, V, R)) -> U2_GAAAAAAAAA(R, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 The graph contains the following edges 1 > 1 4.87/2.23 4.87/2.23 4.87/2.23 *BALANCE55_IN_GAAAAAAAAA(tree(L, V, R)) -> BALANCE55_IN_GAAAAAAAAA(L) 4.87/2.23 The graph contains the following edges 1 > 1 4.87/2.23 4.87/2.23 4.87/2.23 *U2_GAAAAAAAAA(R, balance55_out_gaaaaaaaaa) -> BALANCE55_IN_GAAAAAAAAA(R) 4.87/2.23 The graph contains the following edges 1 >= 1 4.87/2.23 4.87/2.23 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (13) 4.87/2.23 YES 4.87/2.23 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (14) 4.87/2.23 Obligation: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAGAGAAAG(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance_in_ga(T, TB) -> U1_ga(T, TB, balance55_in_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) 4.87/2.23 balance55_in_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaagagaaag(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U2_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaagagaaag(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaagagaaag(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaagagaaag(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 U1_ga(T, TB, balance55_out_gaagagaaag(T, XX0, XX1, [], .(','(nil, -(XX0, XX0)), XX1), [], .(','(TB, -(I, [])), X), X, I, [])) -> balance_out_ga(T, TB) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 balance_in_ga(x1, x2) = balance_in_ga(x1) 4.87/2.23 4.87/2.23 U1_ga(x1, x2, x3) = U1_ga(x3) 4.87/2.23 4.87/2.23 balance55_in_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaagagaaag(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 balance55_out_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaagagaaag 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 U2_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaagagaaag(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 U3_gaagagaaag(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaagagaaag(x19) 4.87/2.23 4.87/2.23 [] = [] 4.87/2.23 4.87/2.23 balance_out_ga(x1, x2) = balance_out_ga 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAGAGAAAG(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAGAGAAAG(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (15) UsableRulesProof (EQUIVALENT) 4.87/2.23 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (16) 4.87/2.23 Obligation: 4.87/2.23 Pi DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> BALANCE55_IN_GAAGAGAAAG(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_GAAGAGAAAG(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) -> balance55_out_gaaaaaaaaa(nil, C, T, T, A, B, A, B, X, X) 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) -> U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) 4.87/2.23 U2_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(L, XX0, XX1, .(','(nil, -(XX2, XX2)), XX3), HR1, TR1, H, T, IH, .(V, IT1))) -> U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_in_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) 4.87/2.23 U3_gaaaaaaaaa(L, V, R, XX0, XX1, NT, HR, TR, LB, VB, RB, A, D, H, X, T, IH, IT, balance55_out_gaaaaaaaaa(R, XX2, XX3, NT, HR, TR, HR1, TR1, IT1, IT)) -> balance55_out_gaaaaaaaaa(tree(L, V, R), XX0, XX1, NT, HR, TR, .(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T)), IH, IT) 4.87/2.23 4.87/2.23 The argument filtering Pi contains the following mapping: 4.87/2.23 nil = nil 4.87/2.23 4.87/2.23 tree(x1, x2, x3) = tree(x1, x2, x3) 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_in_gaaaaaaaaa(x1) 4.87/2.23 4.87/2.23 balance55_out_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 U2_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_gaaaaaaaaa(x3, x19) 4.87/2.23 4.87/2.23 U3_gaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_gaaaaaaaaa(x19) 4.87/2.23 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCE55_IN_GAAGAGAAAG(x1, x4, x6, x10) 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_GAAGAGAAAG(x3, x6, x8, x18, x19) 4.87/2.23 4.87/2.23 4.87/2.23 We have to consider all (P,R,Pi)-chains 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (17) PiDPToQDPProof (SOUND) 4.87/2.23 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (18) 4.87/2.23 Obligation: 4.87/2.23 Q DP problem: 4.87/2.23 The TRS P consists of the following rules: 4.87/2.23 4.87/2.23 U2_GAAGAGAAAG(R, NT, TR, IT, balance55_out_gaaaaaaaaa) -> BALANCE55_IN_GAAGAGAAAG(R, NT, TR, IT) 4.87/2.23 BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), NT, TR, IT) -> U2_GAAGAGAAAG(R, NT, TR, IT, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 4.87/2.23 The TRS R consists of the following rules: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(nil) -> balance55_out_gaaaaaaaaa 4.87/2.23 balance55_in_gaaaaaaaaa(tree(L, V, R)) -> U2_gaaaaaaaaa(R, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 U2_gaaaaaaaaa(R, balance55_out_gaaaaaaaaa) -> U3_gaaaaaaaaa(balance55_in_gaaaaaaaaa(R)) 4.87/2.23 U3_gaaaaaaaaa(balance55_out_gaaaaaaaaa) -> balance55_out_gaaaaaaaaa 4.87/2.23 4.87/2.23 The set Q consists of the following terms: 4.87/2.23 4.87/2.23 balance55_in_gaaaaaaaaa(x0) 4.87/2.23 U2_gaaaaaaaaa(x0, x1) 4.87/2.23 U3_gaaaaaaaaa(x0) 4.87/2.23 4.87/2.23 We have to consider all (P,Q,R)-chains. 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (19) QDPSizeChangeProof (EQUIVALENT) 4.87/2.23 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.87/2.23 4.87/2.23 From the DPs we obtained the following set of size-change graphs: 4.87/2.23 *BALANCE55_IN_GAAGAGAAAG(tree(L, V, R), NT, TR, IT) -> U2_GAAGAGAAAG(R, NT, TR, IT, balance55_in_gaaaaaaaaa(L)) 4.87/2.23 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3, 4 >= 4 4.87/2.23 4.87/2.23 4.87/2.23 *U2_GAAGAGAAAG(R, NT, TR, IT, balance55_out_gaaaaaaaaa) -> BALANCE55_IN_GAAGAGAAAG(R, NT, TR, IT) 4.87/2.23 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4 4.87/2.23 4.87/2.23 4.87/2.23 ---------------------------------------- 4.87/2.23 4.87/2.23 (20) 4.87/2.23 YES 5.21/2.28 EOF