4.02/1.88 YES 4.02/1.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.02/1.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.02/1.89 4.02/1.89 4.02/1.89 Left Termination of the query pattern 4.02/1.89 4.02/1.89 goal(g) 4.02/1.89 4.02/1.89 w.r.t. the given Prolog program could successfully be proven: 4.02/1.89 4.02/1.89 (0) Prolog 4.02/1.89 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.02/1.89 (2) PiTRS 4.02/1.89 (3) DependencyPairsProof [EQUIVALENT, 16 ms] 4.02/1.89 (4) PiDP 4.02/1.89 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.02/1.89 (6) AND 4.02/1.89 (7) PiDP 4.02/1.89 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.02/1.89 (9) PiDP 4.02/1.89 (10) PiDPToQDPProof [SOUND, 4 ms] 4.02/1.89 (11) QDP 4.02/1.89 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.02/1.89 (13) YES 4.02/1.89 (14) PiDP 4.02/1.89 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.02/1.89 (16) PiDP 4.02/1.89 (17) PiDPToQDPProof [SOUND, 0 ms] 4.02/1.89 (18) QDP 4.02/1.89 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.02/1.89 (20) YES 4.02/1.89 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (0) 4.02/1.89 Obligation: 4.02/1.89 Clauses: 4.02/1.89 4.02/1.89 tappend(nil, T, T). 4.02/1.89 tappend(node(nil, X, T2), T1, node(T1, X, T2)). 4.02/1.89 tappend(node(T1, X, nil), T2, node(T1, X, T2)). 4.02/1.89 tappend(node(T1, X, T2), T3, node(U, X, T2)) :- tappend(T1, T3, U). 4.02/1.89 tappend(node(T1, X, T2), T3, node(T1, X, U)) :- tappend(T2, T3, U). 4.02/1.89 s2t(s(X), node(T, Y, T)) :- s2t(X, T). 4.02/1.89 s2t(s(X), node(nil, Y, T)) :- s2t(X, T). 4.02/1.89 s2t(s(X), node(T, Y, nil)) :- s2t(X, T). 4.02/1.89 s2t(s(X), node(nil, Y, nil)). 4.02/1.89 s2t(0, nil). 4.02/1.89 goal(X) :- ','(s2t(X, T1), tappend(T1, T2, T3)). 4.02/1.89 4.02/1.89 4.02/1.89 Query: goal(g) 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (1) PrologToPiTRSProof (SOUND) 4.02/1.89 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.02/1.89 4.02/1.89 goal_in_1: (b) 4.02/1.89 4.02/1.89 s2t_in_2: (b,f) 4.02/1.89 4.02/1.89 tappend_in_3: (b,f,f) 4.02/1.89 4.02/1.89 Transforming Prolog into the following Term Rewriting System: 4.02/1.89 4.02/1.89 Pi-finite rewrite system: 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.89 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.89 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.89 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 goal_in_g(x1) = goal_in_g(x1) 4.02/1.89 4.02/1.89 U6_g(x1, x2) = U6_g(x2) 4.02/1.89 4.02/1.89 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.89 4.02/1.89 s(x1) = s(x1) 4.02/1.89 4.02/1.89 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.89 4.02/1.89 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.89 4.02/1.89 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.89 4.02/1.89 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.89 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 0 = 0 4.02/1.89 4.02/1.89 U7_g(x1, x2) = U7_g(x2) 4.02/1.89 4.02/1.89 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.89 4.02/1.89 nil = nil 4.02/1.89 4.02/1.89 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.89 4.02/1.89 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.89 4.02/1.89 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.89 4.02/1.89 goal_out_g(x1) = goal_out_g 4.02/1.89 4.02/1.89 4.02/1.89 4.02/1.89 4.02/1.89 4.02/1.89 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.02/1.89 4.02/1.89 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (2) 4.02/1.89 Obligation: 4.02/1.89 Pi-finite rewrite system: 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.89 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.89 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.89 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 goal_in_g(x1) = goal_in_g(x1) 4.02/1.89 4.02/1.89 U6_g(x1, x2) = U6_g(x2) 4.02/1.89 4.02/1.89 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.89 4.02/1.89 s(x1) = s(x1) 4.02/1.89 4.02/1.89 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.89 4.02/1.89 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.89 4.02/1.89 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.89 4.02/1.89 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.89 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 0 = 0 4.02/1.89 4.02/1.89 U7_g(x1, x2) = U7_g(x2) 4.02/1.89 4.02/1.89 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.89 4.02/1.89 nil = nil 4.02/1.89 4.02/1.89 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.89 4.02/1.89 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.89 4.02/1.89 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.89 4.02/1.89 goal_out_g(x1) = goal_out_g 4.02/1.89 4.02/1.89 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (3) DependencyPairsProof (EQUIVALENT) 4.02/1.89 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.02/1.89 Pi DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 GOAL_IN_G(X) -> U6_G(X, s2t_in_ga(X, T1)) 4.02/1.89 GOAL_IN_G(X) -> S2T_IN_GA(X, T1) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, T)) -> U3_GA(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(nil, Y, T)) -> U4_GA(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(nil, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, nil)) -> U5_GA(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, nil)) -> S2T_IN_GA(X, T) 4.02/1.89 U6_G(X, s2t_out_ga(X, T1)) -> U7_G(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 U6_G(X, s2t_out_ga(X, T1)) -> TAPPEND_IN_GAA(T1, T2, T3) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> U1_GAA(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> TAPPEND_IN_GAA(T1, T3, U) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> U2_GAA(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> TAPPEND_IN_GAA(T2, T3, U) 4.02/1.89 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.89 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.89 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.89 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 goal_in_g(x1) = goal_in_g(x1) 4.02/1.89 4.02/1.89 U6_g(x1, x2) = U6_g(x2) 4.02/1.89 4.02/1.89 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.89 4.02/1.89 s(x1) = s(x1) 4.02/1.89 4.02/1.89 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.89 4.02/1.89 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.89 4.02/1.89 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.89 4.02/1.89 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.89 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 0 = 0 4.02/1.89 4.02/1.89 U7_g(x1, x2) = U7_g(x2) 4.02/1.89 4.02/1.89 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.89 4.02/1.89 nil = nil 4.02/1.89 4.02/1.89 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.89 4.02/1.89 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.89 4.02/1.89 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.89 4.02/1.89 goal_out_g(x1) = goal_out_g 4.02/1.89 4.02/1.89 GOAL_IN_G(x1) = GOAL_IN_G(x1) 4.02/1.89 4.02/1.89 U6_G(x1, x2) = U6_G(x2) 4.02/1.89 4.02/1.89 S2T_IN_GA(x1, x2) = S2T_IN_GA(x1) 4.02/1.89 4.02/1.89 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.02/1.89 4.02/1.89 U4_GA(x1, x2, x3, x4) = U4_GA(x4) 4.02/1.89 4.02/1.89 U5_GA(x1, x2, x3, x4) = U5_GA(x4) 4.02/1.89 4.02/1.89 U7_G(x1, x2) = U7_G(x2) 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(x1, x2, x3) = TAPPEND_IN_GAA(x1) 4.02/1.89 4.02/1.89 U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x6) 4.02/1.89 4.02/1.89 U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x6) 4.02/1.89 4.02/1.89 4.02/1.89 We have to consider all (P,R,Pi)-chains 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (4) 4.02/1.89 Obligation: 4.02/1.89 Pi DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 GOAL_IN_G(X) -> U6_G(X, s2t_in_ga(X, T1)) 4.02/1.89 GOAL_IN_G(X) -> S2T_IN_GA(X, T1) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, T)) -> U3_GA(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(nil, Y, T)) -> U4_GA(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(nil, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, nil)) -> U5_GA(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, nil)) -> S2T_IN_GA(X, T) 4.02/1.89 U6_G(X, s2t_out_ga(X, T1)) -> U7_G(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 U6_G(X, s2t_out_ga(X, T1)) -> TAPPEND_IN_GAA(T1, T2, T3) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> U1_GAA(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> TAPPEND_IN_GAA(T1, T3, U) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> U2_GAA(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> TAPPEND_IN_GAA(T2, T3, U) 4.02/1.89 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.89 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.89 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.89 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 goal_in_g(x1) = goal_in_g(x1) 4.02/1.89 4.02/1.89 U6_g(x1, x2) = U6_g(x2) 4.02/1.89 4.02/1.89 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.89 4.02/1.89 s(x1) = s(x1) 4.02/1.89 4.02/1.89 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.89 4.02/1.89 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.89 4.02/1.89 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.89 4.02/1.89 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.89 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 0 = 0 4.02/1.89 4.02/1.89 U7_g(x1, x2) = U7_g(x2) 4.02/1.89 4.02/1.89 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.89 4.02/1.89 nil = nil 4.02/1.89 4.02/1.89 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.89 4.02/1.89 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.89 4.02/1.89 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.89 4.02/1.89 goal_out_g(x1) = goal_out_g 4.02/1.89 4.02/1.89 GOAL_IN_G(x1) = GOAL_IN_G(x1) 4.02/1.89 4.02/1.89 U6_G(x1, x2) = U6_G(x2) 4.02/1.89 4.02/1.89 S2T_IN_GA(x1, x2) = S2T_IN_GA(x1) 4.02/1.89 4.02/1.89 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.02/1.89 4.02/1.89 U4_GA(x1, x2, x3, x4) = U4_GA(x4) 4.02/1.89 4.02/1.89 U5_GA(x1, x2, x3, x4) = U5_GA(x4) 4.02/1.89 4.02/1.89 U7_G(x1, x2) = U7_G(x2) 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(x1, x2, x3) = TAPPEND_IN_GAA(x1) 4.02/1.89 4.02/1.89 U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x6) 4.02/1.89 4.02/1.89 U2_GAA(x1, x2, x3, x4, x5, x6) = U2_GAA(x6) 4.02/1.89 4.02/1.89 4.02/1.89 We have to consider all (P,R,Pi)-chains 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (5) DependencyGraphProof (EQUIVALENT) 4.02/1.89 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 9 less nodes. 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (6) 4.02/1.89 Complex Obligation (AND) 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (7) 4.02/1.89 Obligation: 4.02/1.89 Pi DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> TAPPEND_IN_GAA(T2, T3, U) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> TAPPEND_IN_GAA(T1, T3, U) 4.02/1.89 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.89 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.89 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.89 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.89 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 goal_in_g(x1) = goal_in_g(x1) 4.02/1.89 4.02/1.89 U6_g(x1, x2) = U6_g(x2) 4.02/1.89 4.02/1.89 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.89 4.02/1.89 s(x1) = s(x1) 4.02/1.89 4.02/1.89 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.89 4.02/1.89 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.89 4.02/1.89 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.89 4.02/1.89 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.89 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 0 = 0 4.02/1.89 4.02/1.89 U7_g(x1, x2) = U7_g(x2) 4.02/1.89 4.02/1.89 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.89 4.02/1.89 nil = nil 4.02/1.89 4.02/1.89 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.89 4.02/1.89 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.89 4.02/1.89 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.89 4.02/1.89 goal_out_g(x1) = goal_out_g 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(x1, x2, x3) = TAPPEND_IN_GAA(x1) 4.02/1.89 4.02/1.89 4.02/1.89 We have to consider all (P,R,Pi)-chains 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (8) UsableRulesProof (EQUIVALENT) 4.02/1.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (9) 4.02/1.89 Obligation: 4.02/1.89 Pi DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(T1, X, U)) -> TAPPEND_IN_GAA(T2, T3, U) 4.02/1.89 TAPPEND_IN_GAA(node(T1, X, T2), T3, node(U, X, T2)) -> TAPPEND_IN_GAA(T1, T3, U) 4.02/1.89 4.02/1.89 R is empty. 4.02/1.89 The argument filtering Pi contains the following mapping: 4.02/1.89 node(x1, x2, x3) = node(x1, x3) 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(x1, x2, x3) = TAPPEND_IN_GAA(x1) 4.02/1.89 4.02/1.89 4.02/1.89 We have to consider all (P,R,Pi)-chains 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (10) PiDPToQDPProof (SOUND) 4.02/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (11) 4.02/1.89 Obligation: 4.02/1.89 Q DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 TAPPEND_IN_GAA(node(T1, T2)) -> TAPPEND_IN_GAA(T2) 4.02/1.89 TAPPEND_IN_GAA(node(T1, T2)) -> TAPPEND_IN_GAA(T1) 4.02/1.89 4.02/1.89 R is empty. 4.02/1.89 Q is empty. 4.02/1.89 We have to consider all (P,Q,R)-chains. 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (12) QDPSizeChangeProof (EQUIVALENT) 4.02/1.89 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.02/1.89 4.02/1.89 From the DPs we obtained the following set of size-change graphs: 4.02/1.89 *TAPPEND_IN_GAA(node(T1, T2)) -> TAPPEND_IN_GAA(T2) 4.02/1.89 The graph contains the following edges 1 > 1 4.02/1.89 4.02/1.89 4.02/1.89 *TAPPEND_IN_GAA(node(T1, T2)) -> TAPPEND_IN_GAA(T1) 4.02/1.89 The graph contains the following edges 1 > 1 4.02/1.89 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (13) 4.02/1.89 YES 4.02/1.89 4.02/1.89 ---------------------------------------- 4.02/1.89 4.02/1.89 (14) 4.02/1.89 Obligation: 4.02/1.89 Pi DP problem: 4.02/1.89 The TRS P consists of the following rules: 4.02/1.89 4.02/1.89 S2T_IN_GA(s(X), node(nil, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.89 S2T_IN_GA(s(X), node(T, Y, nil)) -> S2T_IN_GA(X, T) 4.02/1.89 4.02/1.89 The TRS R consists of the following rules: 4.02/1.89 4.02/1.89 goal_in_g(X) -> U6_g(X, s2t_in_ga(X, T1)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, T)) -> U3_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, T)) -> U4_ga(X, Y, T, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(T, Y, nil)) -> U5_ga(X, T, Y, s2t_in_ga(X, T)) 4.02/1.89 s2t_in_ga(s(X), node(nil, Y, nil)) -> s2t_out_ga(s(X), node(nil, Y, nil)) 4.02/1.89 s2t_in_ga(0, nil) -> s2t_out_ga(0, nil) 4.02/1.89 U5_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, nil)) 4.02/1.89 U4_ga(X, Y, T, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(nil, Y, T)) 4.02/1.89 U3_ga(X, T, Y, s2t_out_ga(X, T)) -> s2t_out_ga(s(X), node(T, Y, T)) 4.02/1.89 U6_g(X, s2t_out_ga(X, T1)) -> U7_g(X, tappend_in_gaa(T1, T2, T3)) 4.02/1.89 tappend_in_gaa(nil, T, T) -> tappend_out_gaa(nil, T, T) 4.02/1.89 tappend_in_gaa(node(nil, X, T2), T1, node(T1, X, T2)) -> tappend_out_gaa(node(nil, X, T2), T1, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, nil), T2, node(T1, X, T2)) -> tappend_out_gaa(node(T1, X, nil), T2, node(T1, X, T2)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(U, X, T2)) -> U1_gaa(T1, X, T2, T3, U, tappend_in_gaa(T1, T3, U)) 4.02/1.89 tappend_in_gaa(node(T1, X, T2), T3, node(T1, X, U)) -> U2_gaa(T1, X, T2, T3, U, tappend_in_gaa(T2, T3, U)) 4.02/1.90 U2_gaa(T1, X, T2, T3, U, tappend_out_gaa(T2, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(T1, X, U)) 4.02/1.90 U1_gaa(T1, X, T2, T3, U, tappend_out_gaa(T1, T3, U)) -> tappend_out_gaa(node(T1, X, T2), T3, node(U, X, T2)) 4.02/1.90 U7_g(X, tappend_out_gaa(T1, T2, T3)) -> goal_out_g(X) 4.02/1.90 4.02/1.90 The argument filtering Pi contains the following mapping: 4.02/1.90 goal_in_g(x1) = goal_in_g(x1) 4.02/1.90 4.02/1.90 U6_g(x1, x2) = U6_g(x2) 4.02/1.90 4.02/1.90 s2t_in_ga(x1, x2) = s2t_in_ga(x1) 4.02/1.90 4.02/1.90 s(x1) = s(x1) 4.02/1.90 4.02/1.90 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.02/1.90 4.02/1.90 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 4.02/1.90 4.02/1.90 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.02/1.90 4.02/1.90 s2t_out_ga(x1, x2) = s2t_out_ga(x2) 4.02/1.90 4.02/1.90 node(x1, x2, x3) = node(x1, x3) 4.02/1.90 4.02/1.90 0 = 0 4.02/1.90 4.02/1.90 U7_g(x1, x2) = U7_g(x2) 4.02/1.90 4.02/1.90 tappend_in_gaa(x1, x2, x3) = tappend_in_gaa(x1) 4.02/1.90 4.02/1.90 nil = nil 4.02/1.90 4.02/1.90 tappend_out_gaa(x1, x2, x3) = tappend_out_gaa 4.02/1.90 4.02/1.90 U1_gaa(x1, x2, x3, x4, x5, x6) = U1_gaa(x6) 4.02/1.90 4.02/1.90 U2_gaa(x1, x2, x3, x4, x5, x6) = U2_gaa(x6) 4.02/1.90 4.02/1.90 goal_out_g(x1) = goal_out_g 4.02/1.90 4.02/1.90 S2T_IN_GA(x1, x2) = S2T_IN_GA(x1) 4.02/1.90 4.02/1.90 4.02/1.90 We have to consider all (P,R,Pi)-chains 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (15) UsableRulesProof (EQUIVALENT) 4.02/1.90 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (16) 4.02/1.90 Obligation: 4.02/1.90 Pi DP problem: 4.02/1.90 The TRS P consists of the following rules: 4.02/1.90 4.02/1.90 S2T_IN_GA(s(X), node(nil, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.90 S2T_IN_GA(s(X), node(T, Y, T)) -> S2T_IN_GA(X, T) 4.02/1.90 S2T_IN_GA(s(X), node(T, Y, nil)) -> S2T_IN_GA(X, T) 4.02/1.90 4.02/1.90 R is empty. 4.02/1.90 The argument filtering Pi contains the following mapping: 4.02/1.90 s(x1) = s(x1) 4.02/1.90 4.02/1.90 node(x1, x2, x3) = node(x1, x3) 4.02/1.90 4.02/1.90 nil = nil 4.02/1.90 4.02/1.90 S2T_IN_GA(x1, x2) = S2T_IN_GA(x1) 4.02/1.90 4.02/1.90 4.02/1.90 We have to consider all (P,R,Pi)-chains 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (17) PiDPToQDPProof (SOUND) 4.02/1.90 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (18) 4.02/1.90 Obligation: 4.02/1.90 Q DP problem: 4.02/1.90 The TRS P consists of the following rules: 4.02/1.90 4.02/1.90 S2T_IN_GA(s(X)) -> S2T_IN_GA(X) 4.02/1.90 4.02/1.90 R is empty. 4.02/1.90 Q is empty. 4.02/1.90 We have to consider all (P,Q,R)-chains. 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (19) QDPSizeChangeProof (EQUIVALENT) 4.02/1.90 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.02/1.90 4.02/1.90 From the DPs we obtained the following set of size-change graphs: 4.02/1.90 *S2T_IN_GA(s(X)) -> S2T_IN_GA(X) 4.02/1.90 The graph contains the following edges 1 > 1 4.02/1.90 4.02/1.90 4.02/1.90 ---------------------------------------- 4.02/1.90 4.02/1.90 (20) 4.02/1.90 YES 4.32/1.91 EOF