5.06/2.16 YES 5.06/2.18 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.06/2.18 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.06/2.18 5.06/2.18 5.06/2.18 Left Termination of the query pattern 5.06/2.18 5.06/2.18 sameleaves(g,g) 5.06/2.18 5.06/2.18 w.r.t. the given Prolog program could successfully be proven: 5.06/2.18 5.06/2.18 (0) Prolog 5.06/2.18 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.06/2.18 (2) PiTRS 5.06/2.18 (3) DependencyPairsProof [EQUIVALENT, 1 ms] 5.06/2.18 (4) PiDP 5.06/2.18 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.06/2.18 (6) AND 5.06/2.18 (7) PiDP 5.06/2.18 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.06/2.18 (9) PiDP 5.06/2.18 (10) PiDPToQDPProof [SOUND, 0 ms] 5.06/2.18 (11) QDP 5.06/2.18 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.06/2.18 (13) YES 5.06/2.18 (14) PiDP 5.06/2.18 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.06/2.18 (16) PiDP 5.06/2.18 (17) PiDPToQDPProof [SOUND, 0 ms] 5.06/2.18 (18) QDP 5.06/2.18 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.06/2.18 (20) YES 5.06/2.18 (21) PiDP 5.06/2.18 (22) UsableRulesProof [EQUIVALENT, 0 ms] 5.06/2.18 (23) PiDP 5.06/2.18 (24) PiDPToQDPProof [SOUND, 2 ms] 5.06/2.18 (25) QDP 5.06/2.18 (26) UsableRulesReductionPairsProof [EQUIVALENT, 18 ms] 5.06/2.18 (27) QDP 5.06/2.18 (28) DependencyGraphProof [EQUIVALENT, 0 ms] 5.06/2.18 (29) TRUE 5.06/2.18 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (0) 5.06/2.18 Obligation: 5.06/2.18 Clauses: 5.06/2.18 5.06/2.18 sameleaves(leaf(L), leaf(L)). 5.06/2.18 sameleaves(tree(T1, T2), tree(S1, S2)) :- ','(getleave(T1, T2, L, T), ','(getleave(S1, S2, L, S), sameleaves(T, S))). 5.06/2.18 getleave(leaf(A), C, A, C). 5.06/2.18 getleave(tree(A, B), C, L, O) :- getleave(A, tree(B, C), L, O). 5.06/2.18 5.06/2.18 5.06/2.18 Query: sameleaves(g,g) 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (1) PrologToPiTRSProof (SOUND) 5.06/2.18 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.06/2.18 5.06/2.18 sameleaves_in_2: (b,b) 5.06/2.18 5.06/2.18 getleave_in_4: (b,b,f,f) (b,b,b,f) 5.06/2.18 5.06/2.18 Transforming Prolog into the following Term Rewriting System: 5.06/2.18 5.06/2.18 Pi-finite rewrite system: 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 5.06/2.18 5.06/2.18 5.06/2.18 5.06/2.18 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.06/2.18 5.06/2.18 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (2) 5.06/2.18 Obligation: 5.06/2.18 Pi-finite rewrite system: 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (3) DependencyPairsProof (EQUIVALENT) 5.06/2.18 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> GETLEAVE_IN_GGAA(T1, T2, L, T) 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> U4_GGAA(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGAA(A, tree(B, C), L, O) 5.06/2.18 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_GG(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> GETLEAVE_IN_GGGA(S1, S2, L, S) 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> U4_GGGA(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGGA(A, tree(B, C), L, O) 5.06/2.18 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_GG(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.18 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 SAMELEAVES_IN_GG(x1, x2) = SAMELEAVES_IN_GG(x1, x2) 5.06/2.18 5.06/2.18 U1_GG(x1, x2, x3, x4, x5) = U1_GG(x3, x4, x5) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(x1, x2, x3, x4) = GETLEAVE_IN_GGAA(x1, x2) 5.06/2.18 5.06/2.18 U4_GGAA(x1, x2, x3, x4, x5, x6) = U4_GGAA(x6) 5.06/2.18 5.06/2.18 U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x5, x6) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(x1, x2, x3, x4) = GETLEAVE_IN_GGGA(x1, x2, x3) 5.06/2.18 5.06/2.18 U4_GGGA(x1, x2, x3, x4, x5, x6) = U4_GGGA(x6) 5.06/2.18 5.06/2.18 U3_GG(x1, x2, x3, x4, x5) = U3_GG(x5) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (4) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> GETLEAVE_IN_GGAA(T1, T2, L, T) 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> U4_GGAA(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGAA(A, tree(B, C), L, O) 5.06/2.18 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_GG(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> GETLEAVE_IN_GGGA(S1, S2, L, S) 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> U4_GGGA(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGGA(A, tree(B, C), L, O) 5.06/2.18 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_GG(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.18 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 SAMELEAVES_IN_GG(x1, x2) = SAMELEAVES_IN_GG(x1, x2) 5.06/2.18 5.06/2.18 U1_GG(x1, x2, x3, x4, x5) = U1_GG(x3, x4, x5) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(x1, x2, x3, x4) = GETLEAVE_IN_GGAA(x1, x2) 5.06/2.18 5.06/2.18 U4_GGAA(x1, x2, x3, x4, x5, x6) = U4_GGAA(x6) 5.06/2.18 5.06/2.18 U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x5, x6) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(x1, x2, x3, x4) = GETLEAVE_IN_GGGA(x1, x2, x3) 5.06/2.18 5.06/2.18 U4_GGGA(x1, x2, x3, x4, x5, x6) = U4_GGGA(x6) 5.06/2.18 5.06/2.18 U3_GG(x1, x2, x3, x4, x5) = U3_GG(x5) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (5) DependencyGraphProof (EQUIVALENT) 5.06/2.18 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 5 less nodes. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (6) 5.06/2.18 Complex Obligation (AND) 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (7) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGGA(A, tree(B, C), L, O) 5.06/2.18 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(x1, x2, x3, x4) = GETLEAVE_IN_GGGA(x1, x2, x3) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (8) UsableRulesProof (EQUIVALENT) 5.06/2.18 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (9) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGGA(A, tree(B, C), L, O) 5.06/2.18 5.06/2.18 R is empty. 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(x1, x2, x3, x4) = GETLEAVE_IN_GGGA(x1, x2, x3) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (10) PiDPToQDPProof (SOUND) 5.06/2.18 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (11) 5.06/2.18 Obligation: 5.06/2.18 Q DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGGA(tree(A, B), C, L) -> GETLEAVE_IN_GGGA(A, tree(B, C), L) 5.06/2.18 5.06/2.18 R is empty. 5.06/2.18 Q is empty. 5.06/2.18 We have to consider all (P,Q,R)-chains. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (12) QDPSizeChangeProof (EQUIVALENT) 5.06/2.18 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.06/2.18 5.06/2.18 From the DPs we obtained the following set of size-change graphs: 5.06/2.18 *GETLEAVE_IN_GGGA(tree(A, B), C, L) -> GETLEAVE_IN_GGGA(A, tree(B, C), L) 5.06/2.18 The graph contains the following edges 1 > 1, 3 >= 3 5.06/2.18 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (13) 5.06/2.18 YES 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (14) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGAA(A, tree(B, C), L, O) 5.06/2.18 5.06/2.18 The TRS R consists of the following rules: 5.06/2.18 5.06/2.18 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.18 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.18 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.18 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.18 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.18 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.18 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.18 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.18 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.18 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.18 5.06/2.18 leaf(x1) = leaf(x1) 5.06/2.18 5.06/2.18 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.18 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.18 5.06/2.18 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.18 5.06/2.18 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.18 5.06/2.18 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.18 5.06/2.18 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.18 5.06/2.18 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.18 5.06/2.18 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.18 5.06/2.18 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.18 5.06/2.18 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(x1, x2, x3, x4) = GETLEAVE_IN_GGAA(x1, x2) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (15) UsableRulesProof (EQUIVALENT) 5.06/2.18 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (16) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C, L, O) -> GETLEAVE_IN_GGAA(A, tree(B, C), L, O) 5.06/2.18 5.06/2.18 R is empty. 5.06/2.18 The argument filtering Pi contains the following mapping: 5.06/2.18 tree(x1, x2) = tree(x1, x2) 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(x1, x2, x3, x4) = GETLEAVE_IN_GGAA(x1, x2) 5.06/2.18 5.06/2.18 5.06/2.18 We have to consider all (P,R,Pi)-chains 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (17) PiDPToQDPProof (SOUND) 5.06/2.18 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (18) 5.06/2.18 Obligation: 5.06/2.18 Q DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 GETLEAVE_IN_GGAA(tree(A, B), C) -> GETLEAVE_IN_GGAA(A, tree(B, C)) 5.06/2.18 5.06/2.18 R is empty. 5.06/2.18 Q is empty. 5.06/2.18 We have to consider all (P,Q,R)-chains. 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (19) QDPSizeChangeProof (EQUIVALENT) 5.06/2.18 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.06/2.18 5.06/2.18 From the DPs we obtained the following set of size-change graphs: 5.06/2.18 *GETLEAVE_IN_GGAA(tree(A, B), C) -> GETLEAVE_IN_GGAA(A, tree(B, C)) 5.06/2.18 The graph contains the following edges 1 > 1 5.06/2.18 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (20) 5.06/2.18 YES 5.06/2.18 5.06/2.18 ---------------------------------------- 5.06/2.18 5.06/2.18 (21) 5.06/2.18 Obligation: 5.06/2.18 Pi DP problem: 5.06/2.18 The TRS P consists of the following rules: 5.06/2.18 5.06/2.18 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_GG(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.18 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.19 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.19 5.06/2.19 The TRS R consists of the following rules: 5.06/2.19 5.06/2.19 sameleaves_in_gg(leaf(L), leaf(L)) -> sameleaves_out_gg(leaf(L), leaf(L)) 5.06/2.19 sameleaves_in_gg(tree(T1, T2), tree(S1, S2)) -> U1_gg(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.19 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.19 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.19 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.19 U1_gg(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_gg(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.19 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.19 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.19 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.19 U2_gg(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> U3_gg(T1, T2, S1, S2, sameleaves_in_gg(T, S)) 5.06/2.19 U3_gg(T1, T2, S1, S2, sameleaves_out_gg(T, S)) -> sameleaves_out_gg(tree(T1, T2), tree(S1, S2)) 5.06/2.19 5.06/2.19 The argument filtering Pi contains the following mapping: 5.06/2.19 sameleaves_in_gg(x1, x2) = sameleaves_in_gg(x1, x2) 5.06/2.19 5.06/2.19 leaf(x1) = leaf(x1) 5.06/2.19 5.06/2.19 sameleaves_out_gg(x1, x2) = sameleaves_out_gg 5.06/2.19 5.06/2.19 tree(x1, x2) = tree(x1, x2) 5.06/2.19 5.06/2.19 U1_gg(x1, x2, x3, x4, x5) = U1_gg(x3, x4, x5) 5.06/2.19 5.06/2.19 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.19 5.06/2.19 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.19 5.06/2.19 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.19 5.06/2.19 U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x5, x6) 5.06/2.19 5.06/2.19 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.19 5.06/2.19 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.19 5.06/2.19 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.19 5.06/2.19 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.06/2.19 5.06/2.19 SAMELEAVES_IN_GG(x1, x2) = SAMELEAVES_IN_GG(x1, x2) 5.06/2.19 5.06/2.19 U1_GG(x1, x2, x3, x4, x5) = U1_GG(x3, x4, x5) 5.06/2.19 5.06/2.19 U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x5, x6) 5.06/2.19 5.06/2.19 5.06/2.19 We have to consider all (P,R,Pi)-chains 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (22) UsableRulesProof (EQUIVALENT) 5.06/2.19 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (23) 5.06/2.19 Obligation: 5.06/2.19 Pi DP problem: 5.06/2.19 The TRS P consists of the following rules: 5.06/2.19 5.06/2.19 U1_GG(T1, T2, S1, S2, getleave_out_ggaa(T1, T2, L, T)) -> U2_GG(T1, T2, S1, S2, T, getleave_in_ggga(S1, S2, L, S)) 5.06/2.19 U2_GG(T1, T2, S1, S2, T, getleave_out_ggga(S1, S2, L, S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.19 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(T1, T2, S1, S2, getleave_in_ggaa(T1, T2, L, T)) 5.06/2.19 5.06/2.19 The TRS R consists of the following rules: 5.06/2.19 5.06/2.19 getleave_in_ggga(leaf(A), C, A, C) -> getleave_out_ggga(leaf(A), C, A, C) 5.06/2.19 getleave_in_ggga(tree(A, B), C, L, O) -> U4_ggga(A, B, C, L, O, getleave_in_ggga(A, tree(B, C), L, O)) 5.06/2.19 getleave_in_ggaa(leaf(A), C, A, C) -> getleave_out_ggaa(leaf(A), C, A, C) 5.06/2.19 getleave_in_ggaa(tree(A, B), C, L, O) -> U4_ggaa(A, B, C, L, O, getleave_in_ggaa(A, tree(B, C), L, O)) 5.06/2.19 U4_ggga(A, B, C, L, O, getleave_out_ggga(A, tree(B, C), L, O)) -> getleave_out_ggga(tree(A, B), C, L, O) 5.06/2.19 U4_ggaa(A, B, C, L, O, getleave_out_ggaa(A, tree(B, C), L, O)) -> getleave_out_ggaa(tree(A, B), C, L, O) 5.06/2.19 5.06/2.19 The argument filtering Pi contains the following mapping: 5.06/2.19 leaf(x1) = leaf(x1) 5.06/2.19 5.06/2.19 tree(x1, x2) = tree(x1, x2) 5.06/2.19 5.06/2.19 getleave_in_ggaa(x1, x2, x3, x4) = getleave_in_ggaa(x1, x2) 5.06/2.19 5.06/2.19 getleave_out_ggaa(x1, x2, x3, x4) = getleave_out_ggaa(x3, x4) 5.06/2.19 5.06/2.19 U4_ggaa(x1, x2, x3, x4, x5, x6) = U4_ggaa(x6) 5.06/2.19 5.06/2.19 getleave_in_ggga(x1, x2, x3, x4) = getleave_in_ggga(x1, x2, x3) 5.06/2.19 5.06/2.19 getleave_out_ggga(x1, x2, x3, x4) = getleave_out_ggga(x4) 5.06/2.19 5.06/2.19 U4_ggga(x1, x2, x3, x4, x5, x6) = U4_ggga(x6) 5.06/2.19 5.06/2.19 SAMELEAVES_IN_GG(x1, x2) = SAMELEAVES_IN_GG(x1, x2) 5.06/2.19 5.06/2.19 U1_GG(x1, x2, x3, x4, x5) = U1_GG(x3, x4, x5) 5.06/2.19 5.06/2.19 U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x5, x6) 5.06/2.19 5.06/2.19 5.06/2.19 We have to consider all (P,R,Pi)-chains 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (24) PiDPToQDPProof (SOUND) 5.06/2.19 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (25) 5.06/2.19 Obligation: 5.06/2.19 Q DP problem: 5.06/2.19 The TRS P consists of the following rules: 5.06/2.19 5.06/2.19 U1_GG(S1, S2, getleave_out_ggaa(L, T)) -> U2_GG(T, getleave_in_ggga(S1, S2, L)) 5.06/2.19 U2_GG(T, getleave_out_ggga(S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.19 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(S1, S2, getleave_in_ggaa(T1, T2)) 5.06/2.19 5.06/2.19 The TRS R consists of the following rules: 5.06/2.19 5.06/2.19 getleave_in_ggga(leaf(A), C, A) -> getleave_out_ggga(C) 5.06/2.19 getleave_in_ggga(tree(A, B), C, L) -> U4_ggga(getleave_in_ggga(A, tree(B, C), L)) 5.06/2.19 getleave_in_ggaa(leaf(A), C) -> getleave_out_ggaa(A, C) 5.06/2.19 getleave_in_ggaa(tree(A, B), C) -> U4_ggaa(getleave_in_ggaa(A, tree(B, C))) 5.06/2.19 U4_ggga(getleave_out_ggga(O)) -> getleave_out_ggga(O) 5.06/2.19 U4_ggaa(getleave_out_ggaa(L, O)) -> getleave_out_ggaa(L, O) 5.06/2.19 5.06/2.19 The set Q consists of the following terms: 5.06/2.19 5.06/2.19 getleave_in_ggga(x0, x1, x2) 5.06/2.19 getleave_in_ggaa(x0, x1) 5.06/2.19 U4_ggga(x0) 5.06/2.19 U4_ggaa(x0) 5.06/2.19 5.06/2.19 We have to consider all (P,Q,R)-chains. 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (26) UsableRulesReductionPairsProof (EQUIVALENT) 5.06/2.19 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.06/2.19 5.06/2.19 The following dependency pairs can be deleted: 5.06/2.19 5.06/2.19 SAMELEAVES_IN_GG(tree(T1, T2), tree(S1, S2)) -> U1_GG(S1, S2, getleave_in_ggaa(T1, T2)) 5.06/2.19 The following rules are removed from R: 5.06/2.19 5.06/2.19 getleave_in_ggga(leaf(A), C, A) -> getleave_out_ggga(C) 5.06/2.19 getleave_in_ggaa(leaf(A), C) -> getleave_out_ggaa(A, C) 5.06/2.19 Used ordering: POLO with Polynomial interpretation [POLO]: 5.06/2.19 5.06/2.19 POL(SAMELEAVES_IN_GG(x_1, x_2)) = 2*x_1 + x_2 5.06/2.19 POL(U1_GG(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.06/2.19 POL(U2_GG(x_1, x_2)) = 2*x_1 + x_2 5.06/2.19 POL(U4_ggaa(x_1)) = x_1 5.06/2.19 POL(U4_ggga(x_1)) = x_1 5.06/2.19 POL(getleave_in_ggaa(x_1, x_2)) = x_1 + x_2 5.06/2.19 POL(getleave_in_ggga(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.06/2.19 POL(getleave_out_ggaa(x_1, x_2)) = 2*x_1 + x_2 5.06/2.19 POL(getleave_out_ggga(x_1)) = x_1 5.06/2.19 POL(leaf(x_1)) = 2*x_1 5.06/2.19 POL(tree(x_1, x_2)) = 1 + x_1 + x_2 5.06/2.19 5.06/2.19 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (27) 5.06/2.19 Obligation: 5.06/2.19 Q DP problem: 5.06/2.19 The TRS P consists of the following rules: 5.06/2.19 5.06/2.19 U1_GG(S1, S2, getleave_out_ggaa(L, T)) -> U2_GG(T, getleave_in_ggga(S1, S2, L)) 5.06/2.19 U2_GG(T, getleave_out_ggga(S)) -> SAMELEAVES_IN_GG(T, S) 5.06/2.19 5.06/2.19 The TRS R consists of the following rules: 5.06/2.19 5.06/2.19 getleave_in_ggaa(tree(A, B), C) -> U4_ggaa(getleave_in_ggaa(A, tree(B, C))) 5.06/2.19 U4_ggaa(getleave_out_ggaa(L, O)) -> getleave_out_ggaa(L, O) 5.06/2.19 getleave_in_ggga(tree(A, B), C, L) -> U4_ggga(getleave_in_ggga(A, tree(B, C), L)) 5.06/2.19 U4_ggga(getleave_out_ggga(O)) -> getleave_out_ggga(O) 5.06/2.19 5.06/2.19 The set Q consists of the following terms: 5.06/2.19 5.06/2.19 getleave_in_ggga(x0, x1, x2) 5.06/2.19 getleave_in_ggaa(x0, x1) 5.06/2.19 U4_ggga(x0) 5.06/2.19 U4_ggaa(x0) 5.06/2.19 5.06/2.19 We have to consider all (P,Q,R)-chains. 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (28) DependencyGraphProof (EQUIVALENT) 5.06/2.19 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 5.06/2.19 ---------------------------------------- 5.06/2.19 5.06/2.19 (29) 5.06/2.19 TRUE 5.38/2.24 EOF