/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern balance(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 10 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) PrologToPiTRSProof [SOUND, 0 ms] (12) PiTRS (13) DependencyPairsProof [EQUIVALENT, 0 ms] (14) PiDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) PiDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) PiDP (19) PiDPToQDPProof [SOUND, 0 ms] (20) QDP (21) PrologToDTProblemTransformerProof [SOUND, 121 ms] (22) TRIPLES (23) TriplesToPiDPProof [SOUND, 0 ms] (24) PiDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) AND (27) PiDP (28) UsableRulesProof [EQUIVALENT, 0 ms] (29) PiDP (30) PiDPToQDPProof [SOUND, 0 ms] (31) QDP (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PrologToTRSTransformerProof [SOUND, 136 ms] (36) QTRS (37) QTRSRRRProof [EQUIVALENT, 340 ms] (38) QTRS (39) QTRSRRRProof [EQUIVALENT, 0 ms] (40) QTRS (41) QTRSRRRProof [EQUIVALENT, 0 ms] (42) QTRS (43) PrologToIRSwTTransformerProof [SOUND, 196 ms] (44) AND (45) IRSwT (46) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (47) IRSwT (48) IntTRSCompressionProof [EQUIVALENT, 20 ms] (49) IRSwT (50) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (51) IRSwT (52) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (53) IRSwT (54) FilterProof [EQUIVALENT, 0 ms] (55) IntTRS (56) IntTRSPeriodicNontermProof [COMPLETE, 5 ms] (57) NO (58) IRSwT (59) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (60) TRUE ---------------------------------------- (0) Obligation: Clauses: balance(T, TB) :- balance(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])). balance(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)). balance(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) :- ','(balance(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)), balance(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))). Query: balance(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: balance_in_2: (f,b) balance_in_5: (f,f,f,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag(x2) ---------------------------------------- (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: BALANCE_IN_AG(T, TB) -> U1_AG(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) BALANCE_IN_AG(T, TB) -> BALANCE_IN_AAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag(x2) BALANCE_IN_AG(x1, x2) = BALANCE_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) U3_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCE_IN_AG(T, TB) -> U1_AG(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) BALANCE_IN_AG(T, TB) -> BALANCE_IN_AAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag(x2) BALANCE_IN_AG(x1, x2) = BALANCE_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) U3_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag(x2) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) The TRS R consists of the following rules: balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) The argument filtering Pi contains the following mapping: balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAAAA(balance_out_aaaaa) -> BALANCE_IN_AAAAA BALANCE_IN_AAAAA -> U2_AAAAA(balance_in_aaaaa) BALANCE_IN_AAAAA -> BALANCE_IN_AAAAA The TRS R consists of the following rules: balance_in_aaaaa -> balance_out_aaaaa balance_in_aaaaa -> U2_aaaaa(balance_in_aaaaa) U2_aaaaa(balance_out_aaaaa) -> U3_aaaaa(balance_in_aaaaa) U3_aaaaa(balance_out_aaaaa) -> balance_out_aaaaa The set Q consists of the following terms: balance_in_aaaaa U2_aaaaa(x0) U3_aaaaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: balance_in_2: (f,b) balance_in_5: (f,f,f,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (12) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag ---------------------------------------- (13) 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: BALANCE_IN_AG(T, TB) -> U1_AG(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) BALANCE_IN_AG(T, TB) -> BALANCE_IN_AAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag BALANCE_IN_AG(x1, x2) = BALANCE_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) U3_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCE_IN_AG(T, TB) -> U1_AG(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) BALANCE_IN_AG(T, TB) -> BALANCE_IN_AAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag BALANCE_IN_AG(x1, x2) = BALANCE_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) U3_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) The TRS R consists of the following rules: balance_in_ag(T, TB) -> U1_ag(T, TB, balance_in_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) U1_ag(T, TB, balance_out_aaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ag(T, TB) The argument filtering Pi contains the following mapping: balance_in_ag(x1, x2) = balance_in_ag(x2) U1_ag(x1, x2, x3) = U1_ag(x3) balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) balance_out_ag(x1, x2) = balance_out_ag BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_AAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_AAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) BALANCE_IN_AAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_AAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)) The TRS R consists of the following rules: balance_in_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_aaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) balance_in_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) U2_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) U3_aaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_aaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_aaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) The argument filtering Pi contains the following mapping: balance_in_aaaaa(x1, x2, x3, x4, x5) = balance_in_aaaaa balance_out_aaaaa(x1, x2, x3, x4, x5) = balance_out_aaaaa U2_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_aaaaa(x18) U3_aaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U3_aaaaa(x18) BALANCE_IN_AAAAA(x1, x2, x3, x4, x5) = BALANCE_IN_AAAAA U2_AAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) = U2_AAAAA(x18) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AAAAA(balance_out_aaaaa) -> BALANCE_IN_AAAAA BALANCE_IN_AAAAA -> U2_AAAAA(balance_in_aaaaa) BALANCE_IN_AAAAA -> BALANCE_IN_AAAAA The TRS R consists of the following rules: balance_in_aaaaa -> balance_out_aaaaa balance_in_aaaaa -> U2_aaaaa(balance_in_aaaaa) U2_aaaaa(balance_out_aaaaa) -> U3_aaaaa(balance_in_aaaaa) U3_aaaaa(balance_out_aaaaa) -> balance_out_aaaaa The set Q consists of the following terms: balance_in_aaaaa U2_aaaaa(x0) U3_aaaaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 12, "program": { "directives": [], "clauses": [ [ "(balance T TB)", "(balance T (- I ([])) (- (. (',' TB (- I ([]))) X) X) (- Rest ([])) (- Rest ([])))" ], [ "(balance (nil) (- X X) (- A B) (- A B) (- (. (',' (nil) (- C C)) T) T))", null ], [ "(balance (tree L V R) (- IH IT) (- (. (',' (tree LB VB RB) (- A D)) H) (. (',' LB (- A (. VB X))) (. (',' RB (- X D)) T))) (- HR TR) (- NH NT))", "(',' (balance L (- IH (. V IT1)) (- H T) (- HR1 TR1) (- NH NT1)) (balance R (- IT1 IT) (- HR1 TR1) (- HR TR) (- NT1 NT)))" ] ] }, "graph": { "nodes": { "type": "Nodes", "394": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "395": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [{ "clause": 1, "scope": 2, "term": "(balance T7 (- X5 ([])) (- (. (',' T6 (- X5 ([]))) X6) X6) (- X7 ([])) (- X7 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X5", "X6", "X7" ], "exprvars": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111)) (balance T36 (- X108 ([])) (- X109 X110) (- X116 ([])) (- X111 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [ "X116", "X108", "X109", "X110", "X111" ], "exprvars": [] } }, "353": { "goal": [{ "clause": 2, "scope": 2, "term": "(balance T7 (- X5 ([])) (- (. (',' T6 (- X5 ([]))) X6) X6) (- X7 ([])) (- X7 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X5", "X6", "X7" ], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "430": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "474": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T440 (- T441 (. T442 X508)) (- T443 T444) (- X509 X510) (- T445 X511)) (balance T446 (- X508 ([])) (- X509 X510) (- T447 ([])) (- X511 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X508", "X509", "X510", "X511" ], "exprvars": [] } }, "376": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [ "X116", "X108", "X109", "X110", "X111" ], "exprvars": [] } }, "398": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "431": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "475": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T58 (- T53 ([])) (- T54 T55) (- T56 ([])) (- T57 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "432": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "413": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T157 (- T158 (. T159 X245)) (- (. (',' T153 (- T161 ([]))) (. (',' T148 (- T158 (. T149 T162))) (. (',' T150 (- T162 (. T151 T161))) T160))) T160) (- X246 X247) (- X252 X248)) (balance T163 (- X245 (. T164 X249)) (- X246 X247) (- X250 X251) (- X248 X253)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T148", "T149", "T150", "T151", "T153" ], "free": [ "X249", "X250", "X251", "X252", "X253", "X245", "X246", "X247", "X248" ], "exprvars": [] } }, "457": { "goal": [ { "clause": 1, "scope": 5, "term": "(balance T58 (- T53 ([])) (- T54 T55) (- T56 ([])) (- T57 ([])))" }, { "clause": 2, "scope": 5, "term": "(balance T58 (- T53 ([])) (- T54 T55) (- T56 ([])) (- T57 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "479": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T440 (- T441 (. T442 X508)) (- T443 T444) (- X509 X510) (- T445 X511))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X508", "X509", "X510", "X511" ], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T157 (- T158 (. T159 X245)) (- (. (',' T153 (- T161 ([]))) (. (',' T148 (- T158 (. T149 T162))) (. (',' T150 (- T162 (. T151 T161))) T160))) T160) (- X246 X247) (- X252 X248))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T148", "T149", "T150", "T151", "T153" ], "free": [ "X252", "X245", "X246", "X247", "X248" ], "exprvars": [] } }, "416": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T192 (- T187 (. T193 X249)) (- T188 T189) (- X250 X251) (- T191 X253))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X249", "X250", "X251", "X253" ], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "480": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T466 (- T462 ([])) (- T463 T464) (- T467 ([])) (- T465 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "384": { "goal": [ { "clause": 1, "scope": 3, "term": "(balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111))" }, { "clause": 2, "scope": 3, "term": "(balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [ "X116", "X108", "X109", "X110", "X111" ], "exprvars": [] } }, "363": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "385": { "goal": [{ "clause": 1, "scope": 3, "term": "(balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [ "X116", "X108", "X109", "X110", "X111" ], "exprvars": [] } }, "364": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "386": { "goal": [{ "clause": 2, "scope": 3, "term": "(balance T31 (- T32 (. T33 X108)) (- (. (',' T28 (- T32 (. T29 T35))) (. (',' T30 (- T35 ([]))) T34)) T34) (- X109 X110) (- X116 X111))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29", "T30" ], "free": [ "X116", "X108", "X109", "X110", "X111" ], "exprvars": [] } }, "463": { "goal": [{ "clause": 1, "scope": 5, "term": "(balance T58 (- T53 ([])) (- T54 T55) (- T56 ([])) (- T57 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "365": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "464": { "goal": [{ "clause": 2, "scope": 5, "term": "(balance T58 (- T53 ([])) (- T54 T55) (- T56 ([])) (- T57 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "465": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "444": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T307 (- T308 (. T309 X380)) (- T310 T311) (- X381 X382) (- T312 X383)) (balance T313 (- X380 (. T314 X384)) (- X381 X382) (- X385 X386) (- X383 X387)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X384", "X385", "X386", "X387", "X380", "X381", "X382", "X383" ], "exprvars": [] } }, "466": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "225": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T7 (- X5 ([])) (- (. (',' T6 (- X5 ([]))) X6) X6) (- X7 ([])) (- X7 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X5", "X6", "X7" ], "exprvars": [] } }, "445": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "467": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [ { "clause": 1, "scope": 2, "term": "(balance T7 (- X5 ([])) (- (. (',' T6 (- X5 ([]))) X6) X6) (- X7 ([])) (- X7 ([])))" }, { "clause": 2, "scope": 2, "term": "(balance T7 (- X5 ([])) (- (. (',' T6 (- X5 ([]))) X6) X6) (- X7 ([])) (- X7 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X5", "X6", "X7" ], "exprvars": [] } }, "424": { "goal": [ { "clause": 1, "scope": 4, "term": "(balance T192 (- T187 (. T193 X249)) (- T188 T189) (- X250 X251) (- T191 X253))" }, { "clause": 2, "scope": 4, "term": "(balance T192 (- T187 (. T193 X249)) (- T188 T189) (- X250 X251) (- T191 X253))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X249", "X250", "X251", "X253" ], "exprvars": [] } }, "447": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T307 (- T308 (. T309 X380)) (- T310 T311) (- X381 X382) (- T312 X383))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X380", "X381", "X382", "X383" ], "exprvars": [] } }, "426": { "goal": [{ "clause": 1, "scope": 4, "term": "(balance T192 (- T187 (. T193 X249)) (- T188 T189) (- X250 X251) (- T191 X253))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X249", "X250", "X251", "X253" ], "exprvars": [] } }, "448": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T333 (- T329 (. T334 X384)) (- T330 T331) (- X385 X386) (- T332 X387))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X384", "X385", "X386", "X387" ], "exprvars": [] } }, "427": { "goal": [{ "clause": 2, "scope": 4, "term": "(balance T192 (- T187 (. T193 X249)) (- T188 T189) (- X250 X251) (- T191 X253))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X249", "X250", "X251", "X253" ], "exprvars": [] } } }, "edges": [ { "from": 12, "to": 13, "label": "CASE" }, { "from": 13, "to": 225, "label": "ONLY EVAL with clause\nbalance(X3, X4) :- balance(X3, -(X5, []), -(.(','(X4, -(X5, [])), X6), X6), -(X7, []), -(X7, [])).\nand substitutionT1 -> T7,\nX3 -> T7,\nT2 -> T6,\nX4 -> T6,\nT5 -> T7" }, { "from": 225, "to": 226, "label": "CASE" }, { "from": 226, "to": 352, "label": "PARALLEL" }, { "from": 226, "to": 353, "label": "PARALLEL" }, { "from": 352, "to": 363, "label": "EVAL with clause\nbalance(nil, -(X36, X36), -(X37, X38), -(X37, X38), -(.(','(nil, -(X39, X39)), X40), X40)).\nand substitutionT7 -> nil,\nX5 -> [],\nX36 -> [],\nX41 -> [],\nT6 -> nil,\nX6 -> [],\nX37 -> .(','(nil, -([], [])), []),\nX38 -> [],\nX7 -> .(','(nil, -([], [])), []),\nX42 -> [],\nT12 -> nil,\nX39 -> [],\nX40 -> []" }, { "from": 352, "to": 364, "label": "EVAL-BACKTRACK" }, { "from": 353, "to": 374, "label": "EVAL with clause\nbalance(tree(X91, X92, X93), -(X94, X95), -(.(','(tree(X96, X97, X98), -(X99, X100)), X101), .(','(X96, -(X99, .(X97, X102))), .(','(X98, -(X102, X100)), X103))), -(X104, X105), -(X106, X107)) :- ','(balance(X91, -(X94, .(X92, X108)), -(X101, X103), -(X109, X110), -(X106, X111)), balance(X93, -(X108, X95), -(X109, X110), -(X104, X105), -(X111, X107))).\nand substitutionX91 -> T31,\nX92 -> T33,\nX93 -> T36,\nT7 -> tree(T31, T33, T36),\nX5 -> T32,\nX94 -> T32,\nX95 -> [],\nX96 -> T28,\nX97 -> T29,\nX98 -> T30,\nT6 -> tree(T28, T29, T30),\nX99 -> T32,\nX100 -> [],\nX6 -> .(','(T28, -(T32, .(T29, T35))), .(','(T30, -(T35, [])), T34)),\nX101 -> .(','(T28, -(T32, .(T29, T35))), .(','(T30, -(T35, [])), T34)),\nX102 -> T35,\nX103 -> T34,\nX113 -> .(','(T28, -(T32, .(T29, T35))), .(','(T30, -(T35, [])), T34)),\nX7 -> X116,\nX104 -> X116,\nX105 -> [],\nX106 -> X116,\nX107 -> [],\nT25 -> T31,\nX112 -> T32,\nT26 -> T33,\nX115 -> T34,\nX114 -> T35,\nT27 -> T36" }, { "from": 353, "to": 375, "label": "EVAL-BACKTRACK" }, { "from": 363, "to": 365, "label": "SUCCESS" }, { "from": 374, "to": 376, "label": "SPLIT 1" }, { "from": 374, "to": 377, "label": "SPLIT 2\nreplacements:X108 -> T53,\nX109 -> T54,\nX110 -> T55,\nX116 -> T56,\nX111 -> T57,\nT36 -> T58" }, { "from": 376, "to": 384, "label": "CASE" }, { "from": 377, "to": 457, "label": "CASE" }, { "from": 384, "to": 385, "label": "PARALLEL" }, { "from": 384, "to": 386, "label": "PARALLEL" }, { "from": 385, "to": 394, "label": "EVAL with clause\nbalance(nil, -(X173, X173), -(X174, X175), -(X174, X175), -(.(','(nil, -(X176, X176)), X177), X177)).\nand substitutionT31 -> nil,\nT32 -> .(T108, T109),\nX173 -> .(T108, T109),\nT33 -> T108,\nX108 -> T109,\nT107 -> .(T108, T109),\nT28 -> T110,\nT29 -> T111,\nT35 -> T112,\nT30 -> T113,\nT34 -> T114,\nX174 -> .(','(T110, -(.(T108, T109), .(T111, T112))), .(','(T113, -(T112, [])), T114)),\nX175 -> T114,\nX109 -> .(','(T110, -(.(T108, T109), .(T111, T112))), .(','(T113, -(T112, [])), T114)),\nX110 -> T114,\nX176 -> X178,\nX177 -> X179,\nX116 -> .(','(nil, -(X178, X178)), X179),\nX111 -> X179" }, { "from": 385, "to": 395, "label": "EVAL-BACKTRACK" }, { "from": 386, "to": 413, "label": "EVAL with clause\nbalance(tree(X228, X229, X230), -(X231, X232), -(.(','(tree(X233, X234, X235), -(X236, X237)), X238), .(','(X233, -(X236, .(X234, X239))), .(','(X235, -(X239, X237)), X240))), -(X241, X242), -(X243, X244)) :- ','(balance(X228, -(X231, .(X229, X245)), -(X238, X240), -(X246, X247), -(X243, X248)), balance(X230, -(X245, X232), -(X246, X247), -(X241, X242), -(X248, X244))).\nand substitutionX228 -> T157,\nX229 -> T159,\nX230 -> T163,\nT31 -> tree(T157, T159, T163),\nT32 -> T158,\nX231 -> T158,\nT33 -> T164,\nX108 -> X249,\nX232 -> .(T164, X249),\nX233 -> T148,\nX234 -> T149,\nX235 -> T150,\nT28 -> tree(T148, T149, T150),\nX236 -> T158,\nT29 -> T151,\nT35 -> T161,\nX237 -> .(T151, T161),\nT30 -> T153,\nT34 -> .(','(T148, -(T158, .(T149, T162))), .(','(T150, -(T162, .(T151, T161))), T160)),\nX238 -> .(','(T153, -(T161, [])), .(','(T148, -(T158, .(T149, T162))), .(','(T150, -(T162, .(T151, T161))), T160))),\nX239 -> T162,\nX240 -> T160,\nT154 -> .(','(T148, -(T158, .(T149, T162))), .(','(T150, -(T162, .(T151, T161))), T160)),\nX109 -> X250,\nX241 -> X250,\nX110 -> X251,\nX242 -> X251,\nX116 -> X252,\nX243 -> X252,\nX111 -> X253,\nX244 -> X253,\nT143 -> T157,\nT146 -> T158,\nT144 -> T159,\nT156 -> T160,\nT152 -> T161,\nT155 -> T162,\nT145 -> T163,\nT147 -> T164" }, { "from": 386, "to": 414, "label": "EVAL-BACKTRACK" }, { "from": 394, "to": 398, "label": "SUCCESS" }, { "from": 413, "to": 415, "label": "SPLIT 1" }, { "from": 413, "to": 416, "label": "SPLIT 2\nreplacements:X245 -> T187,\nX246 -> T188,\nX247 -> T189,\nX252 -> T190,\nX248 -> T191,\nT163 -> T192,\nT164 -> T193" }, { "from": 415, "to": 416, "label": "INSTANCE with matching:\nT192 -> T157\nT187 -> T158\nT193 -> T159\nX249 -> X245\nT188 -> .(','(T153, -(T161, [])), .(','(T148, -(T158, .(T149, T162))), .(','(T150, -(T162, .(T151, T161))), T160)))\nT189 -> T160\nX250 -> X246\nX251 -> X247\nT191 -> X252\nX253 -> X248" }, { "from": 416, "to": 424, "label": "CASE" }, { "from": 424, "to": 426, "label": "PARALLEL" }, { "from": 424, "to": 427, "label": "PARALLEL" }, { "from": 426, "to": 430, "label": "EVAL with clause\nbalance(nil, -(X312, X312), -(X313, X314), -(X313, X314), -(.(','(nil, -(X315, X315)), X316), X316)).\nand substitutionT192 -> nil,\nT187 -> .(T259, T260),\nX312 -> .(T259, T260),\nT193 -> T259,\nX249 -> T260,\nT258 -> .(T259, T260),\nT188 -> T261,\nX313 -> T261,\nT189 -> T262,\nX314 -> T262,\nX250 -> T261,\nX251 -> T262,\nX315 -> T263,\nX316 -> T264,\nT191 -> .(','(nil, -(T263, T263)), T264),\nX253 -> T264" }, { "from": 426, "to": 431, "label": "EVAL-BACKTRACK" }, { "from": 427, "to": 444, "label": "EVAL with clause\nbalance(tree(X363, X364, X365), -(X366, X367), -(.(','(tree(X368, X369, X370), -(X371, X372)), X373), .(','(X368, -(X371, .(X369, X374))), .(','(X370, -(X374, X372)), X375))), -(X376, X377), -(X378, X379)) :- ','(balance(X363, -(X366, .(X364, X380)), -(X373, X375), -(X381, X382), -(X378, X383)), balance(X365, -(X380, X367), -(X381, X382), -(X376, X377), -(X383, X379))).\nand substitutionX363 -> T307,\nX364 -> T309,\nX365 -> T313,\nT192 -> tree(T307, T309, T313),\nT187 -> T308,\nX366 -> T308,\nT193 -> T314,\nX249 -> X384,\nX367 -> .(T314, X384),\nX368 -> T298,\nX369 -> T299,\nX370 -> T300,\nX371 -> T301,\nX372 -> T302,\nX373 -> T310,\nT188 -> .(','(tree(T298, T299, T300), -(T301, T302)), T310),\nX374 -> T304,\nX375 -> T311,\nT189 -> .(','(T298, -(T301, .(T299, T304))), .(','(T300, -(T304, T302)), T311)),\nX250 -> X385,\nX376 -> X385,\nX251 -> X386,\nX377 -> X386,\nT191 -> T312,\nX378 -> T312,\nX253 -> X387,\nX379 -> X387,\nT293 -> T307,\nT296 -> T308,\nT294 -> T309,\nT303 -> T310,\nT305 -> T311,\nT306 -> T312,\nT295 -> T313,\nT297 -> T314" }, { "from": 427, "to": 445, "label": "EVAL-BACKTRACK" }, { "from": 430, "to": 432, "label": "SUCCESS" }, { "from": 444, "to": 447, "label": "SPLIT 1" }, { "from": 444, "to": 448, "label": "SPLIT 2\nreplacements:X380 -> T329,\nX381 -> T330,\nX382 -> T331,\nX383 -> T332,\nT313 -> T333,\nT314 -> T334" }, { "from": 447, "to": 416, "label": "INSTANCE with matching:\nT192 -> T307\nT187 -> T308\nT193 -> T309\nX249 -> X380\nT188 -> T310\nT189 -> T311\nX250 -> X381\nX251 -> X382\nT191 -> T312\nX253 -> X383" }, { "from": 448, "to": 416, "label": "INSTANCE with matching:\nT192 -> T333\nT187 -> T329\nT193 -> T334\nX249 -> X384\nT188 -> T330\nT189 -> T331\nX250 -> X385\nX251 -> X386\nT191 -> T332\nX253 -> X387" }, { "from": 457, "to": 463, "label": "PARALLEL" }, { "from": 457, "to": 464, "label": "PARALLEL" }, { "from": 463, "to": 465, "label": "EVAL with clause\nbalance(nil, -(X448, X448), -(X449, X450), -(X449, X450), -(.(','(nil, -(X451, X451)), X452), X452)).\nand substitutionT58 -> nil,\nT53 -> [],\nX448 -> [],\nT393 -> [],\nT54 -> T394,\nX449 -> T394,\nT55 -> [],\nX450 -> [],\nT56 -> T394,\nT395 -> [],\nX451 -> T396,\nX452 -> [],\nT57 -> .(','(nil, -(T396, T396)), []),\nT397 -> []" }, { "from": 463, "to": 466, "label": "EVAL-BACKTRACK" }, { "from": 464, "to": 474, "label": "EVAL with clause\nbalance(tree(X491, X492, X493), -(X494, X495), -(.(','(tree(X496, X497, X498), -(X499, X500)), X501), .(','(X496, -(X499, .(X497, X502))), .(','(X498, -(X502, X500)), X503))), -(X504, X505), -(X506, X507)) :- ','(balance(X491, -(X494, .(X492, X508)), -(X501, X503), -(X509, X510), -(X506, X511)), balance(X493, -(X508, X495), -(X509, X510), -(X504, X505), -(X511, X507))).\nand substitutionX491 -> T440,\nX492 -> T442,\nX493 -> T446,\nT58 -> tree(T440, T442, T446),\nT53 -> T441,\nX494 -> T441,\nX495 -> [],\nX496 -> T430,\nX497 -> T431,\nX498 -> T432,\nX499 -> T433,\nX500 -> T434,\nX501 -> T443,\nT54 -> .(','(tree(T430, T431, T432), -(T433, T434)), T443),\nX502 -> T436,\nX503 -> T444,\nT55 -> .(','(T430, -(T433, .(T431, T436))), .(','(T432, -(T436, T434)), T444)),\nT56 -> T447,\nX504 -> T447,\nX505 -> [],\nT57 -> T445,\nX506 -> T445,\nX507 -> [],\nT426 -> T440,\nT429 -> T441,\nT427 -> T442,\nT435 -> T443,\nT437 -> T444,\nT439 -> T445,\nT428 -> T446,\nT438 -> T447" }, { "from": 464, "to": 475, "label": "EVAL-BACKTRACK" }, { "from": 465, "to": 467, "label": "SUCCESS" }, { "from": 474, "to": 479, "label": "SPLIT 1" }, { "from": 474, "to": 480, "label": "SPLIT 2\nreplacements:X508 -> T462,\nX509 -> T463,\nX510 -> T464,\nX511 -> T465,\nT446 -> T466,\nT447 -> T467" }, { "from": 479, "to": 416, "label": "INSTANCE with matching:\nT192 -> T440\nT187 -> T441\nT193 -> T442\nX249 -> X508\nT188 -> T443\nT189 -> T444\nX250 -> X509\nX251 -> X510\nT191 -> T445\nX253 -> X511" }, { "from": 480, "to": 377, "label": "INSTANCE with matching:\nT58 -> T466\nT53 -> T462\nT54 -> T463\nT55 -> T464\nT56 -> T467\nT57 -> T465" } ], "type": "Graph" } } ---------------------------------------- (22) Obligation: Triples: balanceA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) :- balanceA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22). balanceA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) :- ','(balancecA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22), balanceA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)). balanceB(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) :- balanceA(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18). balanceB(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) :- ','(balancecA(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18), balanceB(X3, X15, X16, X17, X13, X18)). balanceD(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) :- balanceA(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19). balanceD(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) :- ','(balancecA(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19), balanceA(X3, X12, X4, X20, X16, X17, X21, X22, X19, X23)). balanceD(tree(X1, X2, X3), tree(X4, X5, X6)) :- ','(balancecC(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14), balanceB(X3, X8, X11, X12, X13, X14)). Clauses: balancecA(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6). balancecA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) :- ','(balancecA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22), balancecA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)). balancecB(nil, [], X1, [], X1, .(','(nil, -(X2, X2)), [])). balancecB(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) :- ','(balancecA(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18), balancecB(X3, X15, X16, X17, X13, X18)). balancecC(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9). balancecC(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) :- ','(balancecA(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22), balancecA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)). Afs: balanceD(x1, x2) = balanceD(x2) ---------------------------------------- (23) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: balanceD_in_2: (f,b) balanceA_in_10: (f,f,f,f,f,f,f,f,f,f) balancecA_in_10: (f,f,f,f,f,f,f,f,f,f) balancecC_in_13: (f,f,f,f,b,b,f,b,f,f,f,f,f) balanceB_in_6: (f,f,f,f,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> U7_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balanceA_in_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> BALANCEA_IN_AAAAAAAAAA(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U1_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balanceA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U3_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balanceA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> BALANCEA_IN_AAAAAAAAAA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18) BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_in_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_out_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) -> U9_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balanceA_in_aaaaaaaaaa(X3, X12, X4, X20, X16, X17, X21, X22, X19, X23)) U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_out_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) -> BALANCEA_IN_AAAAAAAAAA(X3, X12, X4, X20, X16, X17, X21, X22, X19, X23) BALANCED_IN_AG(tree(X1, X2, X3), tree(X4, X5, X6)) -> U10_AG(X1, X2, X3, X4, X5, X6, balancecC_in_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) U10_AG(X1, X2, X3, X4, X5, X6, balancecC_out_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) -> U11_AG(X1, X2, X3, X4, X5, X6, balanceB_in_aaaaaa(X3, X8, X11, X12, X13, X14)) U10_AG(X1, X2, X3, X4, X5, X6, balancecC_out_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) -> BALANCEB_IN_AAAAAA(X3, X8, X11, X12, X13, X14) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U4_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balanceA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> U6_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balanceB_in_aaaaaa(X3, X15, X16, X17, X13, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> BALANCEB_IN_AAAAAA(X3, X15, X16, X17, X13, X18) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) balancecC_in_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) -> balancecC_out_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) balancecC_in_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) -> U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) -> U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecC_out_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balanceA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balanceA_in_aaaaaaaaaa balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) balancecC_in_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_in_aaaaggagaaaaa(x5, x6, x8) balancecC_out_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_out_aaaaggagaaaaa(x5, x6, x8) U17_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U17_aaaaggagaaaaa(x7, x8, x9, x10, x12, x19) U18_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U18_aaaaggagaaaaa(x7, x8, x9, x10, x12, x23) balanceB_in_aaaaaa(x1, x2, x3, x4, x5, x6) = balanceB_in_aaaaaa BALANCED_IN_AG(x1, x2) = BALANCED_IN_AG(x2) U7_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U7_AG(x6, x7, x8, x9, x10, x11) BALANCEA_IN_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCEA_IN_AAAAAAAAAA U1_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U1_AAAAAAAAAA(x19) U2_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_AAAAAAAAAA(x19) U3_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_AAAAAAAAAA(x19) U8_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U8_AG(x6, x7, x8, x9, x10, x11) U9_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U9_AG(x6, x7, x8, x9, x10, x11) U10_AG(x1, x2, x3, x4, x5, x6, x7) = U10_AG(x4, x5, x6, x7) U11_AG(x1, x2, x3, x4, x5, x6, x7) = U11_AG(x4, x5, x6, x7) BALANCEB_IN_AAAAAA(x1, x2, x3, x4, x5, x6) = BALANCEB_IN_AAAAAA U4_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U4_AAAAAA(x15) U5_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U5_AAAAAA(x15) U6_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U6_AAAAAA(x15) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (24) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> U7_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balanceA_in_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> BALANCEA_IN_AAAAAAAAAA(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U1_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balanceA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U3_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balanceA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> BALANCEA_IN_AAAAAAAAAA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18) BALANCED_IN_AG(tree(tree(X1, X2, X3), X4, X5), tree(tree(X6, X7, X8), X9, X10)) -> U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_in_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_out_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) -> U9_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balanceA_in_aaaaaaaaaa(X3, X12, X4, X20, X16, X17, X21, X22, X19, X23)) U8_AG(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, balancecA_out_aaaaaaaaaa(X1, X11, X2, X12, .(','(X10, -(X13, [])), .(','(X6, -(X11, .(X7, X14))), .(','(X8, -(X14, .(X9, X13))), X15))), X15, X16, X17, X18, X19)) -> BALANCEA_IN_AAAAAAAAAA(X3, X12, X4, X20, X16, X17, X21, X22, X19, X23) BALANCED_IN_AG(tree(X1, X2, X3), tree(X4, X5, X6)) -> U10_AG(X1, X2, X3, X4, X5, X6, balancecC_in_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) U10_AG(X1, X2, X3, X4, X5, X6, balancecC_out_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) -> U11_AG(X1, X2, X3, X4, X5, X6, balanceB_in_aaaaaa(X3, X8, X11, X12, X13, X14)) U10_AG(X1, X2, X3, X4, X5, X6, balancecC_out_aaaaggagaaaaa(X1, X7, X2, X8, X4, X5, X9, X6, X10, X11, X12, X13, X14)) -> BALANCEB_IN_AAAAAA(X3, X8, X11, X12, X13, X14) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U4_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balanceA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18) BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> U6_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balanceB_in_aaaaaa(X3, X15, X16, X17, X13, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> BALANCEB_IN_AAAAAA(X3, X15, X16, X17, X13, X18) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) balancecC_in_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) -> balancecC_out_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) balancecC_in_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) -> U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) -> U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecC_out_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balanceA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balanceA_in_aaaaaaaaaa balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) balancecC_in_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_in_aaaaggagaaaaa(x5, x6, x8) balancecC_out_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_out_aaaaggagaaaaa(x5, x6, x8) U17_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U17_aaaaggagaaaaa(x7, x8, x9, x10, x12, x19) U18_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U18_aaaaggagaaaaa(x7, x8, x9, x10, x12, x23) balanceB_in_aaaaaa(x1, x2, x3, x4, x5, x6) = balanceB_in_aaaaaa BALANCED_IN_AG(x1, x2) = BALANCED_IN_AG(x2) U7_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U7_AG(x6, x7, x8, x9, x10, x11) BALANCEA_IN_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCEA_IN_AAAAAAAAAA U1_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U1_AAAAAAAAAA(x19) U2_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_AAAAAAAAAA(x19) U3_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U3_AAAAAAAAAA(x19) U8_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U8_AG(x6, x7, x8, x9, x10, x11) U9_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) = U9_AG(x6, x7, x8, x9, x10, x11) U10_AG(x1, x2, x3, x4, x5, x6, x7) = U10_AG(x4, x5, x6, x7) U11_AG(x1, x2, x3, x4, x5, x6, x7) = U11_AG(x4, x5, x6, x7) BALANCEB_IN_AAAAAA(x1, x2, x3, x4, x5, x6) = BALANCEB_IN_AAAAAA U4_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U4_AAAAAA(x15) U5_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U5_AAAAAA(x15) U6_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U6_AAAAAA(x15) We have to consider all (P,R,Pi)-chains ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 13 less nodes. ---------------------------------------- (26) Complex Obligation (AND) ---------------------------------------- (27) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> BALANCEA_IN_AAAAAAAAAA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) balancecC_in_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) -> balancecC_out_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) balancecC_in_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) -> U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) -> U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecC_out_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) balancecC_in_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_in_aaaaggagaaaaa(x5, x6, x8) balancecC_out_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_out_aaaaggagaaaaa(x5, x6, x8) U17_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U17_aaaaggagaaaaa(x7, x8, x9, x10, x12, x19) U18_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U18_aaaaggagaaaaa(x7, x8, x9, x10, x12, x23) BALANCEA_IN_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCEA_IN_AAAAAAAAAA U2_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_AAAAAAAAAA(x19) We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U2_AAAAAAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> BALANCEA_IN_AAAAAAAAAA(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18) BALANCEA_IN_AAAAAAAAAA(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> BALANCEA_IN_AAAAAAAAAA(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) BALANCEA_IN_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = BALANCEA_IN_AAAAAAAAAA U2_AAAAAAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U2_AAAAAAAAAA(x19) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: BALANCEA_IN_AAAAAAAAAA -> U2_AAAAAAAAAA(balancecA_in_aaaaaaaaaa) U2_AAAAAAAAAA(balancecA_out_aaaaaaaaaa) -> BALANCEA_IN_AAAAAAAAAA BALANCEA_IN_AAAAAAAAAA -> BALANCEA_IN_AAAAAAAAAA The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa -> balancecA_out_aaaaaaaaaa balancecA_in_aaaaaaaaaa -> U13_aaaaaaaaaa(balancecA_in_aaaaaaaaaa) U13_aaaaaaaaaa(balancecA_out_aaaaaaaaaa) -> U14_aaaaaaaaaa(balancecA_in_aaaaaaaaaa) U14_aaaaaaaaaa(balancecA_out_aaaaaaaaaa) -> balancecA_out_aaaaaaaaaa The set Q consists of the following terms: balancecA_in_aaaaaaaaaa U13_aaaaaaaaaa(x0) U14_aaaaaaaaaa(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> BALANCEB_IN_AAAAAA(X3, X15, X16, X17, X13, X18) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) balancecC_in_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) -> balancecC_out_aaaaggagaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X5, X6, X7, .(','(X3, -(.(X1, X2), .(X4, X5))), .(','(X6, -(X5, [])), X7)), X7, .(','(nil, -(X8, X8)), X9), X9) balancecC_in_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) -> U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) U17_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, .(','(X12, -(X11, [])), .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14))), X14, X20, X21, X17, X22)) -> U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U18_aaaaggagaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecC_out_aaaaggagaaaaa(tree(X1, X2, X3), X4, X5, X6, tree(X7, X8, X9), X10, X11, X12, .(','(X7, -(X4, .(X8, X13))), .(','(X9, -(X13, .(X10, X11))), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) balancecC_in_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_in_aaaaggagaaaaa(x5, x6, x8) balancecC_out_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) = balancecC_out_aaaaggagaaaaa(x5, x6, x8) U17_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U17_aaaaggagaaaaa(x7, x8, x9, x10, x12, x19) U18_aaaaggagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U18_aaaaggagaaaaa(x7, x8, x9, x10, x12, x23) BALANCEB_IN_AAAAAA(x1, x2, x3, x4, x5, x6) = BALANCEB_IN_AAAAAA U5_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U5_AAAAAA(x15) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: BALANCEB_IN_AAAAAA(tree(X1, X2, X3), X4, .(','(tree(X5, X6, X7), -(X8, X9)), X10), .(','(X5, -(X8, .(X6, X11))), .(','(X7, -(X11, X9)), X12)), X13, X14) -> U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_in_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) U5_AAAAAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, balancecA_out_aaaaaaaaaa(X1, X4, X2, X15, X10, X12, X16, X17, X14, X18)) -> BALANCEB_IN_AAAAAA(X3, X15, X16, X17, X13, X18) The TRS R consists of the following rules: balancecA_in_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) -> balancecA_out_aaaaaaaaaa(nil, .(X1, X2), X1, X2, X3, X4, X3, X4, .(','(nil, -(X5, X5)), X6), X6) balancecA_in_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) -> U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_in_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) U13_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, balancecA_out_aaaaaaaaaa(X1, X4, X2, X19, X12, X14, X20, X21, X17, X22)) -> U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_in_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) U14_aaaaaaaaaa(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, balancecA_out_aaaaaaaaaa(X3, X19, X5, X6, X20, X21, X15, X16, X22, X18)) -> balancecA_out_aaaaaaaaaa(tree(X1, X2, X3), X4, X5, X6, .(','(tree(X7, X8, X9), -(X10, X11)), X12), .(','(X7, -(X10, .(X8, X13))), .(','(X9, -(X13, X11)), X14)), X15, X16, X17, X18) The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) balancecA_in_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_in_aaaaaaaaaa balancecA_out_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = balancecA_out_aaaaaaaaaa U13_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) = U13_aaaaaaaaaa(x19) U14_aaaaaaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23) = U14_aaaaaaaaaa(x23) BALANCEB_IN_AAAAAA(x1, x2, x3, x4, x5, x6) = BALANCEB_IN_AAAAAA U5_AAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) = U5_AAAAAA(x15) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 3, "program": { "directives": [], "clauses": [ [ "(balance T TB)", "(balance T (- I ([])) (- (. (',' TB (- I ([]))) X) X) (- Rest ([])) (- Rest ([])))" ], [ "(balance (nil) (- X X) (- A B) (- A B) (- (. (',' (nil) (- C C)) T) T))", null ], [ "(balance (tree L V R) (- IH IT) (- (. (',' (tree LB VB RB) (- A D)) H) (. (',' LB (- A (. VB X))) (. (',' RB (- X D)) T))) (- HR TR) (- NH NT))", "(',' (balance L (- IH (. V IT1)) (- H T) (- HR1 TR1) (- NH NT1)) (balance R (- IT1 IT) (- HR1 TR1) (- HR TR) (- NT1 NT)))" ] ] }, "graph": { "nodes": { "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "391": { "goal": [ { "clause": 1, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }, { "clause": 2, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "type": "Nodes", "370": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "450": { "goal": [{ "clause": 2, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "498": { "goal": [ { "clause": 1, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }, { "clause": 2, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "499": { "goal": [{ "clause": 1, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "359": { "goal": [{ "clause": 1, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "436": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T164 (- T165 (. T166 X278)) (- (. (',' T160 (- T168 ([]))) (. (',' T155 (- T165 (. T156 T169))) (. (',' T157 (- T169 (. T158 T168))) T167))) T167) (- X279 X280) (- X285 X281)) (balance T170 (- X278 (. T171 X282)) (- X279 X280) (- X283 X284) (- X281 X286)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T155", "T156", "T157", "T158", "T160" ], "free": [ "X282", "X283", "X284", "X285", "X286", "X278", "X279", "X280", "X281" ], "exprvars": [] } }, "458": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "437": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "459": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "419": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": 0, "scope": 1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "360": { "goal": [{ "clause": 2, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "460": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "484": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T314 (- T315 (. T316 X413)) (- T317 T318) (- X414 X415) (- T319 X416)) (balance T320 (- X413 (. T321 X417)) (- X414 X415) (- X418 X419) (- X416 X420)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X417", "X418", "X419", "X420", "X413", "X414", "X415", "X416" ], "exprvars": [] } }, "485": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "387": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144)) (balance T43 (- X141 ([])) (- X142 X143) (- X149 ([])) (- X144 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "420": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "442": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T164 (- T165 (. T166 X278)) (- (. (',' T160 (- T168 ([]))) (. (',' T155 (- T165 (. T156 T169))) (. (',' T157 (- T169 (. T158 T168))) T167))) T167) (- X279 X280) (- X285 X281))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T155", "T156", "T157", "T158", "T160" ], "free": [ "X285", "X278", "X279", "X280", "X281" ], "exprvars": [] } }, "486": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T314 (- T315 (. T316 X413)) (- T317 T318) (- X414 X415) (- T319 X416))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X413", "X414", "X415", "X416" ], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "388": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "421": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "443": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "487": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T340 (- T336 (. T341 X417)) (- T337 T338) (- X418 X419) (- T339 X420))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X417", "X418", "X419", "X420" ], "exprvars": [] } }, "224": { "goal": [ { "clause": 1, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }, { "clause": 2, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "389": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "368": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "500": { "goal": [{ "clause": 2, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "369": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "446": { "goal": [ { "clause": 1, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }, { "clause": 2, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "501": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "502": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "503": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "449": { "goal": [{ "clause": 1, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "504": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T447 (- T448 (. T449 X541)) (- T450 T451) (- X542 X543) (- T452 X544)) (balance T453 (- X541 ([])) (- X542 X543) (- T454 ([])) (- X544 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X541", "X542", "X543", "X544" ], "exprvars": [] } }, "505": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "506": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T447 (- T448 (. T449 X541)) (- T450 T451) (- X542 X543) (- T452 X544))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X541", "X542", "X543", "X544" ], "exprvars": [] } }, "408": { "goal": [{ "clause": 1, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "507": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T473 (- T469 ([])) (- T470 T471) (- T474 ([])) (- T472 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "409": { "goal": [{ "clause": 2, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 11, "label": "CASE" }, { "from": 11, "to": 215, "label": "ONLY EVAL with clause\nbalance(X22, X23) :- balance(X22, -(X24, []), -(.(','(X23, -(X24, [])), X25), X25), -(X26, []), -(X26, [])).\nand substitutionT1 -> T12,\nX22 -> T12,\nT2 -> T11,\nX23 -> T11,\nT10 -> T12" }, { "from": 215, "to": 224, "label": "CASE" }, { "from": 224, "to": 359, "label": "PARALLEL" }, { "from": 224, "to": 360, "label": "PARALLEL" }, { "from": 359, "to": 368, "label": "EVAL with clause\nbalance(nil, -(X69, X69), -(X70, X71), -(X70, X71), -(.(','(nil, -(X72, X72)), X73), X73)).\nand substitutionT12 -> nil,\nX24 -> [],\nX69 -> [],\nX74 -> [],\nT11 -> nil,\nX25 -> [],\nX70 -> .(','(nil, -([], [])), []),\nX71 -> [],\nX26 -> .(','(nil, -([], [])), []),\nX75 -> [],\nT19 -> nil,\nX72 -> [],\nX73 -> []" }, { "from": 359, "to": 369, "label": "EVAL-BACKTRACK" }, { "from": 360, "to": 387, "label": "EVAL with clause\nbalance(tree(X124, X125, X126), -(X127, X128), -(.(','(tree(X129, X130, X131), -(X132, X133)), X134), .(','(X129, -(X132, .(X130, X135))), .(','(X131, -(X135, X133)), X136))), -(X137, X138), -(X139, X140)) :- ','(balance(X124, -(X127, .(X125, X141)), -(X134, X136), -(X142, X143), -(X139, X144)), balance(X126, -(X141, X128), -(X142, X143), -(X137, X138), -(X144, X140))).\nand substitutionX124 -> T38,\nX125 -> T40,\nX126 -> T43,\nT12 -> tree(T38, T40, T43),\nX24 -> T39,\nX127 -> T39,\nX128 -> [],\nX129 -> T35,\nX130 -> T36,\nX131 -> T37,\nT11 -> tree(T35, T36, T37),\nX132 -> T39,\nX133 -> [],\nX25 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX134 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX135 -> T42,\nX136 -> T41,\nX146 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX26 -> X149,\nX137 -> X149,\nX138 -> [],\nX139 -> X149,\nX140 -> [],\nT32 -> T38,\nX145 -> T39,\nT33 -> T40,\nX148 -> T41,\nX147 -> T42,\nT34 -> T43" }, { "from": 360, "to": 388, "label": "EVAL-BACKTRACK" }, { "from": 368, "to": 370, "label": "SUCCESS" }, { "from": 387, "to": 389, "label": "SPLIT 1" }, { "from": 387, "to": 390, "label": "SPLIT 2\nreplacements:X141 -> T60,\nX142 -> T61,\nX143 -> T62,\nX149 -> T63,\nX144 -> T64,\nT43 -> T65" }, { "from": 389, "to": 391, "label": "CASE" }, { "from": 390, "to": 498, "label": "CASE" }, { "from": 391, "to": 408, "label": "PARALLEL" }, { "from": 391, "to": 409, "label": "PARALLEL" }, { "from": 408, "to": 419, "label": "EVAL with clause\nbalance(nil, -(X206, X206), -(X207, X208), -(X207, X208), -(.(','(nil, -(X209, X209)), X210), X210)).\nand substitutionT38 -> nil,\nT39 -> .(T115, T116),\nX206 -> .(T115, T116),\nT40 -> T115,\nX141 -> T116,\nT114 -> .(T115, T116),\nT35 -> T117,\nT36 -> T118,\nT42 -> T119,\nT37 -> T120,\nT41 -> T121,\nX207 -> .(','(T117, -(.(T115, T116), .(T118, T119))), .(','(T120, -(T119, [])), T121)),\nX208 -> T121,\nX142 -> .(','(T117, -(.(T115, T116), .(T118, T119))), .(','(T120, -(T119, [])), T121)),\nX143 -> T121,\nX209 -> X211,\nX210 -> X212,\nX149 -> .(','(nil, -(X211, X211)), X212),\nX144 -> X212" }, { "from": 408, "to": 420, "label": "EVAL-BACKTRACK" }, { "from": 409, "to": 436, "label": "EVAL with clause\nbalance(tree(X261, X262, X263), -(X264, X265), -(.(','(tree(X266, X267, X268), -(X269, X270)), X271), .(','(X266, -(X269, .(X267, X272))), .(','(X268, -(X272, X270)), X273))), -(X274, X275), -(X276, X277)) :- ','(balance(X261, -(X264, .(X262, X278)), -(X271, X273), -(X279, X280), -(X276, X281)), balance(X263, -(X278, X265), -(X279, X280), -(X274, X275), -(X281, X277))).\nand substitutionX261 -> T164,\nX262 -> T166,\nX263 -> T170,\nT38 -> tree(T164, T166, T170),\nT39 -> T165,\nX264 -> T165,\nT40 -> T171,\nX141 -> X282,\nX265 -> .(T171, X282),\nX266 -> T155,\nX267 -> T156,\nX268 -> T157,\nT35 -> tree(T155, T156, T157),\nX269 -> T165,\nT36 -> T158,\nT42 -> T168,\nX270 -> .(T158, T168),\nT37 -> T160,\nT41 -> .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)),\nX271 -> .(','(T160, -(T168, [])), .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167))),\nX272 -> T169,\nX273 -> T167,\nT161 -> .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)),\nX142 -> X283,\nX274 -> X283,\nX143 -> X284,\nX275 -> X284,\nX149 -> X285,\nX276 -> X285,\nX144 -> X286,\nX277 -> X286,\nT150 -> T164,\nT153 -> T165,\nT151 -> T166,\nT163 -> T167,\nT159 -> T168,\nT162 -> T169,\nT152 -> T170,\nT154 -> T171" }, { "from": 409, "to": 437, "label": "EVAL-BACKTRACK" }, { "from": 419, "to": 421, "label": "SUCCESS" }, { "from": 436, "to": 442, "label": "SPLIT 1" }, { "from": 436, "to": 443, "label": "SPLIT 2\nreplacements:X278 -> T194,\nX279 -> T195,\nX280 -> T196,\nX285 -> T197,\nX281 -> T198,\nT170 -> T199,\nT171 -> T200" }, { "from": 442, "to": 443, "label": "INSTANCE with matching:\nT199 -> T164\nT194 -> T165\nT200 -> T166\nX282 -> X278\nT195 -> .(','(T160, -(T168, [])), .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)))\nT196 -> T167\nX283 -> X279\nX284 -> X280\nT198 -> X285\nX286 -> X281" }, { "from": 443, "to": 446, "label": "CASE" }, { "from": 446, "to": 449, "label": "PARALLEL" }, { "from": 446, "to": 450, "label": "PARALLEL" }, { "from": 449, "to": 458, "label": "EVAL with clause\nbalance(nil, -(X345, X345), -(X346, X347), -(X346, X347), -(.(','(nil, -(X348, X348)), X349), X349)).\nand substitutionT199 -> nil,\nT194 -> .(T266, T267),\nX345 -> .(T266, T267),\nT200 -> T266,\nX282 -> T267,\nT265 -> .(T266, T267),\nT195 -> T268,\nX346 -> T268,\nT196 -> T269,\nX347 -> T269,\nX283 -> T268,\nX284 -> T269,\nX348 -> T270,\nX349 -> T271,\nT198 -> .(','(nil, -(T270, T270)), T271),\nX286 -> T271" }, { "from": 449, "to": 459, "label": "EVAL-BACKTRACK" }, { "from": 450, "to": 484, "label": "EVAL with clause\nbalance(tree(X396, X397, X398), -(X399, X400), -(.(','(tree(X401, X402, X403), -(X404, X405)), X406), .(','(X401, -(X404, .(X402, X407))), .(','(X403, -(X407, X405)), X408))), -(X409, X410), -(X411, X412)) :- ','(balance(X396, -(X399, .(X397, X413)), -(X406, X408), -(X414, X415), -(X411, X416)), balance(X398, -(X413, X400), -(X414, X415), -(X409, X410), -(X416, X412))).\nand substitutionX396 -> T314,\nX397 -> T316,\nX398 -> T320,\nT199 -> tree(T314, T316, T320),\nT194 -> T315,\nX399 -> T315,\nT200 -> T321,\nX282 -> X417,\nX400 -> .(T321, X417),\nX401 -> T305,\nX402 -> T306,\nX403 -> T307,\nX404 -> T308,\nX405 -> T309,\nX406 -> T317,\nT195 -> .(','(tree(T305, T306, T307), -(T308, T309)), T317),\nX407 -> T311,\nX408 -> T318,\nT196 -> .(','(T305, -(T308, .(T306, T311))), .(','(T307, -(T311, T309)), T318)),\nX283 -> X418,\nX409 -> X418,\nX284 -> X419,\nX410 -> X419,\nT198 -> T319,\nX411 -> T319,\nX286 -> X420,\nX412 -> X420,\nT300 -> T314,\nT303 -> T315,\nT301 -> T316,\nT310 -> T317,\nT312 -> T318,\nT313 -> T319,\nT302 -> T320,\nT304 -> T321" }, { "from": 450, "to": 485, "label": "EVAL-BACKTRACK" }, { "from": 458, "to": 460, "label": "SUCCESS" }, { "from": 484, "to": 486, "label": "SPLIT 1" }, { "from": 484, "to": 487, "label": "SPLIT 2\nreplacements:X413 -> T336,\nX414 -> T337,\nX415 -> T338,\nX416 -> T339,\nT320 -> T340,\nT321 -> T341" }, { "from": 486, "to": 443, "label": "INSTANCE with matching:\nT199 -> T314\nT194 -> T315\nT200 -> T316\nX282 -> X413\nT195 -> T317\nT196 -> T318\nX283 -> X414\nX284 -> X415\nT198 -> T319\nX286 -> X416" }, { "from": 487, "to": 443, "label": "INSTANCE with matching:\nT199 -> T340\nT194 -> T336\nT200 -> T341\nX282 -> X417\nT195 -> T337\nT196 -> T338\nX283 -> X418\nX284 -> X419\nT198 -> T339\nX286 -> X420" }, { "from": 498, "to": 499, "label": "PARALLEL" }, { "from": 498, "to": 500, "label": "PARALLEL" }, { "from": 499, "to": 501, "label": "EVAL with clause\nbalance(nil, -(X481, X481), -(X482, X483), -(X482, X483), -(.(','(nil, -(X484, X484)), X485), X485)).\nand substitutionT65 -> nil,\nT60 -> [],\nX481 -> [],\nT400 -> [],\nT61 -> T401,\nX482 -> T401,\nT62 -> [],\nX483 -> [],\nT63 -> T401,\nT402 -> [],\nX484 -> T403,\nX485 -> [],\nT64 -> .(','(nil, -(T403, T403)), []),\nT404 -> []" }, { "from": 499, "to": 502, "label": "EVAL-BACKTRACK" }, { "from": 500, "to": 504, "label": "EVAL with clause\nbalance(tree(X524, X525, X526), -(X527, X528), -(.(','(tree(X529, X530, X531), -(X532, X533)), X534), .(','(X529, -(X532, .(X530, X535))), .(','(X531, -(X535, X533)), X536))), -(X537, X538), -(X539, X540)) :- ','(balance(X524, -(X527, .(X525, X541)), -(X534, X536), -(X542, X543), -(X539, X544)), balance(X526, -(X541, X528), -(X542, X543), -(X537, X538), -(X544, X540))).\nand substitutionX524 -> T447,\nX525 -> T449,\nX526 -> T453,\nT65 -> tree(T447, T449, T453),\nT60 -> T448,\nX527 -> T448,\nX528 -> [],\nX529 -> T437,\nX530 -> T438,\nX531 -> T439,\nX532 -> T440,\nX533 -> T441,\nX534 -> T450,\nT61 -> .(','(tree(T437, T438, T439), -(T440, T441)), T450),\nX535 -> T443,\nX536 -> T451,\nT62 -> .(','(T437, -(T440, .(T438, T443))), .(','(T439, -(T443, T441)), T451)),\nT63 -> T454,\nX537 -> T454,\nX538 -> [],\nT64 -> T452,\nX539 -> T452,\nX540 -> [],\nT433 -> T447,\nT436 -> T448,\nT434 -> T449,\nT442 -> T450,\nT444 -> T451,\nT446 -> T452,\nT435 -> T453,\nT445 -> T454" }, { "from": 500, "to": 505, "label": "EVAL-BACKTRACK" }, { "from": 501, "to": 503, "label": "SUCCESS" }, { "from": 504, "to": 506, "label": "SPLIT 1" }, { "from": 504, "to": 507, "label": "SPLIT 2\nreplacements:X541 -> T469,\nX542 -> T470,\nX543 -> T471,\nX544 -> T472,\nT453 -> T473,\nT454 -> T474" }, { "from": 506, "to": 443, "label": "INSTANCE with matching:\nT199 -> T447\nT194 -> T448\nT200 -> T449\nX282 -> X541\nT195 -> T450\nT196 -> T451\nX283 -> X542\nX284 -> X543\nT198 -> T452\nX286 -> X544" }, { "from": 507, "to": 390, "label": "INSTANCE with matching:\nT65 -> T473\nT60 -> T469\nT61 -> T470\nT62 -> T471\nT63 -> T474\nT64 -> T472" } ], "type": "Graph" } } ---------------------------------------- (36) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in(nil) -> f3_out1 f3_in(tree(T35, T36, T37)) -> U1(f387_in(T35, T36, T37), tree(T35, T36, T37)) U1(f387_out1, tree(T35, T36, T37)) -> f3_out1 f443_in -> f443_out1 f443_in -> U2(f484_in) U2(f484_out1) -> f443_out1 f390_in -> f390_out1 f390_in -> U3(f504_in) U3(f504_out1) -> f390_out1 f389_in(T117, T118, T120) -> f389_out1 f389_in(tree(T155, T156, T157), T158, T160) -> U4(f436_in(T160, T155, T156, T157, T158), tree(T155, T156, T157), T158, T160) U4(f436_out1, tree(T155, T156, T157), T158, T160) -> f389_out1 f387_in(T35, T36, T37) -> U5(f389_in(T35, T36, T37), T35, T36, T37) U5(f389_out1, T35, T36, T37) -> U6(f390_in, T35, T36, T37) U6(f390_out1, T35, T36, T37) -> f387_out1 f436_in(T160, T155, T156, T157, T158) -> U7(f443_in, T160, T155, T156, T157, T158) U7(f443_out1, T160, T155, T156, T157, T158) -> U8(f443_in, T160, T155, T156, T157, T158) U8(f443_out1, T160, T155, T156, T157, T158) -> f436_out1 f484_in -> U9(f443_in) U9(f443_out1) -> U10(f443_in) U10(f443_out1) -> f484_out1 f504_in -> U11(f443_in) U11(f443_out1) -> U12(f390_in) U12(f390_out1) -> f504_out1 Q is empty. ---------------------------------------- (37) QTRSRRRProof (EQUIVALENT) Used ordering: f3_in/1(YES) nil/0) f3_out1/0) tree/3(YES,YES,YES) U1/2(YES,YES) f387_in/3(YES,YES,YES) f387_out1/0) f443_in/0) f443_out1/0) U2/1)YES( f484_in/0) f484_out1/0) f390_in/0) f390_out1/0) U3/1)YES( f504_in/0) f504_out1/0) f389_in/3(YES,YES,YES) f389_out1/0) U4/4(YES,YES,YES,YES) f436_in/5(YES,YES,YES,YES,YES) f436_out1/0) U5/4(YES,YES,YES,YES) U6/4(YES,YES,YES,YES) U7/6(YES,YES,YES,YES,YES,YES) U8/6(YES,YES,YES,YES,YES,YES) U9/1)YES( U10/1)YES( U11/1)YES( U12/1)YES( Quasi precedence: f3_in_1 > U1_2 > f3_out1 f3_in_1 > f387_in_3 > [f389_in_3, f436_in_5] > tree_3 > U4_4 f3_in_1 > f387_in_3 > [f389_in_3, f436_in_5] > [f443_in, f443_out1, f484_in, f484_out1, f390_in, f390_out1, f504_in, f504_out1, f389_out1, f436_out1, U6_4] > f387_out1 f3_in_1 > f387_in_3 > [f389_in_3, f436_in_5] > [f443_in, f443_out1, f484_in, f484_out1, f390_in, f390_out1, f504_in, f504_out1, f389_out1, f436_out1, U6_4] > U8_6 f3_in_1 > f387_in_3 > [f389_in_3, f436_in_5] > U7_6 > U8_6 f3_in_1 > f387_in_3 > U5_4 > [f443_in, f443_out1, f484_in, f484_out1, f390_in, f390_out1, f504_in, f504_out1, f389_out1, f436_out1, U6_4] > f387_out1 f3_in_1 > f387_in_3 > U5_4 > [f443_in, f443_out1, f484_in, f484_out1, f390_in, f390_out1, f504_in, f504_out1, f389_out1, f436_out1, U6_4] > U8_6 nil > f3_out1 Status: f3_in_1: multiset status nil: multiset status f3_out1: multiset status tree_3: multiset status U1_2: multiset status f387_in_3: multiset status f387_out1: multiset status f443_in: multiset status f443_out1: multiset status f484_in: multiset status f484_out1: multiset status f390_in: multiset status f390_out1: multiset status f504_in: multiset status f504_out1: multiset status f389_in_3: [1,2,3] f389_out1: multiset status U4_4: multiset status f436_in_5: [3,1,5,4,2] f436_out1: multiset status U5_4: multiset status U6_4: multiset status U7_6: multiset status U8_6: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f3_in(nil) -> f3_out1 f3_in(tree(T35, T36, T37)) -> U1(f387_in(T35, T36, T37), tree(T35, T36, T37)) U1(f387_out1, tree(T35, T36, T37)) -> f3_out1 f389_in(T117, T118, T120) -> f389_out1 f389_in(tree(T155, T156, T157), T158, T160) -> U4(f436_in(T160, T155, T156, T157, T158), tree(T155, T156, T157), T158, T160) U4(f436_out1, tree(T155, T156, T157), T158, T160) -> f389_out1 f387_in(T35, T36, T37) -> U5(f389_in(T35, T36, T37), T35, T36, T37) U5(f389_out1, T35, T36, T37) -> U6(f390_in, T35, T36, T37) U6(f390_out1, T35, T36, T37) -> f387_out1 f436_in(T160, T155, T156, T157, T158) -> U7(f443_in, T160, T155, T156, T157, T158) U7(f443_out1, T160, T155, T156, T157, T158) -> U8(f443_in, T160, T155, T156, T157, T158) U8(f443_out1, T160, T155, T156, T157, T158) -> f436_out1 ---------------------------------------- (38) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f443_in -> f443_out1 f443_in -> U2(f484_in) U2(f484_out1) -> f443_out1 f390_in -> f390_out1 f390_in -> U3(f504_in) U3(f504_out1) -> f390_out1 f484_in -> U9(f443_in) U9(f443_out1) -> U10(f443_in) U10(f443_out1) -> f484_out1 f504_in -> U11(f443_in) U11(f443_out1) -> U12(f390_in) U12(f390_out1) -> f504_out1 Q is empty. ---------------------------------------- (39) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U10(x_1)) = 2*x_1 POL(U11(x_1)) = 1 + 2*x_1 POL(U12(x_1)) = x_1 POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = x_1 POL(U9(x_1)) = 2*x_1 POL(f390_in) = 1 POL(f390_out1) = 0 POL(f443_in) = 0 POL(f443_out1) = 0 POL(f484_in) = 0 POL(f484_out1) = 0 POL(f504_in) = 1 POL(f504_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f390_in -> f390_out1 ---------------------------------------- (40) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f443_in -> f443_out1 f443_in -> U2(f484_in) U2(f484_out1) -> f443_out1 f390_in -> U3(f504_in) U3(f504_out1) -> f390_out1 f484_in -> U9(f443_in) U9(f443_out1) -> U10(f443_in) U10(f443_out1) -> f484_out1 f504_in -> U11(f443_in) U11(f443_out1) -> U12(f390_in) U12(f390_out1) -> f504_out1 Q is empty. ---------------------------------------- (41) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U10(x_1)) = x_1 POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = 2*x_1 POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = 2*x_1 POL(U9(x_1)) = x_1 POL(f390_in) = 0 POL(f390_out1) = 2 POL(f443_in) = 0 POL(f443_out1) = 0 POL(f484_in) = 0 POL(f484_out1) = 0 POL(f504_in) = 0 POL(f504_out1) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U3(f504_out1) -> f390_out1 U12(f390_out1) -> f504_out1 ---------------------------------------- (42) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f443_in -> f443_out1 f443_in -> U2(f484_in) U2(f484_out1) -> f443_out1 f390_in -> U3(f504_in) f484_in -> U9(f443_in) U9(f443_out1) -> U10(f443_in) U10(f443_out1) -> f484_out1 f504_in -> U11(f443_in) U11(f443_out1) -> U12(f390_in) Q is empty. ---------------------------------------- (43) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(balance T TB)", "(balance T (- I ([])) (- (. (',' TB (- I ([]))) X) X) (- Rest ([])) (- Rest ([])))" ], [ "(balance (nil) (- X X) (- A B) (- A B) (- (. (',' (nil) (- C C)) T) T))", null ], [ "(balance (tree L V R) (- IH IT) (- (. (',' (tree LB VB RB) (- A D)) H) (. (',' LB (- A (. VB X))) (. (',' RB (- X D)) T))) (- HR TR) (- NH NT))", "(',' (balance L (- IH (. V IT1)) (- H T) (- HR1 TR1) (- NH NT1)) (balance R (- IT1 IT) (- HR1 TR1) (- HR TR) (- NT1 NT)))" ] ] }, "graph": { "nodes": { "type": "Nodes", "392": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144)) (balance T43 (- X141 ([])) (- X142 X143) (- X149 ([])) (- X144 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "371": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "393": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "372": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "373": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "472": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T447 (- T448 (. T449 X541)) (- T450 T451) (- X542 X543) (- T452 X544))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X541", "X542", "X543", "X544" ], "exprvars": [] } }, "396": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "451": { "goal": [ { "clause": 1, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }, { "clause": 2, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "473": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T473 (- T469 ([])) (- T470 T471) (- T474 ([])) (- T472 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "331": { "goal": [ { "clause": 1, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }, { "clause": 2, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "397": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "452": { "goal": [{ "clause": 1, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "453": { "goal": [{ "clause": 2, "scope": 5, "term": "(balance T65 (- T60 ([])) (- T61 T62) (- T63 ([])) (- T64 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "399": { "goal": [ { "clause": 1, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }, { "clause": 2, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "410": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "454": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "411": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "433": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "455": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "412": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "434": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "456": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "435": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "438": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T314 (- T315 (. T316 X413)) (- T317 T318) (- X414 X415) (- T319 X416)) (balance T320 (- X413 (. T321 X417)) (- X414 X415) (- X418 X419) (- X416 X420)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X417", "X418", "X419", "X420", "X413", "X414", "X415", "X416" ], "exprvars": [] } }, "417": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T164 (- T165 (. T166 X278)) (- (. (',' T160 (- T168 ([]))) (. (',' T155 (- T165 (. T156 T169))) (. (',' T157 (- T169 (. T158 T168))) T167))) T167) (- X279 X280) (- X285 X281)) (balance T170 (- X278 (. T171 X282)) (- X279 X280) (- X283 X284) (- X281 X286)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T155", "T156", "T157", "T158", "T160" ], "free": [ "X282", "X283", "X284", "X285", "X286", "X278", "X279", "X280", "X281" ], "exprvars": [] } }, "439": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "418": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "461": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (balance T447 (- T448 (. T449 X541)) (- T450 T451) (- X542 X543) (- T452 X544)) (balance T453 (- X541 ([])) (- X542 X543) (- T454 ([])) (- X544 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X541", "X542", "X543", "X544" ], "exprvars": [] } }, "440": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T314 (- T315 (. T316 X413)) (- T317 T318) (- X414 X415) (- T319 X416))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X413", "X414", "X415", "X416" ], "exprvars": [] } }, "462": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "441": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T340 (- T336 (. T341 X417)) (- T337 T338) (- X418 X419) (- T339 X420))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X417", "X418", "X419", "X420" ], "exprvars": [] } }, "366": { "goal": [{ "clause": 1, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(balance T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "367": { "goal": [{ "clause": 2, "scope": 2, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "400": { "goal": [{ "clause": 1, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "422": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T164 (- T165 (. T166 X278)) (- (. (',' T160 (- T168 ([]))) (. (',' T155 (- T165 (. T156 T169))) (. (',' T157 (- T169 (. T158 T168))) T167))) T167) (- X279 X280) (- X285 X281))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T155", "T156", "T157", "T158", "T160" ], "free": [ "X285", "X278", "X279", "X280", "X281" ], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T12 (- X24 ([])) (- (. (',' T11 (- X24 ([]))) X25) X25) (- X26 ([])) (- X26 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X24", "X25", "X26" ], "exprvars": [] } }, "401": { "goal": [{ "clause": 2, "scope": 3, "term": "(balance T38 (- T39 (. T40 X141)) (- (. (',' T35 (- T39 (. T36 T42))) (. (',' T37 (- T42 ([]))) T41)) T41) (- X142 X143) (- X149 X144))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36", "T37" ], "free": [ "X149", "X141", "X142", "X143", "X144" ], "exprvars": [] } }, "423": { "goal": [{ "clause": -1, "scope": -1, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "425": { "goal": [ { "clause": 1, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }, { "clause": 2, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "428": { "goal": [{ "clause": 1, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } }, "429": { "goal": [{ "clause": 2, "scope": 4, "term": "(balance T199 (- T194 (. T200 X282)) (- T195 T196) (- X283 X284) (- T198 X286))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X282", "X283", "X284", "X286" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 269, "label": "ONLY EVAL with clause\nbalance(X22, X23) :- balance(X22, -(X24, []), -(.(','(X23, -(X24, [])), X25), X25), -(X26, []), -(X26, [])).\nand substitutionT1 -> T12,\nX22 -> T12,\nT2 -> T11,\nX23 -> T11,\nT10 -> T12" }, { "from": 269, "to": 331, "label": "CASE" }, { "from": 331, "to": 366, "label": "PARALLEL" }, { "from": 331, "to": 367, "label": "PARALLEL" }, { "from": 366, "to": 371, "label": "EVAL with clause\nbalance(nil, -(X69, X69), -(X70, X71), -(X70, X71), -(.(','(nil, -(X72, X72)), X73), X73)).\nand substitutionT12 -> nil,\nX24 -> [],\nX69 -> [],\nX74 -> [],\nT11 -> nil,\nX25 -> [],\nX70 -> .(','(nil, -([], [])), []),\nX71 -> [],\nX26 -> .(','(nil, -([], [])), []),\nX75 -> [],\nT19 -> nil,\nX72 -> [],\nX73 -> []" }, { "from": 366, "to": 372, "label": "EVAL-BACKTRACK" }, { "from": 367, "to": 392, "label": "EVAL with clause\nbalance(tree(X124, X125, X126), -(X127, X128), -(.(','(tree(X129, X130, X131), -(X132, X133)), X134), .(','(X129, -(X132, .(X130, X135))), .(','(X131, -(X135, X133)), X136))), -(X137, X138), -(X139, X140)) :- ','(balance(X124, -(X127, .(X125, X141)), -(X134, X136), -(X142, X143), -(X139, X144)), balance(X126, -(X141, X128), -(X142, X143), -(X137, X138), -(X144, X140))).\nand substitutionX124 -> T38,\nX125 -> T40,\nX126 -> T43,\nT12 -> tree(T38, T40, T43),\nX24 -> T39,\nX127 -> T39,\nX128 -> [],\nX129 -> T35,\nX130 -> T36,\nX131 -> T37,\nT11 -> tree(T35, T36, T37),\nX132 -> T39,\nX133 -> [],\nX25 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX134 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX135 -> T42,\nX136 -> T41,\nX146 -> .(','(T35, -(T39, .(T36, T42))), .(','(T37, -(T42, [])), T41)),\nX26 -> X149,\nX137 -> X149,\nX138 -> [],\nX139 -> X149,\nX140 -> [],\nT32 -> T38,\nX145 -> T39,\nT33 -> T40,\nX148 -> T41,\nX147 -> T42,\nT34 -> T43" }, { "from": 367, "to": 393, "label": "EVAL-BACKTRACK" }, { "from": 371, "to": 373, "label": "SUCCESS" }, { "from": 392, "to": 396, "label": "SPLIT 1" }, { "from": 392, "to": 397, "label": "SPLIT 2\nreplacements:X141 -> T60,\nX142 -> T61,\nX143 -> T62,\nX149 -> T63,\nX144 -> T64,\nT43 -> T65" }, { "from": 396, "to": 399, "label": "CASE" }, { "from": 397, "to": 451, "label": "CASE" }, { "from": 399, "to": 400, "label": "PARALLEL" }, { "from": 399, "to": 401, "label": "PARALLEL" }, { "from": 400, "to": 410, "label": "EVAL with clause\nbalance(nil, -(X206, X206), -(X207, X208), -(X207, X208), -(.(','(nil, -(X209, X209)), X210), X210)).\nand substitutionT38 -> nil,\nT39 -> .(T115, T116),\nX206 -> .(T115, T116),\nT40 -> T115,\nX141 -> T116,\nT114 -> .(T115, T116),\nT35 -> T117,\nT36 -> T118,\nT42 -> T119,\nT37 -> T120,\nT41 -> T121,\nX207 -> .(','(T117, -(.(T115, T116), .(T118, T119))), .(','(T120, -(T119, [])), T121)),\nX208 -> T121,\nX142 -> .(','(T117, -(.(T115, T116), .(T118, T119))), .(','(T120, -(T119, [])), T121)),\nX143 -> T121,\nX209 -> X211,\nX210 -> X212,\nX149 -> .(','(nil, -(X211, X211)), X212),\nX144 -> X212" }, { "from": 400, "to": 411, "label": "EVAL-BACKTRACK" }, { "from": 401, "to": 417, "label": "EVAL with clause\nbalance(tree(X261, X262, X263), -(X264, X265), -(.(','(tree(X266, X267, X268), -(X269, X270)), X271), .(','(X266, -(X269, .(X267, X272))), .(','(X268, -(X272, X270)), X273))), -(X274, X275), -(X276, X277)) :- ','(balance(X261, -(X264, .(X262, X278)), -(X271, X273), -(X279, X280), -(X276, X281)), balance(X263, -(X278, X265), -(X279, X280), -(X274, X275), -(X281, X277))).\nand substitutionX261 -> T164,\nX262 -> T166,\nX263 -> T170,\nT38 -> tree(T164, T166, T170),\nT39 -> T165,\nX264 -> T165,\nT40 -> T171,\nX141 -> X282,\nX265 -> .(T171, X282),\nX266 -> T155,\nX267 -> T156,\nX268 -> T157,\nT35 -> tree(T155, T156, T157),\nX269 -> T165,\nT36 -> T158,\nT42 -> T168,\nX270 -> .(T158, T168),\nT37 -> T160,\nT41 -> .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)),\nX271 -> .(','(T160, -(T168, [])), .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167))),\nX272 -> T169,\nX273 -> T167,\nT161 -> .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)),\nX142 -> X283,\nX274 -> X283,\nX143 -> X284,\nX275 -> X284,\nX149 -> X285,\nX276 -> X285,\nX144 -> X286,\nX277 -> X286,\nT150 -> T164,\nT153 -> T165,\nT151 -> T166,\nT163 -> T167,\nT159 -> T168,\nT162 -> T169,\nT152 -> T170,\nT154 -> T171" }, { "from": 401, "to": 418, "label": "EVAL-BACKTRACK" }, { "from": 410, "to": 412, "label": "SUCCESS" }, { "from": 417, "to": 422, "label": "SPLIT 1" }, { "from": 417, "to": 423, "label": "SPLIT 2\nreplacements:X278 -> T194,\nX279 -> T195,\nX280 -> T196,\nX285 -> T197,\nX281 -> T198,\nT170 -> T199,\nT171 -> T200" }, { "from": 422, "to": 423, "label": "INSTANCE with matching:\nT199 -> T164\nT194 -> T165\nT200 -> T166\nX282 -> X278\nT195 -> .(','(T160, -(T168, [])), .(','(T155, -(T165, .(T156, T169))), .(','(T157, -(T169, .(T158, T168))), T167)))\nT196 -> T167\nX283 -> X279\nX284 -> X280\nT198 -> X285\nX286 -> X281" }, { "from": 423, "to": 425, "label": "CASE" }, { "from": 425, "to": 428, "label": "PARALLEL" }, { "from": 425, "to": 429, "label": "PARALLEL" }, { "from": 428, "to": 433, "label": "EVAL with clause\nbalance(nil, -(X345, X345), -(X346, X347), -(X346, X347), -(.(','(nil, -(X348, X348)), X349), X349)).\nand substitutionT199 -> nil,\nT194 -> .(T266, T267),\nX345 -> .(T266, T267),\nT200 -> T266,\nX282 -> T267,\nT265 -> .(T266, T267),\nT195 -> T268,\nX346 -> T268,\nT196 -> T269,\nX347 -> T269,\nX283 -> T268,\nX284 -> T269,\nX348 -> T270,\nX349 -> T271,\nT198 -> .(','(nil, -(T270, T270)), T271),\nX286 -> T271" }, { "from": 428, "to": 434, "label": "EVAL-BACKTRACK" }, { "from": 429, "to": 438, "label": "EVAL with clause\nbalance(tree(X396, X397, X398), -(X399, X400), -(.(','(tree(X401, X402, X403), -(X404, X405)), X406), .(','(X401, -(X404, .(X402, X407))), .(','(X403, -(X407, X405)), X408))), -(X409, X410), -(X411, X412)) :- ','(balance(X396, -(X399, .(X397, X413)), -(X406, X408), -(X414, X415), -(X411, X416)), balance(X398, -(X413, X400), -(X414, X415), -(X409, X410), -(X416, X412))).\nand substitutionX396 -> T314,\nX397 -> T316,\nX398 -> T320,\nT199 -> tree(T314, T316, T320),\nT194 -> T315,\nX399 -> T315,\nT200 -> T321,\nX282 -> X417,\nX400 -> .(T321, X417),\nX401 -> T305,\nX402 -> T306,\nX403 -> T307,\nX404 -> T308,\nX405 -> T309,\nX406 -> T317,\nT195 -> .(','(tree(T305, T306, T307), -(T308, T309)), T317),\nX407 -> T311,\nX408 -> T318,\nT196 -> .(','(T305, -(T308, .(T306, T311))), .(','(T307, -(T311, T309)), T318)),\nX283 -> X418,\nX409 -> X418,\nX284 -> X419,\nX410 -> X419,\nT198 -> T319,\nX411 -> T319,\nX286 -> X420,\nX412 -> X420,\nT300 -> T314,\nT303 -> T315,\nT301 -> T316,\nT310 -> T317,\nT312 -> T318,\nT313 -> T319,\nT302 -> T320,\nT304 -> T321" }, { "from": 429, "to": 439, "label": "EVAL-BACKTRACK" }, { "from": 433, "to": 435, "label": "SUCCESS" }, { "from": 438, "to": 440, "label": "SPLIT 1" }, { "from": 438, "to": 441, "label": "SPLIT 2\nreplacements:X413 -> T336,\nX414 -> T337,\nX415 -> T338,\nX416 -> T339,\nT320 -> T340,\nT321 -> T341" }, { "from": 440, "to": 423, "label": "INSTANCE with matching:\nT199 -> T314\nT194 -> T315\nT200 -> T316\nX282 -> X413\nT195 -> T317\nT196 -> T318\nX283 -> X414\nX284 -> X415\nT198 -> T319\nX286 -> X416" }, { "from": 441, "to": 423, "label": "INSTANCE with matching:\nT199 -> T340\nT194 -> T336\nT200 -> T341\nX282 -> X417\nT195 -> T337\nT196 -> T338\nX283 -> X418\nX284 -> X419\nT198 -> T339\nX286 -> X420" }, { "from": 451, "to": 452, "label": "PARALLEL" }, { "from": 451, "to": 453, "label": "PARALLEL" }, { "from": 452, "to": 454, "label": "EVAL with clause\nbalance(nil, -(X481, X481), -(X482, X483), -(X482, X483), -(.(','(nil, -(X484, X484)), X485), X485)).\nand substitutionT65 -> nil,\nT60 -> [],\nX481 -> [],\nT400 -> [],\nT61 -> T401,\nX482 -> T401,\nT62 -> [],\nX483 -> [],\nT63 -> T401,\nT402 -> [],\nX484 -> T403,\nX485 -> [],\nT64 -> .(','(nil, -(T403, T403)), []),\nT404 -> []" }, { "from": 452, "to": 455, "label": "EVAL-BACKTRACK" }, { "from": 453, "to": 461, "label": "EVAL with clause\nbalance(tree(X524, X525, X526), -(X527, X528), -(.(','(tree(X529, X530, X531), -(X532, X533)), X534), .(','(X529, -(X532, .(X530, X535))), .(','(X531, -(X535, X533)), X536))), -(X537, X538), -(X539, X540)) :- ','(balance(X524, -(X527, .(X525, X541)), -(X534, X536), -(X542, X543), -(X539, X544)), balance(X526, -(X541, X528), -(X542, X543), -(X537, X538), -(X544, X540))).\nand substitutionX524 -> T447,\nX525 -> T449,\nX526 -> T453,\nT65 -> tree(T447, T449, T453),\nT60 -> T448,\nX527 -> T448,\nX528 -> [],\nX529 -> T437,\nX530 -> T438,\nX531 -> T439,\nX532 -> T440,\nX533 -> T441,\nX534 -> T450,\nT61 -> .(','(tree(T437, T438, T439), -(T440, T441)), T450),\nX535 -> T443,\nX536 -> T451,\nT62 -> .(','(T437, -(T440, .(T438, T443))), .(','(T439, -(T443, T441)), T451)),\nT63 -> T454,\nX537 -> T454,\nX538 -> [],\nT64 -> T452,\nX539 -> T452,\nX540 -> [],\nT433 -> T447,\nT436 -> T448,\nT434 -> T449,\nT442 -> T450,\nT444 -> T451,\nT446 -> T452,\nT435 -> T453,\nT445 -> T454" }, { "from": 453, "to": 462, "label": "EVAL-BACKTRACK" }, { "from": 454, "to": 456, "label": "SUCCESS" }, { "from": 461, "to": 472, "label": "SPLIT 1" }, { "from": 461, "to": 473, "label": "SPLIT 2\nreplacements:X541 -> T469,\nX542 -> T470,\nX543 -> T471,\nX544 -> T472,\nT453 -> T473,\nT454 -> T474" }, { "from": 472, "to": 423, "label": "INSTANCE with matching:\nT199 -> T447\nT194 -> T448\nT200 -> T449\nX282 -> X541\nT195 -> T450\nT196 -> T451\nX283 -> X542\nX284 -> X543\nT198 -> T452\nX286 -> X544" }, { "from": 473, "to": 397, "label": "INSTANCE with matching:\nT65 -> T473\nT60 -> T469\nT61 -> T470\nT62 -> T471\nT63 -> T474\nT64 -> T472" } ], "type": "Graph" } } ---------------------------------------- (44) Complex Obligation (AND) ---------------------------------------- (45) Obligation: Rules: f438_out -> f429_out :|: TRUE f429_in -> f439_in :|: TRUE f439_out -> f429_out :|: TRUE f429_in -> f438_in :|: TRUE f440_in -> f423_in :|: TRUE f423_out -> f440_out :|: TRUE f428_out -> f425_out :|: TRUE f429_out -> f425_out :|: TRUE f425_in -> f429_in :|: TRUE f425_in -> f428_in :|: TRUE f438_in -> f440_in :|: TRUE f441_out -> f438_out :|: TRUE f440_out -> f441_in :|: TRUE f423_out -> f441_out :|: TRUE f441_in -> f423_in :|: TRUE f425_out -> f423_out :|: TRUE f423_in -> f425_in :|: TRUE f4_out(T2) -> f1_out(T2) :|: TRUE f1_in(x) -> f4_in(x) :|: TRUE f269_out(T11) -> f4_out(T11) :|: TRUE f4_in(x1) -> f269_in(x1) :|: TRUE f331_out(x2) -> f269_out(x2) :|: TRUE f269_in(x3) -> f331_in(x3) :|: TRUE f331_in(x4) -> f367_in(x4) :|: TRUE f331_in(x5) -> f366_in(x5) :|: TRUE f367_out(x6) -> f331_out(x6) :|: TRUE f366_out(x7) -> f331_out(x7) :|: TRUE f367_in(tree(T35, T36, T37)) -> f392_in(T35, T36, T37) :|: TRUE f367_in(x8) -> f393_in :|: TRUE f392_out(x9, x10, x11) -> f367_out(tree(x9, x10, x11)) :|: TRUE f393_out -> f367_out(x12) :|: TRUE f397_out -> f392_out(x13, x14, x15) :|: TRUE f392_in(x16, x17, x18) -> f396_in(x16, x17, x18) :|: TRUE f396_out(x19, x20, x21) -> f397_in :|: TRUE f396_in(x22, x23, x24) -> f399_in(x22, x23, x24) :|: TRUE f399_out(x25, x26, x27) -> f396_out(x25, x26, x27) :|: TRUE f399_in(x28, x29, x30) -> f400_in(x28, x29, x30) :|: TRUE f401_out(x31, x32, x33) -> f399_out(x31, x32, x33) :|: TRUE f400_out(x34, x35, x36) -> f399_out(x34, x35, x36) :|: TRUE f399_in(x37, x38, x39) -> f401_in(x37, x38, x39) :|: TRUE f401_in(tree(T155, T156, T157), T158, T160) -> f417_in(T160, T155, T156, T157, T158) :|: TRUE f418_out -> f401_out(x40, x41, x42) :|: TRUE f417_out(x43, x44, x45, x46, x47) -> f401_out(tree(x44, x45, x46), x47, x43) :|: TRUE f401_in(x48, x49, x50) -> f418_in :|: TRUE f423_out -> f417_out(x51, x52, x53, x54, x55) :|: TRUE f422_out(x56, x57, x58, x59, x60) -> f423_in :|: TRUE f417_in(x61, x62, x63, x64, x65) -> f422_in(x61, x62, x63, x64, x65) :|: TRUE f422_in(x66, x67, x68, x69, x70) -> f423_in :|: TRUE f423_out -> f422_out(x71, x72, x73, x74, x75) :|: TRUE f451_out -> f397_out :|: TRUE f397_in -> f451_in :|: TRUE f451_in -> f452_in :|: TRUE f452_out -> f451_out :|: TRUE f453_out -> f451_out :|: TRUE f451_in -> f453_in :|: TRUE f461_out -> f453_out :|: TRUE f453_in -> f461_in :|: TRUE f453_in -> f462_in :|: TRUE f462_out -> f453_out :|: TRUE f473_out -> f461_out :|: TRUE f472_out -> f473_in :|: TRUE f461_in -> f472_in :|: TRUE f423_out -> f472_out :|: TRUE f472_in -> f423_in :|: TRUE Start term: f1_in(T2) ---------------------------------------- (46) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f429_in -> f438_in :|: TRUE f440_in -> f423_in :|: TRUE f425_in -> f429_in :|: TRUE f438_in -> f440_in :|: TRUE f423_in -> f425_in :|: TRUE ---------------------------------------- (47) Obligation: Rules: f429_in -> f438_in :|: TRUE f440_in -> f423_in :|: TRUE f425_in -> f429_in :|: TRUE f438_in -> f440_in :|: TRUE f423_in -> f425_in :|: TRUE ---------------------------------------- (48) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (49) Obligation: Rules: f425_in -> f425_in :|: TRUE ---------------------------------------- (50) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (51) Obligation: Rules: f425_in -> f425_in :|: TRUE ---------------------------------------- (52) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f425_in -> f425_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (53) Obligation: Termination digraph: Nodes: (1) f425_in -> f425_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (54) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f425_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (55) Obligation: Rules: f425_in -> f425_in :|: TRUE ---------------------------------------- (56) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1) ---------------------------------------- (57) NO ---------------------------------------- (58) Obligation: Rules: f438_out -> f429_out :|: TRUE f429_in -> f439_in :|: TRUE f439_out -> f429_out :|: TRUE f429_in -> f438_in :|: TRUE f461_out -> f453_out :|: TRUE f453_in -> f461_in :|: TRUE f453_in -> f462_in :|: TRUE f462_out -> f453_out :|: TRUE f451_in -> f452_in :|: TRUE f452_out -> f451_out :|: TRUE f453_out -> f451_out :|: TRUE f451_in -> f453_in :|: TRUE f473_out -> f461_out :|: TRUE f472_out -> f473_in :|: TRUE f461_in -> f472_in :|: TRUE f440_in -> f423_in :|: TRUE f423_out -> f440_out :|: TRUE f451_out -> f397_out :|: TRUE f397_in -> f451_in :|: TRUE f428_out -> f425_out :|: TRUE f429_out -> f425_out :|: TRUE f425_in -> f429_in :|: TRUE f425_in -> f428_in :|: TRUE f428_in -> f433_in :|: TRUE f434_out -> f428_out :|: TRUE f428_in -> f434_in :|: TRUE f433_out -> f428_out :|: TRUE f438_in -> f440_in :|: TRUE f441_out -> f438_out :|: TRUE f440_out -> f441_in :|: TRUE f397_out -> f473_out :|: TRUE f473_in -> f397_in :|: TRUE f423_out -> f441_out :|: TRUE f441_in -> f423_in :|: TRUE f433_in -> f433_out :|: TRUE f423_out -> f472_out :|: TRUE f472_in -> f423_in :|: TRUE f425_out -> f423_out :|: TRUE f423_in -> f425_in :|: TRUE f4_out(T2) -> f1_out(T2) :|: TRUE f1_in(x) -> f4_in(x) :|: TRUE f269_out(T11) -> f4_out(T11) :|: TRUE f4_in(x1) -> f269_in(x1) :|: TRUE f331_out(x2) -> f269_out(x2) :|: TRUE f269_in(x3) -> f331_in(x3) :|: TRUE f331_in(x4) -> f367_in(x4) :|: TRUE f331_in(x5) -> f366_in(x5) :|: TRUE f367_out(x6) -> f331_out(x6) :|: TRUE f366_out(x7) -> f331_out(x7) :|: TRUE f367_in(tree(T35, T36, T37)) -> f392_in(T35, T36, T37) :|: TRUE f367_in(x8) -> f393_in :|: TRUE f392_out(x9, x10, x11) -> f367_out(tree(x9, x10, x11)) :|: TRUE f393_out -> f367_out(x12) :|: TRUE f397_out -> f392_out(x13, x14, x15) :|: TRUE f392_in(x16, x17, x18) -> f396_in(x16, x17, x18) :|: TRUE f396_out(x19, x20, x21) -> f397_in :|: TRUE Start term: f1_in(T2) ---------------------------------------- (59) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (60) TRUE