5.49/2.27 YES 5.49/2.30 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.49/2.30 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.49/2.30 5.49/2.30 5.49/2.30 Left Termination of the query pattern 5.49/2.30 5.49/2.30 samefringe(g,g) 5.49/2.30 5.49/2.30 w.r.t. the given Prolog program could successfully be proven: 5.49/2.30 5.49/2.30 (0) Prolog 5.49/2.30 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.49/2.30 (2) PiTRS 5.49/2.30 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.49/2.30 (4) PiDP 5.49/2.30 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.49/2.30 (6) AND 5.49/2.30 (7) PiDP 5.49/2.30 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.49/2.30 (9) PiDP 5.49/2.30 (10) PiDPToQDPProof [SOUND, 0 ms] 5.49/2.30 (11) QDP 5.49/2.30 (12) MRRProof [EQUIVALENT, 3 ms] 5.49/2.30 (13) QDP 5.49/2.30 (14) PisEmptyProof [EQUIVALENT, 0 ms] 5.49/2.30 (15) YES 5.49/2.30 (16) PiDP 5.49/2.30 (17) UsableRulesProof [EQUIVALENT, 0 ms] 5.49/2.30 (18) PiDP 5.49/2.30 (19) PiDPToQDPProof [SOUND, 0 ms] 5.49/2.30 (20) QDP 5.49/2.30 (21) MRRProof [EQUIVALENT, 0 ms] 5.49/2.30 (22) QDP 5.49/2.30 (23) PisEmptyProof [EQUIVALENT, 0 ms] 5.49/2.30 (24) YES 5.49/2.30 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (0) 5.49/2.30 Obligation: 5.49/2.30 Clauses: 5.49/2.30 5.49/2.30 gopher(nil, nil). 5.49/2.30 gopher(cons(nil, Y), cons(nil, Y)). 5.49/2.30 gopher(cons(cons(U, V), W), X) :- gopher(cons(U, cons(V, W)), X). 5.49/2.30 samefringe(nil, nil). 5.49/2.30 samefringe(cons(U, V), cons(X, Y)) :- ','(gopher(cons(U, V), cons(U1, V1)), ','(gopher(cons(X, Y), cons(X1, Y1)), samefringe(V1, Y1))). 5.49/2.30 5.49/2.30 5.49/2.30 Query: samefringe(g,g) 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (1) PrologToPiTRSProof (SOUND) 5.49/2.30 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.49/2.30 5.49/2.30 samefringe_in_2: (b,b) 5.49/2.30 5.49/2.30 gopher_in_2: (b,f) 5.49/2.30 5.49/2.30 Transforming Prolog into the following Term Rewriting System: 5.49/2.30 5.49/2.30 Pi-finite rewrite system: 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 5.49/2.30 5.49/2.30 5.49/2.30 5.49/2.30 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.49/2.30 5.49/2.30 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (2) 5.49/2.30 Obligation: 5.49/2.30 Pi-finite rewrite system: 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (3) DependencyPairsProof (EQUIVALENT) 5.49/2.30 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> GOPHER_IN_GA(cons(U, V), cons(U1, V1)) 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> U1_GA(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> GOPHER_IN_GA(cons(U, cons(V, W)), X) 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_GG(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> GOPHER_IN_GA(cons(X, Y), cons(X1, Y1)) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_GG(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(x1, x2) = SAMEFRINGE_IN_GG(x1, x2) 5.49/2.30 5.49/2.30 U2_GG(x1, x2, x3, x4, x5) = U2_GG(x3, x4, x5) 5.49/2.30 5.49/2.30 GOPHER_IN_GA(x1, x2) = GOPHER_IN_GA(x1) 5.49/2.30 5.49/2.30 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x5) 5.49/2.30 5.49/2.30 U3_GG(x1, x2, x3, x4, x5, x6, x7) = U3_GG(x6, x7) 5.49/2.30 5.49/2.30 U4_GG(x1, x2, x3, x4, x5) = U4_GG(x5) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (4) 5.49/2.30 Obligation: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> GOPHER_IN_GA(cons(U, V), cons(U1, V1)) 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> U1_GA(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> GOPHER_IN_GA(cons(U, cons(V, W)), X) 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_GG(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> GOPHER_IN_GA(cons(X, Y), cons(X1, Y1)) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_GG(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(x1, x2) = SAMEFRINGE_IN_GG(x1, x2) 5.49/2.30 5.49/2.30 U2_GG(x1, x2, x3, x4, x5) = U2_GG(x3, x4, x5) 5.49/2.30 5.49/2.30 GOPHER_IN_GA(x1, x2) = GOPHER_IN_GA(x1) 5.49/2.30 5.49/2.30 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x5) 5.49/2.30 5.49/2.30 U3_GG(x1, x2, x3, x4, x5, x6, x7) = U3_GG(x6, x7) 5.49/2.30 5.49/2.30 U4_GG(x1, x2, x3, x4, x5) = U4_GG(x5) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (5) DependencyGraphProof (EQUIVALENT) 5.49/2.30 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (6) 5.49/2.30 Complex Obligation (AND) 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (7) 5.49/2.30 Obligation: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> GOPHER_IN_GA(cons(U, cons(V, W)), X) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 GOPHER_IN_GA(x1, x2) = GOPHER_IN_GA(x1) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (8) UsableRulesProof (EQUIVALENT) 5.49/2.30 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (9) 5.49/2.30 Obligation: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W), X) -> GOPHER_IN_GA(cons(U, cons(V, W)), X) 5.49/2.30 5.49/2.30 R is empty. 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 GOPHER_IN_GA(x1, x2) = GOPHER_IN_GA(x1) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (10) PiDPToQDPProof (SOUND) 5.49/2.30 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (11) 5.49/2.30 Obligation: 5.49/2.30 Q DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W)) -> GOPHER_IN_GA(cons(U, cons(V, W))) 5.49/2.30 5.49/2.30 R is empty. 5.49/2.30 Q is empty. 5.49/2.30 We have to consider all (P,Q,R)-chains. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (12) MRRProof (EQUIVALENT) 5.49/2.30 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.49/2.30 5.49/2.30 Strictly oriented dependency pairs: 5.49/2.30 5.49/2.30 GOPHER_IN_GA(cons(cons(U, V), W)) -> GOPHER_IN_GA(cons(U, cons(V, W))) 5.49/2.30 5.49/2.30 5.49/2.30 Used ordering: Knuth-Bendix order [KBO] with precedence:cons_2 > GOPHER_IN_GA_1 5.49/2.30 5.49/2.30 and weight map: 5.49/2.30 5.49/2.30 GOPHER_IN_GA_1=1 5.49/2.30 cons_2=0 5.49/2.30 5.49/2.30 The variable weight is 1 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (13) 5.49/2.30 Obligation: 5.49/2.30 Q DP problem: 5.49/2.30 P is empty. 5.49/2.30 R is empty. 5.49/2.30 Q is empty. 5.49/2.30 We have to consider all (P,Q,R)-chains. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (14) PisEmptyProof (EQUIVALENT) 5.49/2.30 The TRS P is empty. Hence, there is no (P,Q,R) chain. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (15) 5.49/2.30 YES 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (16) 5.49/2.30 Obligation: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_GG(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 samefringe_in_gg(nil, nil) -> samefringe_out_gg(nil, nil) 5.49/2.30 samefringe_in_gg(cons(U, V), cons(X, Y)) -> U2_gg(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 gopher_in_ga(nil, nil) -> gopher_out_ga(nil, nil) 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 U2_gg(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_gg(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_gg(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> U4_gg(U, V, X, Y, samefringe_in_gg(V1, Y1)) 5.49/2.30 U4_gg(U, V, X, Y, samefringe_out_gg(V1, Y1)) -> samefringe_out_gg(cons(U, V), cons(X, Y)) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 samefringe_in_gg(x1, x2) = samefringe_in_gg(x1, x2) 5.49/2.30 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 samefringe_out_gg(x1, x2) = samefringe_out_gg 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 U2_gg(x1, x2, x3, x4, x5) = U2_gg(x3, x4, x5) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 U3_gg(x1, x2, x3, x4, x5, x6, x7) = U3_gg(x6, x7) 5.49/2.30 5.49/2.30 U4_gg(x1, x2, x3, x4, x5) = U4_gg(x5) 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(x1, x2) = SAMEFRINGE_IN_GG(x1, x2) 5.49/2.30 5.49/2.30 U2_GG(x1, x2, x3, x4, x5) = U2_GG(x3, x4, x5) 5.49/2.30 5.49/2.30 U3_GG(x1, x2, x3, x4, x5, x6, x7) = U3_GG(x6, x7) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (17) UsableRulesProof (EQUIVALENT) 5.49/2.30 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (18) 5.49/2.30 Obligation: 5.49/2.30 Pi DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 U2_GG(U, V, X, Y, gopher_out_ga(cons(U, V), cons(U1, V1))) -> U3_GG(U, V, X, Y, U1, V1, gopher_in_ga(cons(X, Y), cons(X1, Y1))) 5.49/2.30 U3_GG(U, V, X, Y, U1, V1, gopher_out_ga(cons(X, Y), cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(U, V, X, Y, gopher_in_ga(cons(U, V), cons(U1, V1))) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 gopher_in_ga(cons(nil, Y), cons(nil, Y)) -> gopher_out_ga(cons(nil, Y), cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W), X) -> U1_ga(U, V, W, X, gopher_in_ga(cons(U, cons(V, W)), X)) 5.49/2.30 U1_ga(U, V, W, X, gopher_out_ga(cons(U, cons(V, W)), X)) -> gopher_out_ga(cons(cons(U, V), W), X) 5.49/2.30 5.49/2.30 The argument filtering Pi contains the following mapping: 5.49/2.30 nil = nil 5.49/2.30 5.49/2.30 cons(x1, x2) = cons(x1, x2) 5.49/2.30 5.49/2.30 gopher_in_ga(x1, x2) = gopher_in_ga(x1) 5.49/2.30 5.49/2.30 gopher_out_ga(x1, x2) = gopher_out_ga(x2) 5.49/2.30 5.49/2.30 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) 5.49/2.30 5.49/2.30 SAMEFRINGE_IN_GG(x1, x2) = SAMEFRINGE_IN_GG(x1, x2) 5.49/2.30 5.49/2.30 U2_GG(x1, x2, x3, x4, x5) = U2_GG(x3, x4, x5) 5.49/2.30 5.49/2.30 U3_GG(x1, x2, x3, x4, x5, x6, x7) = U3_GG(x6, x7) 5.49/2.30 5.49/2.30 5.49/2.30 We have to consider all (P,R,Pi)-chains 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (19) PiDPToQDPProof (SOUND) 5.49/2.30 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (20) 5.49/2.30 Obligation: 5.49/2.30 Q DP problem: 5.49/2.30 The TRS P consists of the following rules: 5.49/2.30 5.49/2.30 U2_GG(X, Y, gopher_out_ga(cons(U1, V1))) -> U3_GG(V1, gopher_in_ga(cons(X, Y))) 5.49/2.30 U3_GG(V1, gopher_out_ga(cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(X, Y, gopher_in_ga(cons(U, V))) 5.49/2.30 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 gopher_in_ga(cons(nil, Y)) -> gopher_out_ga(cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W)) -> U1_ga(gopher_in_ga(cons(U, cons(V, W)))) 5.49/2.30 U1_ga(gopher_out_ga(X)) -> gopher_out_ga(X) 5.49/2.30 5.49/2.30 The set Q consists of the following terms: 5.49/2.30 5.49/2.30 gopher_in_ga(x0) 5.49/2.30 U1_ga(x0) 5.49/2.30 5.49/2.30 We have to consider all (P,Q,R)-chains. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (21) MRRProof (EQUIVALENT) 5.49/2.30 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.49/2.30 5.49/2.30 Strictly oriented dependency pairs: 5.49/2.30 5.49/2.30 U2_GG(X, Y, gopher_out_ga(cons(U1, V1))) -> U3_GG(V1, gopher_in_ga(cons(X, Y))) 5.49/2.30 U3_GG(V1, gopher_out_ga(cons(X1, Y1))) -> SAMEFRINGE_IN_GG(V1, Y1) 5.49/2.30 SAMEFRINGE_IN_GG(cons(U, V), cons(X, Y)) -> U2_GG(X, Y, gopher_in_ga(cons(U, V))) 5.49/2.30 5.49/2.30 5.49/2.30 Used ordering: Polynomial interpretation [POLO]: 5.49/2.30 5.49/2.30 POL(SAMEFRINGE_IN_GG(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 5.49/2.30 POL(U1_ga(x_1)) = x_1 5.49/2.30 POL(U2_GG(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 5.49/2.30 POL(U3_GG(x_1, x_2)) = 2*x_1 + x_2 5.49/2.30 POL(cons(x_1, x_2)) = 2 + x_1 + x_2 5.49/2.30 POL(gopher_in_ga(x_1)) = 2*x_1 5.49/2.30 POL(gopher_out_ga(x_1)) = 2*x_1 5.49/2.30 POL(nil) = 0 5.49/2.30 5.49/2.30 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (22) 5.49/2.30 Obligation: 5.49/2.30 Q DP problem: 5.49/2.30 P is empty. 5.49/2.30 The TRS R consists of the following rules: 5.49/2.30 5.49/2.30 gopher_in_ga(cons(nil, Y)) -> gopher_out_ga(cons(nil, Y)) 5.49/2.30 gopher_in_ga(cons(cons(U, V), W)) -> U1_ga(gopher_in_ga(cons(U, cons(V, W)))) 5.49/2.30 U1_ga(gopher_out_ga(X)) -> gopher_out_ga(X) 5.49/2.30 5.49/2.30 The set Q consists of the following terms: 5.49/2.30 5.49/2.30 gopher_in_ga(x0) 5.49/2.30 U1_ga(x0) 5.49/2.30 5.49/2.30 We have to consider all (P,Q,R)-chains. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (23) PisEmptyProof (EQUIVALENT) 5.49/2.30 The TRS P is empty. Hence, there is no (P,Q,R) chain. 5.49/2.30 ---------------------------------------- 5.49/2.30 5.49/2.30 (24) 5.49/2.30 YES 5.86/2.35 EOF