13.32/4.25 YES 13.58/4.27 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 13.58/4.27 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.58/4.27 13.58/4.27 13.58/4.27 Left Termination of the query pattern 13.58/4.27 13.58/4.27 q(g,g) 13.58/4.27 13.58/4.27 w.r.t. the given Prolog program could successfully be proven: 13.58/4.27 13.58/4.27 (0) Prolog 13.58/4.27 (1) PrologToPiTRSProof [SOUND, 0 ms] 13.58/4.27 (2) PiTRS 13.58/4.27 (3) DependencyPairsProof [EQUIVALENT, 30 ms] 13.58/4.27 (4) PiDP 13.58/4.27 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 13.58/4.27 (6) PiDP 13.58/4.27 (7) PiDPToQDPProof [SOUND, 6 ms] 13.58/4.27 (8) QDP 13.58/4.27 (9) QDPQMonotonicMRRProof [EQUIVALENT, 315 ms] 13.58/4.27 (10) QDP 13.58/4.27 (11) DependencyGraphProof [EQUIVALENT, 2 ms] 13.58/4.27 (12) QDP 13.58/4.27 (13) UsableRulesProof [EQUIVALENT, 0 ms] 13.58/4.27 (14) QDP 13.58/4.27 (15) QReductionProof [EQUIVALENT, 0 ms] 13.58/4.27 (16) QDP 13.58/4.27 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.58/4.27 (18) YES 13.58/4.27 13.58/4.27 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (0) 13.58/4.27 Obligation: 13.58/4.27 Clauses: 13.58/4.27 13.58/4.27 e(a, b). 13.58/4.27 q(X, Y) :- e(X, Y). 13.58/4.27 q(X, f(f(X))) :- ','(p(X, f(f(X))), q(X, f(X))). 13.58/4.27 q(X, f(f(Y))) :- p(X, f(Y)). 13.58/4.27 p(X, Y) :- e(X, Y). 13.58/4.27 p(X, f(Y)) :- ','(r(X, f(Y)), p(X, Y)). 13.58/4.27 r(X, Y) :- e(X, Y). 13.58/4.27 r(X, f(Y)) :- ','(q(X, Y), r(X, Y)). 13.58/4.27 r(f(X), f(X)) :- t(f(X), f(X)). 13.58/4.27 t(X, Y) :- e(X, Y). 13.58/4.27 t(f(X), f(Y)) :- ','(q(f(X), f(Y)), t(X, Y)). 13.58/4.27 13.58/4.27 13.58/4.27 Query: q(g,g) 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (1) PrologToPiTRSProof (SOUND) 13.58/4.27 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 13.58/4.27 13.58/4.27 q_in_2: (b,b) 13.58/4.27 13.58/4.27 p_in_2: (b,b) 13.58/4.27 13.58/4.27 r_in_2: (b,b) 13.58/4.27 13.58/4.27 t_in_2: (b,b) 13.58/4.27 13.58/4.27 Transforming Prolog into the following Term Rewriting System: 13.58/4.27 13.58/4.27 Pi-finite rewrite system: 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg(a, b) 13.58/4.27 U1_gg(X, Y, e_out_gg(X, Y)) -> q_out_gg(X, Y) 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U5_gg(X, Y, e_out_gg(X, Y)) -> p_out_gg(X, Y) 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U8_gg(X, Y, e_out_gg(X, Y)) -> r_out_gg(X, Y) 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(X, Y, p_out_gg(X, f(Y))) -> q_out_gg(X, f(f(Y))) 13.58/4.27 U9_gg(X, Y, q_out_gg(X, Y)) -> U10_gg(X, Y, r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(X, t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U12_gg(X, Y, e_out_gg(X, Y)) -> t_out_gg(X, Y) 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg(f(X), f(Y))) -> U14_gg(X, Y, t_in_gg(X, Y)) 13.58/4.27 U14_gg(X, Y, t_out_gg(X, Y)) -> t_out_gg(f(X), f(Y)) 13.58/4.27 U11_gg(X, t_out_gg(f(X), f(X))) -> r_out_gg(f(X), f(X)) 13.58/4.27 U10_gg(X, Y, r_out_gg(X, Y)) -> r_out_gg(X, f(Y)) 13.58/4.27 U6_gg(X, Y, r_out_gg(X, f(Y))) -> U7_gg(X, Y, p_in_gg(X, Y)) 13.58/4.27 U7_gg(X, Y, p_out_gg(X, Y)) -> p_out_gg(X, f(Y)) 13.58/4.27 U2_gg(X, p_out_gg(X, f(f(X)))) -> U3_gg(X, q_in_gg(X, f(X))) 13.58/4.27 U3_gg(X, q_out_gg(X, f(X))) -> q_out_gg(X, f(f(X))) 13.58/4.27 13.58/4.27 The argument filtering Pi contains the following mapping: 13.58/4.27 q_in_gg(x1, x2) = q_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U1_gg(x1, x2, x3) = U1_gg(x3) 13.58/4.27 13.58/4.27 e_in_gg(x1, x2) = e_in_gg(x1, x2) 13.58/4.27 13.58/4.27 a = a 13.58/4.27 13.58/4.27 b = b 13.58/4.27 13.58/4.27 e_out_gg(x1, x2) = e_out_gg 13.58/4.27 13.58/4.27 q_out_gg(x1, x2) = q_out_gg 13.58/4.27 13.58/4.27 f(x1) = f(x1) 13.58/4.27 13.58/4.27 U2_gg(x1, x2) = U2_gg(x1, x2) 13.58/4.27 13.58/4.27 p_in_gg(x1, x2) = p_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U5_gg(x1, x2, x3) = U5_gg(x3) 13.58/4.27 13.58/4.27 p_out_gg(x1, x2) = p_out_gg 13.58/4.27 13.58/4.27 U6_gg(x1, x2, x3) = U6_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 r_in_gg(x1, x2) = r_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U8_gg(x1, x2, x3) = U8_gg(x3) 13.58/4.27 13.58/4.27 r_out_gg(x1, x2) = r_out_gg 13.58/4.27 13.58/4.27 U9_gg(x1, x2, x3) = U9_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_gg(x1, x2, x3) = U4_gg(x3) 13.58/4.27 13.58/4.27 U10_gg(x1, x2, x3) = U10_gg(x3) 13.58/4.27 13.58/4.27 U11_gg(x1, x2) = U11_gg(x2) 13.58/4.27 13.58/4.27 t_in_gg(x1, x2) = t_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U12_gg(x1, x2, x3) = U12_gg(x3) 13.58/4.27 13.58/4.27 t_out_gg(x1, x2) = t_out_gg 13.58/4.27 13.58/4.27 U13_gg(x1, x2, x3) = U13_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_gg(x1, x2, x3) = U14_gg(x3) 13.58/4.27 13.58/4.27 U7_gg(x1, x2, x3) = U7_gg(x3) 13.58/4.27 13.58/4.27 U3_gg(x1, x2) = U3_gg(x2) 13.58/4.27 13.58/4.27 13.58/4.27 13.58/4.27 13.58/4.27 13.58/4.27 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 13.58/4.27 13.58/4.27 13.58/4.27 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (2) 13.58/4.27 Obligation: 13.58/4.27 Pi-finite rewrite system: 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg(a, b) 13.58/4.27 U1_gg(X, Y, e_out_gg(X, Y)) -> q_out_gg(X, Y) 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U5_gg(X, Y, e_out_gg(X, Y)) -> p_out_gg(X, Y) 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U8_gg(X, Y, e_out_gg(X, Y)) -> r_out_gg(X, Y) 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(X, Y, p_out_gg(X, f(Y))) -> q_out_gg(X, f(f(Y))) 13.58/4.27 U9_gg(X, Y, q_out_gg(X, Y)) -> U10_gg(X, Y, r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(X, t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U12_gg(X, Y, e_out_gg(X, Y)) -> t_out_gg(X, Y) 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg(f(X), f(Y))) -> U14_gg(X, Y, t_in_gg(X, Y)) 13.58/4.27 U14_gg(X, Y, t_out_gg(X, Y)) -> t_out_gg(f(X), f(Y)) 13.58/4.27 U11_gg(X, t_out_gg(f(X), f(X))) -> r_out_gg(f(X), f(X)) 13.58/4.27 U10_gg(X, Y, r_out_gg(X, Y)) -> r_out_gg(X, f(Y)) 13.58/4.27 U6_gg(X, Y, r_out_gg(X, f(Y))) -> U7_gg(X, Y, p_in_gg(X, Y)) 13.58/4.27 U7_gg(X, Y, p_out_gg(X, Y)) -> p_out_gg(X, f(Y)) 13.58/4.27 U2_gg(X, p_out_gg(X, f(f(X)))) -> U3_gg(X, q_in_gg(X, f(X))) 13.58/4.27 U3_gg(X, q_out_gg(X, f(X))) -> q_out_gg(X, f(f(X))) 13.58/4.27 13.58/4.27 The argument filtering Pi contains the following mapping: 13.58/4.27 q_in_gg(x1, x2) = q_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U1_gg(x1, x2, x3) = U1_gg(x3) 13.58/4.27 13.58/4.27 e_in_gg(x1, x2) = e_in_gg(x1, x2) 13.58/4.27 13.58/4.27 a = a 13.58/4.27 13.58/4.27 b = b 13.58/4.27 13.58/4.27 e_out_gg(x1, x2) = e_out_gg 13.58/4.27 13.58/4.27 q_out_gg(x1, x2) = q_out_gg 13.58/4.27 13.58/4.27 f(x1) = f(x1) 13.58/4.27 13.58/4.27 U2_gg(x1, x2) = U2_gg(x1, x2) 13.58/4.27 13.58/4.27 p_in_gg(x1, x2) = p_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U5_gg(x1, x2, x3) = U5_gg(x3) 13.58/4.27 13.58/4.27 p_out_gg(x1, x2) = p_out_gg 13.58/4.27 13.58/4.27 U6_gg(x1, x2, x3) = U6_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 r_in_gg(x1, x2) = r_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U8_gg(x1, x2, x3) = U8_gg(x3) 13.58/4.27 13.58/4.27 r_out_gg(x1, x2) = r_out_gg 13.58/4.27 13.58/4.27 U9_gg(x1, x2, x3) = U9_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_gg(x1, x2, x3) = U4_gg(x3) 13.58/4.27 13.58/4.27 U10_gg(x1, x2, x3) = U10_gg(x3) 13.58/4.27 13.58/4.27 U11_gg(x1, x2) = U11_gg(x2) 13.58/4.27 13.58/4.27 t_in_gg(x1, x2) = t_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U12_gg(x1, x2, x3) = U12_gg(x3) 13.58/4.27 13.58/4.27 t_out_gg(x1, x2) = t_out_gg 13.58/4.27 13.58/4.27 U13_gg(x1, x2, x3) = U13_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_gg(x1, x2, x3) = U14_gg(x3) 13.58/4.27 13.58/4.27 U7_gg(x1, x2, x3) = U7_gg(x3) 13.58/4.27 13.58/4.27 U3_gg(x1, x2) = U3_gg(x2) 13.58/4.27 13.58/4.27 13.58/4.27 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (3) DependencyPairsProof (EQUIVALENT) 13.58/4.27 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 13.58/4.27 Pi DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 Q_IN_GG(X, Y) -> U1_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 Q_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> U2_GG(X, p_in_gg(X, f(f(X)))) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 P_IN_GG(X, Y) -> U5_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 P_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 P_IN_GG(X, f(Y)) -> U6_GG(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(X, Y) -> U8_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 R_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 R_IN_GG(X, f(Y)) -> U9_GG(X, Y, q_in_gg(X, Y)) 13.58/4.27 R_IN_GG(X, f(Y)) -> Q_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> U4_GG(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> P_IN_GG(X, f(Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg(X, Y)) -> U10_GG(X, Y, r_in_gg(X, Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg(X, Y)) -> R_IN_GG(X, Y) 13.58/4.27 R_IN_GG(f(X), f(X)) -> U11_GG(X, t_in_gg(f(X), f(X))) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(X, Y) -> U12_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 T_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> U13_GG(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 U13_GG(X, Y, q_out_gg(f(X), f(Y))) -> U14_GG(X, Y, t_in_gg(X, Y)) 13.58/4.27 U13_GG(X, Y, q_out_gg(f(X), f(Y))) -> T_IN_GG(X, Y) 13.58/4.27 U6_GG(X, Y, r_out_gg(X, f(Y))) -> U7_GG(X, Y, p_in_gg(X, Y)) 13.58/4.27 U6_GG(X, Y, r_out_gg(X, f(Y))) -> P_IN_GG(X, Y) 13.58/4.27 U2_GG(X, p_out_gg(X, f(f(X)))) -> U3_GG(X, q_in_gg(X, f(X))) 13.58/4.27 U2_GG(X, p_out_gg(X, f(f(X)))) -> Q_IN_GG(X, f(X)) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg(a, b) 13.58/4.27 U1_gg(X, Y, e_out_gg(X, Y)) -> q_out_gg(X, Y) 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U5_gg(X, Y, e_out_gg(X, Y)) -> p_out_gg(X, Y) 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U8_gg(X, Y, e_out_gg(X, Y)) -> r_out_gg(X, Y) 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(X, Y, p_out_gg(X, f(Y))) -> q_out_gg(X, f(f(Y))) 13.58/4.27 U9_gg(X, Y, q_out_gg(X, Y)) -> U10_gg(X, Y, r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(X, t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U12_gg(X, Y, e_out_gg(X, Y)) -> t_out_gg(X, Y) 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg(f(X), f(Y))) -> U14_gg(X, Y, t_in_gg(X, Y)) 13.58/4.27 U14_gg(X, Y, t_out_gg(X, Y)) -> t_out_gg(f(X), f(Y)) 13.58/4.27 U11_gg(X, t_out_gg(f(X), f(X))) -> r_out_gg(f(X), f(X)) 13.58/4.27 U10_gg(X, Y, r_out_gg(X, Y)) -> r_out_gg(X, f(Y)) 13.58/4.27 U6_gg(X, Y, r_out_gg(X, f(Y))) -> U7_gg(X, Y, p_in_gg(X, Y)) 13.58/4.27 U7_gg(X, Y, p_out_gg(X, Y)) -> p_out_gg(X, f(Y)) 13.58/4.27 U2_gg(X, p_out_gg(X, f(f(X)))) -> U3_gg(X, q_in_gg(X, f(X))) 13.58/4.27 U3_gg(X, q_out_gg(X, f(X))) -> q_out_gg(X, f(f(X))) 13.58/4.27 13.58/4.27 The argument filtering Pi contains the following mapping: 13.58/4.27 q_in_gg(x1, x2) = q_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U1_gg(x1, x2, x3) = U1_gg(x3) 13.58/4.27 13.58/4.27 e_in_gg(x1, x2) = e_in_gg(x1, x2) 13.58/4.27 13.58/4.27 a = a 13.58/4.27 13.58/4.27 b = b 13.58/4.27 13.58/4.27 e_out_gg(x1, x2) = e_out_gg 13.58/4.27 13.58/4.27 q_out_gg(x1, x2) = q_out_gg 13.58/4.27 13.58/4.27 f(x1) = f(x1) 13.58/4.27 13.58/4.27 U2_gg(x1, x2) = U2_gg(x1, x2) 13.58/4.27 13.58/4.27 p_in_gg(x1, x2) = p_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U5_gg(x1, x2, x3) = U5_gg(x3) 13.58/4.27 13.58/4.27 p_out_gg(x1, x2) = p_out_gg 13.58/4.27 13.58/4.27 U6_gg(x1, x2, x3) = U6_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 r_in_gg(x1, x2) = r_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U8_gg(x1, x2, x3) = U8_gg(x3) 13.58/4.27 13.58/4.27 r_out_gg(x1, x2) = r_out_gg 13.58/4.27 13.58/4.27 U9_gg(x1, x2, x3) = U9_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_gg(x1, x2, x3) = U4_gg(x3) 13.58/4.27 13.58/4.27 U10_gg(x1, x2, x3) = U10_gg(x3) 13.58/4.27 13.58/4.27 U11_gg(x1, x2) = U11_gg(x2) 13.58/4.27 13.58/4.27 t_in_gg(x1, x2) = t_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U12_gg(x1, x2, x3) = U12_gg(x3) 13.58/4.27 13.58/4.27 t_out_gg(x1, x2) = t_out_gg 13.58/4.27 13.58/4.27 U13_gg(x1, x2, x3) = U13_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_gg(x1, x2, x3) = U14_gg(x3) 13.58/4.27 13.58/4.27 U7_gg(x1, x2, x3) = U7_gg(x3) 13.58/4.27 13.58/4.27 U3_gg(x1, x2) = U3_gg(x2) 13.58/4.27 13.58/4.27 Q_IN_GG(x1, x2) = Q_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U1_GG(x1, x2, x3) = U1_GG(x3) 13.58/4.27 13.58/4.27 E_IN_GG(x1, x2) = E_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U2_GG(x1, x2) = U2_GG(x1, x2) 13.58/4.27 13.58/4.27 P_IN_GG(x1, x2) = P_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U5_GG(x1, x2, x3) = U5_GG(x3) 13.58/4.27 13.58/4.27 U6_GG(x1, x2, x3) = U6_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 R_IN_GG(x1, x2) = R_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U8_GG(x1, x2, x3) = U8_GG(x3) 13.58/4.27 13.58/4.27 U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_GG(x1, x2, x3) = U4_GG(x3) 13.58/4.27 13.58/4.27 U10_GG(x1, x2, x3) = U10_GG(x3) 13.58/4.27 13.58/4.27 U11_GG(x1, x2) = U11_GG(x2) 13.58/4.27 13.58/4.27 T_IN_GG(x1, x2) = T_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U12_GG(x1, x2, x3) = U12_GG(x3) 13.58/4.27 13.58/4.27 U13_GG(x1, x2, x3) = U13_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_GG(x1, x2, x3) = U14_GG(x3) 13.58/4.27 13.58/4.27 U7_GG(x1, x2, x3) = U7_GG(x3) 13.58/4.27 13.58/4.27 U3_GG(x1, x2) = U3_GG(x2) 13.58/4.27 13.58/4.27 13.58/4.27 We have to consider all (P,R,Pi)-chains 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (4) 13.58/4.27 Obligation: 13.58/4.27 Pi DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 Q_IN_GG(X, Y) -> U1_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 Q_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> U2_GG(X, p_in_gg(X, f(f(X)))) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 P_IN_GG(X, Y) -> U5_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 P_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 P_IN_GG(X, f(Y)) -> U6_GG(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(X, Y) -> U8_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 R_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 R_IN_GG(X, f(Y)) -> U9_GG(X, Y, q_in_gg(X, Y)) 13.58/4.27 R_IN_GG(X, f(Y)) -> Q_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> U4_GG(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> P_IN_GG(X, f(Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg(X, Y)) -> U10_GG(X, Y, r_in_gg(X, Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg(X, Y)) -> R_IN_GG(X, Y) 13.58/4.27 R_IN_GG(f(X), f(X)) -> U11_GG(X, t_in_gg(f(X), f(X))) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(X, Y) -> U12_GG(X, Y, e_in_gg(X, Y)) 13.58/4.27 T_IN_GG(X, Y) -> E_IN_GG(X, Y) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> U13_GG(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 U13_GG(X, Y, q_out_gg(f(X), f(Y))) -> U14_GG(X, Y, t_in_gg(X, Y)) 13.58/4.27 U13_GG(X, Y, q_out_gg(f(X), f(Y))) -> T_IN_GG(X, Y) 13.58/4.27 U6_GG(X, Y, r_out_gg(X, f(Y))) -> U7_GG(X, Y, p_in_gg(X, Y)) 13.58/4.27 U6_GG(X, Y, r_out_gg(X, f(Y))) -> P_IN_GG(X, Y) 13.58/4.27 U2_GG(X, p_out_gg(X, f(f(X)))) -> U3_GG(X, q_in_gg(X, f(X))) 13.58/4.27 U2_GG(X, p_out_gg(X, f(f(X)))) -> Q_IN_GG(X, f(X)) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg(a, b) 13.58/4.27 U1_gg(X, Y, e_out_gg(X, Y)) -> q_out_gg(X, Y) 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U5_gg(X, Y, e_out_gg(X, Y)) -> p_out_gg(X, Y) 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U8_gg(X, Y, e_out_gg(X, Y)) -> r_out_gg(X, Y) 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(X, Y, p_out_gg(X, f(Y))) -> q_out_gg(X, f(f(Y))) 13.58/4.27 U9_gg(X, Y, q_out_gg(X, Y)) -> U10_gg(X, Y, r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(X, t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U12_gg(X, Y, e_out_gg(X, Y)) -> t_out_gg(X, Y) 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg(f(X), f(Y))) -> U14_gg(X, Y, t_in_gg(X, Y)) 13.58/4.27 U14_gg(X, Y, t_out_gg(X, Y)) -> t_out_gg(f(X), f(Y)) 13.58/4.27 U11_gg(X, t_out_gg(f(X), f(X))) -> r_out_gg(f(X), f(X)) 13.58/4.27 U10_gg(X, Y, r_out_gg(X, Y)) -> r_out_gg(X, f(Y)) 13.58/4.27 U6_gg(X, Y, r_out_gg(X, f(Y))) -> U7_gg(X, Y, p_in_gg(X, Y)) 13.58/4.27 U7_gg(X, Y, p_out_gg(X, Y)) -> p_out_gg(X, f(Y)) 13.58/4.27 U2_gg(X, p_out_gg(X, f(f(X)))) -> U3_gg(X, q_in_gg(X, f(X))) 13.58/4.27 U3_gg(X, q_out_gg(X, f(X))) -> q_out_gg(X, f(f(X))) 13.58/4.27 13.58/4.27 The argument filtering Pi contains the following mapping: 13.58/4.27 q_in_gg(x1, x2) = q_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U1_gg(x1, x2, x3) = U1_gg(x3) 13.58/4.27 13.58/4.27 e_in_gg(x1, x2) = e_in_gg(x1, x2) 13.58/4.27 13.58/4.27 a = a 13.58/4.27 13.58/4.27 b = b 13.58/4.27 13.58/4.27 e_out_gg(x1, x2) = e_out_gg 13.58/4.27 13.58/4.27 q_out_gg(x1, x2) = q_out_gg 13.58/4.27 13.58/4.27 f(x1) = f(x1) 13.58/4.27 13.58/4.27 U2_gg(x1, x2) = U2_gg(x1, x2) 13.58/4.27 13.58/4.27 p_in_gg(x1, x2) = p_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U5_gg(x1, x2, x3) = U5_gg(x3) 13.58/4.27 13.58/4.27 p_out_gg(x1, x2) = p_out_gg 13.58/4.27 13.58/4.27 U6_gg(x1, x2, x3) = U6_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 r_in_gg(x1, x2) = r_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U8_gg(x1, x2, x3) = U8_gg(x3) 13.58/4.27 13.58/4.27 r_out_gg(x1, x2) = r_out_gg 13.58/4.27 13.58/4.27 U9_gg(x1, x2, x3) = U9_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_gg(x1, x2, x3) = U4_gg(x3) 13.58/4.27 13.58/4.27 U10_gg(x1, x2, x3) = U10_gg(x3) 13.58/4.27 13.58/4.27 U11_gg(x1, x2) = U11_gg(x2) 13.58/4.27 13.58/4.27 t_in_gg(x1, x2) = t_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U12_gg(x1, x2, x3) = U12_gg(x3) 13.58/4.27 13.58/4.27 t_out_gg(x1, x2) = t_out_gg 13.58/4.27 13.58/4.27 U13_gg(x1, x2, x3) = U13_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_gg(x1, x2, x3) = U14_gg(x3) 13.58/4.27 13.58/4.27 U7_gg(x1, x2, x3) = U7_gg(x3) 13.58/4.27 13.58/4.27 U3_gg(x1, x2) = U3_gg(x2) 13.58/4.27 13.58/4.27 Q_IN_GG(x1, x2) = Q_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U1_GG(x1, x2, x3) = U1_GG(x3) 13.58/4.27 13.58/4.27 E_IN_GG(x1, x2) = E_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U2_GG(x1, x2) = U2_GG(x1, x2) 13.58/4.27 13.58/4.27 P_IN_GG(x1, x2) = P_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U5_GG(x1, x2, x3) = U5_GG(x3) 13.58/4.27 13.58/4.27 U6_GG(x1, x2, x3) = U6_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 R_IN_GG(x1, x2) = R_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U8_GG(x1, x2, x3) = U8_GG(x3) 13.58/4.27 13.58/4.27 U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_GG(x1, x2, x3) = U4_GG(x3) 13.58/4.27 13.58/4.27 U10_GG(x1, x2, x3) = U10_GG(x3) 13.58/4.27 13.58/4.27 U11_GG(x1, x2) = U11_GG(x2) 13.58/4.27 13.58/4.27 T_IN_GG(x1, x2) = T_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U12_GG(x1, x2, x3) = U12_GG(x3) 13.58/4.27 13.58/4.27 U13_GG(x1, x2, x3) = U13_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_GG(x1, x2, x3) = U14_GG(x3) 13.58/4.27 13.58/4.27 U7_GG(x1, x2, x3) = U7_GG(x3) 13.58/4.27 13.58/4.27 U3_GG(x1, x2) = U3_GG(x2) 13.58/4.27 13.58/4.27 13.58/4.27 We have to consider all (P,R,Pi)-chains 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (5) DependencyGraphProof (EQUIVALENT) 13.58/4.27 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 14 less nodes. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (6) 13.58/4.27 Obligation: 13.58/4.27 Pi DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 Q_IN_GG(X, f(f(X))) -> U2_GG(X, p_in_gg(X, f(f(X)))) 13.58/4.27 U2_GG(X, p_out_gg(X, f(f(X)))) -> Q_IN_GG(X, f(X)) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 P_IN_GG(X, f(Y)) -> U6_GG(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 U6_GG(X, Y, r_out_gg(X, f(Y))) -> P_IN_GG(X, Y) 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(X, f(Y)) -> U9_GG(X, Y, q_in_gg(X, Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg(X, Y)) -> R_IN_GG(X, Y) 13.58/4.27 R_IN_GG(X, f(Y)) -> Q_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> P_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> U13_GG(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_GG(X, Y, q_out_gg(f(X), f(Y))) -> T_IN_GG(X, Y) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg(a, b) 13.58/4.27 U1_gg(X, Y, e_out_gg(X, Y)) -> q_out_gg(X, Y) 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U5_gg(X, Y, e_out_gg(X, Y)) -> p_out_gg(X, Y) 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U8_gg(X, Y, e_out_gg(X, Y)) -> r_out_gg(X, Y) 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(X, Y, p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(X, Y, p_out_gg(X, f(Y))) -> q_out_gg(X, f(f(Y))) 13.58/4.27 U9_gg(X, Y, q_out_gg(X, Y)) -> U10_gg(X, Y, r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(X, t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(X, Y, e_in_gg(X, Y)) 13.58/4.27 U12_gg(X, Y, e_out_gg(X, Y)) -> t_out_gg(X, Y) 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg(f(X), f(Y))) -> U14_gg(X, Y, t_in_gg(X, Y)) 13.58/4.27 U14_gg(X, Y, t_out_gg(X, Y)) -> t_out_gg(f(X), f(Y)) 13.58/4.27 U11_gg(X, t_out_gg(f(X), f(X))) -> r_out_gg(f(X), f(X)) 13.58/4.27 U10_gg(X, Y, r_out_gg(X, Y)) -> r_out_gg(X, f(Y)) 13.58/4.27 U6_gg(X, Y, r_out_gg(X, f(Y))) -> U7_gg(X, Y, p_in_gg(X, Y)) 13.58/4.27 U7_gg(X, Y, p_out_gg(X, Y)) -> p_out_gg(X, f(Y)) 13.58/4.27 U2_gg(X, p_out_gg(X, f(f(X)))) -> U3_gg(X, q_in_gg(X, f(X))) 13.58/4.27 U3_gg(X, q_out_gg(X, f(X))) -> q_out_gg(X, f(f(X))) 13.58/4.27 13.58/4.27 The argument filtering Pi contains the following mapping: 13.58/4.27 q_in_gg(x1, x2) = q_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U1_gg(x1, x2, x3) = U1_gg(x3) 13.58/4.27 13.58/4.27 e_in_gg(x1, x2) = e_in_gg(x1, x2) 13.58/4.27 13.58/4.27 a = a 13.58/4.27 13.58/4.27 b = b 13.58/4.27 13.58/4.27 e_out_gg(x1, x2) = e_out_gg 13.58/4.27 13.58/4.27 q_out_gg(x1, x2) = q_out_gg 13.58/4.27 13.58/4.27 f(x1) = f(x1) 13.58/4.27 13.58/4.27 U2_gg(x1, x2) = U2_gg(x1, x2) 13.58/4.27 13.58/4.27 p_in_gg(x1, x2) = p_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U5_gg(x1, x2, x3) = U5_gg(x3) 13.58/4.27 13.58/4.27 p_out_gg(x1, x2) = p_out_gg 13.58/4.27 13.58/4.27 U6_gg(x1, x2, x3) = U6_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 r_in_gg(x1, x2) = r_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U8_gg(x1, x2, x3) = U8_gg(x3) 13.58/4.27 13.58/4.27 r_out_gg(x1, x2) = r_out_gg 13.58/4.27 13.58/4.27 U9_gg(x1, x2, x3) = U9_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U4_gg(x1, x2, x3) = U4_gg(x3) 13.58/4.27 13.58/4.27 U10_gg(x1, x2, x3) = U10_gg(x3) 13.58/4.27 13.58/4.27 U11_gg(x1, x2) = U11_gg(x2) 13.58/4.27 13.58/4.27 t_in_gg(x1, x2) = t_in_gg(x1, x2) 13.58/4.27 13.58/4.27 U12_gg(x1, x2, x3) = U12_gg(x3) 13.58/4.27 13.58/4.27 t_out_gg(x1, x2) = t_out_gg 13.58/4.27 13.58/4.27 U13_gg(x1, x2, x3) = U13_gg(x1, x2, x3) 13.58/4.27 13.58/4.27 U14_gg(x1, x2, x3) = U14_gg(x3) 13.58/4.27 13.58/4.27 U7_gg(x1, x2, x3) = U7_gg(x3) 13.58/4.27 13.58/4.27 U3_gg(x1, x2) = U3_gg(x2) 13.58/4.27 13.58/4.27 Q_IN_GG(x1, x2) = Q_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U2_GG(x1, x2) = U2_GG(x1, x2) 13.58/4.27 13.58/4.27 P_IN_GG(x1, x2) = P_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U6_GG(x1, x2, x3) = U6_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 R_IN_GG(x1, x2) = R_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 T_IN_GG(x1, x2) = T_IN_GG(x1, x2) 13.58/4.27 13.58/4.27 U13_GG(x1, x2, x3) = U13_GG(x1, x2, x3) 13.58/4.27 13.58/4.27 13.58/4.27 We have to consider all (P,R,Pi)-chains 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (7) PiDPToQDPProof (SOUND) 13.58/4.27 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (8) 13.58/4.27 Obligation: 13.58/4.27 Q DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 Q_IN_GG(X, f(f(X))) -> U2_GG(X, p_in_gg(X, f(f(X)))) 13.58/4.27 U2_GG(X, p_out_gg) -> Q_IN_GG(X, f(X)) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 P_IN_GG(X, f(Y)) -> U6_GG(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 U6_GG(X, Y, r_out_gg) -> P_IN_GG(X, Y) 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(X, f(Y)) -> U9_GG(X, Y, q_in_gg(X, Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg) -> R_IN_GG(X, Y) 13.58/4.27 R_IN_GG(X, f(Y)) -> Q_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> P_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> U13_GG(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_GG(X, Y, q_out_gg) -> T_IN_GG(X, Y) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg 13.58/4.27 U1_gg(e_out_gg) -> q_out_gg 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(e_in_gg(X, Y)) 13.58/4.27 U5_gg(e_out_gg) -> p_out_gg 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(e_in_gg(X, Y)) 13.58/4.27 U8_gg(e_out_gg) -> r_out_gg 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(p_out_gg) -> q_out_gg 13.58/4.27 U9_gg(X, Y, q_out_gg) -> U10_gg(r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(e_in_gg(X, Y)) 13.58/4.27 U12_gg(e_out_gg) -> t_out_gg 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg) -> U14_gg(t_in_gg(X, Y)) 13.58/4.27 U14_gg(t_out_gg) -> t_out_gg 13.58/4.27 U11_gg(t_out_gg) -> r_out_gg 13.58/4.27 U10_gg(r_out_gg) -> r_out_gg 13.58/4.27 U6_gg(X, Y, r_out_gg) -> U7_gg(p_in_gg(X, Y)) 13.58/4.27 U7_gg(p_out_gg) -> p_out_gg 13.58/4.27 U2_gg(X, p_out_gg) -> U3_gg(q_in_gg(X, f(X))) 13.58/4.27 U3_gg(q_out_gg) -> q_out_gg 13.58/4.27 13.58/4.27 The set Q consists of the following terms: 13.58/4.27 13.58/4.27 q_in_gg(x0, x1) 13.58/4.27 e_in_gg(x0, x1) 13.58/4.27 U1_gg(x0) 13.58/4.27 p_in_gg(x0, x1) 13.58/4.27 U5_gg(x0) 13.58/4.27 r_in_gg(x0, x1) 13.58/4.27 U8_gg(x0) 13.58/4.27 U4_gg(x0) 13.58/4.27 U9_gg(x0, x1, x2) 13.58/4.27 t_in_gg(x0, x1) 13.58/4.27 U12_gg(x0) 13.58/4.27 U13_gg(x0, x1, x2) 13.58/4.27 U14_gg(x0) 13.58/4.27 U11_gg(x0) 13.58/4.27 U10_gg(x0) 13.58/4.27 U6_gg(x0, x1, x2) 13.58/4.27 U7_gg(x0) 13.58/4.27 U2_gg(x0, x1) 13.58/4.27 U3_gg(x0) 13.58/4.27 13.58/4.27 We have to consider all (P,Q,R)-chains. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (9) QDPQMonotonicMRRProof (EQUIVALENT) 13.58/4.27 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 13.58/4.27 13.58/4.27 Strictly oriented dependency pairs: 13.58/4.27 13.58/4.27 Q_IN_GG(X, f(f(X))) -> U2_GG(X, p_in_gg(X, f(f(X)))) 13.58/4.27 P_IN_GG(X, f(Y)) -> U6_GG(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 U6_GG(X, Y, r_out_gg) -> P_IN_GG(X, Y) 13.58/4.27 R_IN_GG(X, f(Y)) -> U9_GG(X, Y, q_in_gg(X, Y)) 13.58/4.27 R_IN_GG(X, f(Y)) -> Q_IN_GG(X, Y) 13.58/4.27 Q_IN_GG(X, f(f(Y))) -> P_IN_GG(X, f(Y)) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> U13_GG(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 13.58/4.27 13.58/4.27 Used ordering: Polynomial interpretation [POLO]: 13.58/4.27 13.58/4.27 POL(P_IN_GG(x_1, x_2)) = x_2 13.58/4.27 POL(Q_IN_GG(x_1, x_2)) = x_2 13.58/4.27 POL(R_IN_GG(x_1, x_2)) = x_2 13.58/4.27 POL(T_IN_GG(x_1, x_2)) = x_2 13.58/4.27 POL(U10_gg(x_1)) = 0 13.58/4.27 POL(U11_gg(x_1)) = 0 13.58/4.27 POL(U12_gg(x_1)) = 0 13.58/4.27 POL(U13_GG(x_1, x_2, x_3)) = x_2 13.58/4.27 POL(U13_gg(x_1, x_2, x_3)) = 0 13.58/4.27 POL(U14_gg(x_1)) = 0 13.58/4.27 POL(U1_gg(x_1)) = 0 13.58/4.27 POL(U2_GG(x_1, x_2)) = 2 + 2*x_1 13.58/4.27 POL(U2_gg(x_1, x_2)) = 0 13.58/4.27 POL(U3_gg(x_1)) = 0 13.58/4.27 POL(U4_gg(x_1)) = 0 13.58/4.27 POL(U5_gg(x_1)) = 0 13.58/4.27 POL(U6_GG(x_1, x_2, x_3)) = 1 + x_2 13.58/4.27 POL(U6_gg(x_1, x_2, x_3)) = 0 13.58/4.27 POL(U7_gg(x_1)) = 0 13.58/4.27 POL(U8_gg(x_1)) = 0 13.58/4.27 POL(U9_GG(x_1, x_2, x_3)) = x_2 13.58/4.27 POL(U9_gg(x_1, x_2, x_3)) = 0 13.58/4.27 POL(a) = 2 13.58/4.27 POL(b) = 2 13.58/4.27 POL(e_in_gg(x_1, x_2)) = 0 13.58/4.27 POL(e_out_gg) = 0 13.58/4.27 POL(f(x_1)) = 2 + 2*x_1 13.58/4.27 POL(p_in_gg(x_1, x_2)) = 0 13.58/4.27 POL(p_out_gg) = 0 13.58/4.27 POL(q_in_gg(x_1, x_2)) = 0 13.58/4.27 POL(q_out_gg) = 0 13.58/4.27 POL(r_in_gg(x_1, x_2)) = 0 13.58/4.27 POL(r_out_gg) = 0 13.58/4.27 POL(t_in_gg(x_1, x_2)) = 0 13.58/4.27 POL(t_out_gg) = 0 13.58/4.27 13.58/4.27 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (10) 13.58/4.27 Obligation: 13.58/4.27 Q DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 U2_GG(X, p_out_gg) -> Q_IN_GG(X, f(X)) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 U9_GG(X, Y, q_out_gg) -> R_IN_GG(X, Y) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 U13_GG(X, Y, q_out_gg) -> T_IN_GG(X, Y) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg 13.58/4.27 U1_gg(e_out_gg) -> q_out_gg 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(e_in_gg(X, Y)) 13.58/4.27 U5_gg(e_out_gg) -> p_out_gg 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(e_in_gg(X, Y)) 13.58/4.27 U8_gg(e_out_gg) -> r_out_gg 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(p_out_gg) -> q_out_gg 13.58/4.27 U9_gg(X, Y, q_out_gg) -> U10_gg(r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(e_in_gg(X, Y)) 13.58/4.27 U12_gg(e_out_gg) -> t_out_gg 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg) -> U14_gg(t_in_gg(X, Y)) 13.58/4.27 U14_gg(t_out_gg) -> t_out_gg 13.58/4.27 U11_gg(t_out_gg) -> r_out_gg 13.58/4.27 U10_gg(r_out_gg) -> r_out_gg 13.58/4.27 U6_gg(X, Y, r_out_gg) -> U7_gg(p_in_gg(X, Y)) 13.58/4.27 U7_gg(p_out_gg) -> p_out_gg 13.58/4.27 U2_gg(X, p_out_gg) -> U3_gg(q_in_gg(X, f(X))) 13.58/4.27 U3_gg(q_out_gg) -> q_out_gg 13.58/4.27 13.58/4.27 The set Q consists of the following terms: 13.58/4.27 13.58/4.27 q_in_gg(x0, x1) 13.58/4.27 e_in_gg(x0, x1) 13.58/4.27 U1_gg(x0) 13.58/4.27 p_in_gg(x0, x1) 13.58/4.27 U5_gg(x0) 13.58/4.27 r_in_gg(x0, x1) 13.58/4.27 U8_gg(x0) 13.58/4.27 U4_gg(x0) 13.58/4.27 U9_gg(x0, x1, x2) 13.58/4.27 t_in_gg(x0, x1) 13.58/4.27 U12_gg(x0) 13.58/4.27 U13_gg(x0, x1, x2) 13.58/4.27 U14_gg(x0) 13.58/4.27 U11_gg(x0) 13.58/4.27 U10_gg(x0) 13.58/4.27 U6_gg(x0, x1, x2) 13.58/4.27 U7_gg(x0) 13.58/4.27 U2_gg(x0, x1) 13.58/4.27 U3_gg(x0) 13.58/4.27 13.58/4.27 We have to consider all (P,Q,R)-chains. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (11) DependencyGraphProof (EQUIVALENT) 13.58/4.27 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (12) 13.58/4.27 Obligation: 13.58/4.27 Q DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 13.58/4.27 The TRS R consists of the following rules: 13.58/4.27 13.58/4.27 q_in_gg(X, Y) -> U1_gg(e_in_gg(X, Y)) 13.58/4.27 e_in_gg(a, b) -> e_out_gg 13.58/4.27 U1_gg(e_out_gg) -> q_out_gg 13.58/4.27 q_in_gg(X, f(f(X))) -> U2_gg(X, p_in_gg(X, f(f(X)))) 13.58/4.27 p_in_gg(X, Y) -> U5_gg(e_in_gg(X, Y)) 13.58/4.27 U5_gg(e_out_gg) -> p_out_gg 13.58/4.27 p_in_gg(X, f(Y)) -> U6_gg(X, Y, r_in_gg(X, f(Y))) 13.58/4.27 r_in_gg(X, Y) -> U8_gg(e_in_gg(X, Y)) 13.58/4.27 U8_gg(e_out_gg) -> r_out_gg 13.58/4.27 r_in_gg(X, f(Y)) -> U9_gg(X, Y, q_in_gg(X, Y)) 13.58/4.27 q_in_gg(X, f(f(Y))) -> U4_gg(p_in_gg(X, f(Y))) 13.58/4.27 U4_gg(p_out_gg) -> q_out_gg 13.58/4.27 U9_gg(X, Y, q_out_gg) -> U10_gg(r_in_gg(X, Y)) 13.58/4.27 r_in_gg(f(X), f(X)) -> U11_gg(t_in_gg(f(X), f(X))) 13.58/4.27 t_in_gg(X, Y) -> U12_gg(e_in_gg(X, Y)) 13.58/4.27 U12_gg(e_out_gg) -> t_out_gg 13.58/4.27 t_in_gg(f(X), f(Y)) -> U13_gg(X, Y, q_in_gg(f(X), f(Y))) 13.58/4.27 U13_gg(X, Y, q_out_gg) -> U14_gg(t_in_gg(X, Y)) 13.58/4.27 U14_gg(t_out_gg) -> t_out_gg 13.58/4.27 U11_gg(t_out_gg) -> r_out_gg 13.58/4.27 U10_gg(r_out_gg) -> r_out_gg 13.58/4.27 U6_gg(X, Y, r_out_gg) -> U7_gg(p_in_gg(X, Y)) 13.58/4.27 U7_gg(p_out_gg) -> p_out_gg 13.58/4.27 U2_gg(X, p_out_gg) -> U3_gg(q_in_gg(X, f(X))) 13.58/4.27 U3_gg(q_out_gg) -> q_out_gg 13.58/4.27 13.58/4.27 The set Q consists of the following terms: 13.58/4.27 13.58/4.27 q_in_gg(x0, x1) 13.58/4.27 e_in_gg(x0, x1) 13.58/4.27 U1_gg(x0) 13.58/4.27 p_in_gg(x0, x1) 13.58/4.27 U5_gg(x0) 13.58/4.27 r_in_gg(x0, x1) 13.58/4.27 U8_gg(x0) 13.58/4.27 U4_gg(x0) 13.58/4.27 U9_gg(x0, x1, x2) 13.58/4.27 t_in_gg(x0, x1) 13.58/4.27 U12_gg(x0) 13.58/4.27 U13_gg(x0, x1, x2) 13.58/4.27 U14_gg(x0) 13.58/4.27 U11_gg(x0) 13.58/4.27 U10_gg(x0) 13.58/4.27 U6_gg(x0, x1, x2) 13.58/4.27 U7_gg(x0) 13.58/4.27 U2_gg(x0, x1) 13.58/4.27 U3_gg(x0) 13.58/4.27 13.58/4.27 We have to consider all (P,Q,R)-chains. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (13) UsableRulesProof (EQUIVALENT) 13.58/4.27 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (14) 13.58/4.27 Obligation: 13.58/4.27 Q DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.27 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.27 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.27 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.27 13.58/4.27 R is empty. 13.58/4.27 The set Q consists of the following terms: 13.58/4.27 13.58/4.27 q_in_gg(x0, x1) 13.58/4.27 e_in_gg(x0, x1) 13.58/4.27 U1_gg(x0) 13.58/4.27 p_in_gg(x0, x1) 13.58/4.27 U5_gg(x0) 13.58/4.27 r_in_gg(x0, x1) 13.58/4.27 U8_gg(x0) 13.58/4.27 U4_gg(x0) 13.58/4.27 U9_gg(x0, x1, x2) 13.58/4.27 t_in_gg(x0, x1) 13.58/4.27 U12_gg(x0) 13.58/4.27 U13_gg(x0, x1, x2) 13.58/4.27 U14_gg(x0) 13.58/4.27 U11_gg(x0) 13.58/4.27 U10_gg(x0) 13.58/4.27 U6_gg(x0, x1, x2) 13.58/4.27 U7_gg(x0) 13.58/4.27 U2_gg(x0, x1) 13.58/4.27 U3_gg(x0) 13.58/4.27 13.58/4.27 We have to consider all (P,Q,R)-chains. 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (15) QReductionProof (EQUIVALENT) 13.58/4.27 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.58/4.27 13.58/4.27 q_in_gg(x0, x1) 13.58/4.27 e_in_gg(x0, x1) 13.58/4.27 U1_gg(x0) 13.58/4.27 p_in_gg(x0, x1) 13.58/4.27 U5_gg(x0) 13.58/4.27 r_in_gg(x0, x1) 13.58/4.27 U8_gg(x0) 13.58/4.27 U4_gg(x0) 13.58/4.27 U9_gg(x0, x1, x2) 13.58/4.27 t_in_gg(x0, x1) 13.58/4.27 U12_gg(x0) 13.58/4.27 U13_gg(x0, x1, x2) 13.58/4.27 U14_gg(x0) 13.58/4.27 U11_gg(x0) 13.58/4.27 U10_gg(x0) 13.58/4.27 U6_gg(x0, x1, x2) 13.58/4.27 U7_gg(x0) 13.58/4.27 U2_gg(x0, x1) 13.58/4.27 U3_gg(x0) 13.58/4.27 13.58/4.27 13.58/4.27 ---------------------------------------- 13.58/4.27 13.58/4.27 (16) 13.58/4.27 Obligation: 13.58/4.27 Q DP problem: 13.58/4.27 The TRS P consists of the following rules: 13.58/4.27 13.58/4.27 P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.28 R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.28 T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.28 Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.28 13.58/4.28 R is empty. 13.58/4.28 Q is empty. 13.58/4.28 We have to consider all (P,Q,R)-chains. 13.58/4.28 ---------------------------------------- 13.58/4.28 13.58/4.28 (17) QDPSizeChangeProof (EQUIVALENT) 13.58/4.28 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. 13.58/4.28 13.58/4.28 From the DPs we obtained the following set of size-change graphs: 13.58/4.28 *R_IN_GG(f(X), f(X)) -> T_IN_GG(f(X), f(X)) 13.58/4.28 The graph contains the following edges 1 >= 1, 2 >= 1, 1 >= 2, 2 >= 2 13.58/4.28 13.58/4.28 13.58/4.28 *Q_IN_GG(X, f(f(X))) -> P_IN_GG(X, f(f(X))) 13.58/4.28 The graph contains the following edges 1 >= 1, 2 > 1, 2 >= 2 13.58/4.28 13.58/4.28 13.58/4.28 *T_IN_GG(f(X), f(Y)) -> Q_IN_GG(f(X), f(Y)) 13.58/4.28 The graph contains the following edges 1 >= 1, 2 >= 2 13.58/4.28 13.58/4.28 13.58/4.28 *P_IN_GG(X, f(Y)) -> R_IN_GG(X, f(Y)) 13.58/4.28 The graph contains the following edges 1 >= 1, 2 >= 2 13.58/4.28 13.58/4.28 13.58/4.28 ---------------------------------------- 13.58/4.28 13.58/4.28 (18) 13.58/4.28 YES 13.58/4.33 EOF