4.77/1.99 YES 4.77/2.01 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.77/2.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.77/2.01 4.77/2.01 4.77/2.01 Left Termination of the query pattern 4.77/2.01 4.77/2.01 perm(g,a) 4.77/2.01 4.77/2.01 w.r.t. the given Prolog program could successfully be proven: 4.77/2.01 4.77/2.01 (0) Prolog 4.77/2.01 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.77/2.01 (2) PiTRS 4.77/2.01 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.77/2.01 (4) PiDP 4.77/2.01 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.77/2.01 (6) AND 4.77/2.01 (7) PiDP 4.77/2.01 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.77/2.01 (9) PiDP 4.77/2.01 (10) PiDPToQDPProof [SOUND, 0 ms] 4.77/2.01 (11) QDP 4.77/2.01 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.77/2.01 (13) YES 4.77/2.01 (14) PiDP 4.77/2.01 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.77/2.01 (16) PiDP 4.77/2.01 (17) PiDPToQDPProof [SOUND, 0 ms] 4.77/2.01 (18) QDP 4.77/2.01 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.77/2.01 (20) YES 4.77/2.01 (21) PiDP 4.77/2.01 (22) UsableRulesProof [EQUIVALENT, 0 ms] 4.77/2.01 (23) PiDP 4.77/2.01 (24) PiDPToQDPProof [SOUND, 0 ms] 4.77/2.01 (25) QDP 4.77/2.01 (26) MRRProof [EQUIVALENT, 0 ms] 4.77/2.01 (27) QDP 4.77/2.01 (28) PisEmptyProof [EQUIVALENT, 0 ms] 4.77/2.01 (29) YES 4.77/2.01 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (0) 4.77/2.01 Obligation: 4.77/2.01 Clauses: 4.77/2.01 4.77/2.01 app1(.(X0, X), Y, .(X0, Z)) :- app1(X, Y, Z). 4.77/2.01 app1([], Y, Y). 4.77/2.01 app2(.(X0, X), Y, .(X0, Z)) :- app2(X, Y, Z). 4.77/2.01 app2([], Y, Y). 4.77/2.01 perm(X, .(X0, Y)) :- ','(app1(X1, .(X0, X2), X), ','(app2(X1, X2, Z), perm(Z, Y))). 4.77/2.01 perm([], []). 4.77/2.01 4.77/2.01 4.77/2.01 Query: perm(g,a) 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (1) PrologToPiTRSProof (SOUND) 4.77/2.01 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.77/2.01 4.77/2.01 perm_in_2: (b,f) 4.77/2.01 4.77/2.01 app1_in_3: (f,f,b) 4.77/2.01 4.77/2.01 app2_in_3: (b,b,f) 4.77/2.01 4.77/2.01 Transforming Prolog into the following Term Rewriting System: 4.77/2.01 4.77/2.01 Pi-finite rewrite system: 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 4.77/2.01 4.77/2.01 4.77/2.01 4.77/2.01 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.77/2.01 4.77/2.01 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (2) 4.77/2.01 Obligation: 4.77/2.01 Pi-finite rewrite system: 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (3) DependencyPairsProof (EQUIVALENT) 4.77/2.01 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> U3_GA(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> APP1_IN_AAG(X1, .(X0, X2), X) 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> U1_AAG(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> APP1_IN_AAG(X, Y, Z) 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_GA(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> APP2_IN_GGA(X1, X2, Z) 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> U2_GGA(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> APP2_IN_GGA(X, Y, Z) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_GA(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> PERM_IN_GA(Z, Y) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.77/2.01 4.77/2.01 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.77/2.01 4.77/2.01 APP1_IN_AAG(x1, x2, x3) = APP1_IN_AAG(x3) 4.77/2.01 4.77/2.01 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x5) 4.77/2.01 4.77/2.01 U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x6) 4.77/2.01 4.77/2.01 APP2_IN_GGA(x1, x2, x3) = APP2_IN_GGA(x1, x2) 4.77/2.01 4.77/2.01 U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x5) 4.77/2.01 4.77/2.01 U5_GA(x1, x2, x3, x4) = U5_GA(x4) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (4) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> U3_GA(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> APP1_IN_AAG(X1, .(X0, X2), X) 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> U1_AAG(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> APP1_IN_AAG(X, Y, Z) 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_GA(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> APP2_IN_GGA(X1, X2, Z) 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> U2_GGA(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> APP2_IN_GGA(X, Y, Z) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_GA(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> PERM_IN_GA(Z, Y) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.77/2.01 4.77/2.01 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.77/2.01 4.77/2.01 APP1_IN_AAG(x1, x2, x3) = APP1_IN_AAG(x3) 4.77/2.01 4.77/2.01 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x5) 4.77/2.01 4.77/2.01 U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x6) 4.77/2.01 4.77/2.01 APP2_IN_GGA(x1, x2, x3) = APP2_IN_GGA(x1, x2) 4.77/2.01 4.77/2.01 U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x5) 4.77/2.01 4.77/2.01 U5_GA(x1, x2, x3, x4) = U5_GA(x4) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (5) DependencyGraphProof (EQUIVALENT) 4.77/2.01 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 5 less nodes. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (6) 4.77/2.01 Complex Obligation (AND) 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (7) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> APP2_IN_GGA(X, Y, Z) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 APP2_IN_GGA(x1, x2, x3) = APP2_IN_GGA(x1, x2) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (8) UsableRulesProof (EQUIVALENT) 4.77/2.01 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (9) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP2_IN_GGA(.(X0, X), Y, .(X0, Z)) -> APP2_IN_GGA(X, Y, Z) 4.77/2.01 4.77/2.01 R is empty. 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 APP2_IN_GGA(x1, x2, x3) = APP2_IN_GGA(x1, x2) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (10) PiDPToQDPProof (SOUND) 4.77/2.01 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (11) 4.77/2.01 Obligation: 4.77/2.01 Q DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP2_IN_GGA(.(X), Y) -> APP2_IN_GGA(X, Y) 4.77/2.01 4.77/2.01 R is empty. 4.77/2.01 Q is empty. 4.77/2.01 We have to consider all (P,Q,R)-chains. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (12) QDPSizeChangeProof (EQUIVALENT) 4.77/2.01 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.77/2.01 4.77/2.01 From the DPs we obtained the following set of size-change graphs: 4.77/2.01 *APP2_IN_GGA(.(X), Y) -> APP2_IN_GGA(X, Y) 4.77/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.77/2.01 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (13) 4.77/2.01 YES 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (14) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> APP1_IN_AAG(X, Y, Z) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 APP1_IN_AAG(x1, x2, x3) = APP1_IN_AAG(x3) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (15) UsableRulesProof (EQUIVALENT) 4.77/2.01 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (16) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP1_IN_AAG(.(X0, X), Y, .(X0, Z)) -> APP1_IN_AAG(X, Y, Z) 4.77/2.01 4.77/2.01 R is empty. 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 APP1_IN_AAG(x1, x2, x3) = APP1_IN_AAG(x3) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (17) PiDPToQDPProof (SOUND) 4.77/2.01 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (18) 4.77/2.01 Obligation: 4.77/2.01 Q DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 APP1_IN_AAG(.(Z)) -> APP1_IN_AAG(Z) 4.77/2.01 4.77/2.01 R is empty. 4.77/2.01 Q is empty. 4.77/2.01 We have to consider all (P,Q,R)-chains. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (19) QDPSizeChangeProof (EQUIVALENT) 4.77/2.01 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.77/2.01 4.77/2.01 From the DPs we obtained the following set of size-change graphs: 4.77/2.01 *APP1_IN_AAG(.(Z)) -> APP1_IN_AAG(Z) 4.77/2.01 The graph contains the following edges 1 > 1 4.77/2.01 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (20) 4.77/2.01 YES 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (21) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_GA(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> PERM_IN_GA(Z, Y) 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> U3_GA(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 perm_in_ga(X, .(X0, Y)) -> U3_ga(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U3_ga(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_ga(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U4_ga(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> U5_ga(X, X0, Y, perm_in_ga(Z, Y)) 4.77/2.01 perm_in_ga([], []) -> perm_out_ga([], []) 4.77/2.01 U5_ga(X, X0, Y, perm_out_ga(Z, Y)) -> perm_out_ga(X, .(X0, Y)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 perm_in_ga(x1, x2) = perm_in_ga(x1) 4.77/2.01 4.77/2.01 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 4.77/2.01 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 U4_ga(x1, x2, x3, x4, x5, x6) = U4_ga(x6) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 U5_ga(x1, x2, x3, x4) = U5_ga(x4) 4.77/2.01 4.77/2.01 perm_out_ga(x1, x2) = perm_out_ga(x2) 4.77/2.01 4.77/2.01 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.77/2.01 4.77/2.01 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.77/2.01 4.77/2.01 U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x6) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (22) UsableRulesProof (EQUIVALENT) 4.77/2.01 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (23) 4.77/2.01 Obligation: 4.77/2.01 Pi DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 U3_GA(X, X0, Y, app1_out_aag(X1, .(X0, X2), X)) -> U4_GA(X, X0, Y, X1, X2, app2_in_gga(X1, X2, Z)) 4.77/2.01 U4_GA(X, X0, Y, X1, X2, app2_out_gga(X1, X2, Z)) -> PERM_IN_GA(Z, Y) 4.77/2.01 PERM_IN_GA(X, .(X0, Y)) -> U3_GA(X, X0, Y, app1_in_aag(X1, .(X0, X2), X)) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 app2_in_gga(.(X0, X), Y, .(X0, Z)) -> U2_gga(X0, X, Y, Z, app2_in_gga(X, Y, Z)) 4.77/2.01 app2_in_gga([], Y, Y) -> app2_out_gga([], Y, Y) 4.77/2.01 app1_in_aag(.(X0, X), Y, .(X0, Z)) -> U1_aag(X0, X, Y, Z, app1_in_aag(X, Y, Z)) 4.77/2.01 app1_in_aag([], Y, Y) -> app1_out_aag([], Y, Y) 4.77/2.01 U2_gga(X0, X, Y, Z, app2_out_gga(X, Y, Z)) -> app2_out_gga(.(X0, X), Y, .(X0, Z)) 4.77/2.01 U1_aag(X0, X, Y, Z, app1_out_aag(X, Y, Z)) -> app1_out_aag(.(X0, X), Y, .(X0, Z)) 4.77/2.01 4.77/2.01 The argument filtering Pi contains the following mapping: 4.77/2.01 app1_in_aag(x1, x2, x3) = app1_in_aag(x3) 4.77/2.01 4.77/2.01 .(x1, x2) = .(x2) 4.77/2.01 4.77/2.01 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x5) 4.77/2.01 4.77/2.01 app1_out_aag(x1, x2, x3) = app1_out_aag(x1, x2) 4.77/2.01 4.77/2.01 app2_in_gga(x1, x2, x3) = app2_in_gga(x1, x2) 4.77/2.01 4.77/2.01 U2_gga(x1, x2, x3, x4, x5) = U2_gga(x5) 4.77/2.01 4.77/2.01 [] = [] 4.77/2.01 4.77/2.01 app2_out_gga(x1, x2, x3) = app2_out_gga(x3) 4.77/2.01 4.77/2.01 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 4.77/2.01 4.77/2.01 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 4.77/2.01 4.77/2.01 U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x6) 4.77/2.01 4.77/2.01 4.77/2.01 We have to consider all (P,R,Pi)-chains 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (24) PiDPToQDPProof (SOUND) 4.77/2.01 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (25) 4.77/2.01 Obligation: 4.77/2.01 Q DP problem: 4.77/2.01 The TRS P consists of the following rules: 4.77/2.01 4.77/2.01 U3_GA(app1_out_aag(X1, .(X2))) -> U4_GA(app2_in_gga(X1, X2)) 4.77/2.01 U4_GA(app2_out_gga(Z)) -> PERM_IN_GA(Z) 4.77/2.01 PERM_IN_GA(X) -> U3_GA(app1_in_aag(X)) 4.77/2.01 4.77/2.01 The TRS R consists of the following rules: 4.77/2.01 4.77/2.01 app2_in_gga(.(X), Y) -> U2_gga(app2_in_gga(X, Y)) 4.77/2.01 app2_in_gga([], Y) -> app2_out_gga(Y) 4.77/2.01 app1_in_aag(.(Z)) -> U1_aag(app1_in_aag(Z)) 4.77/2.01 app1_in_aag(Y) -> app1_out_aag([], Y) 4.77/2.01 U2_gga(app2_out_gga(Z)) -> app2_out_gga(.(Z)) 4.77/2.01 U1_aag(app1_out_aag(X, Y)) -> app1_out_aag(.(X), Y) 4.77/2.01 4.77/2.01 The set Q consists of the following terms: 4.77/2.01 4.77/2.01 app2_in_gga(x0, x1) 4.77/2.01 app1_in_aag(x0) 4.77/2.01 U2_gga(x0) 4.77/2.01 U1_aag(x0) 4.77/2.01 4.77/2.01 We have to consider all (P,Q,R)-chains. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (26) MRRProof (EQUIVALENT) 4.77/2.01 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. 4.77/2.01 4.77/2.01 Strictly oriented dependency pairs: 4.77/2.01 4.77/2.01 U3_GA(app1_out_aag(X1, .(X2))) -> U4_GA(app2_in_gga(X1, X2)) 4.77/2.01 U4_GA(app2_out_gga(Z)) -> PERM_IN_GA(Z) 4.77/2.01 PERM_IN_GA(X) -> U3_GA(app1_in_aag(X)) 4.77/2.01 4.77/2.01 Strictly oriented rules of the TRS R: 4.77/2.01 4.77/2.01 app2_in_gga(.(X), Y) -> U2_gga(app2_in_gga(X, Y)) 4.77/2.01 app2_in_gga([], Y) -> app2_out_gga(Y) 4.77/2.01 app1_in_aag(.(Z)) -> U1_aag(app1_in_aag(Z)) 4.77/2.01 app1_in_aag(Y) -> app1_out_aag([], Y) 4.77/2.01 U2_gga(app2_out_gga(Z)) -> app2_out_gga(.(Z)) 4.77/2.01 U1_aag(app1_out_aag(X, Y)) -> app1_out_aag(.(X), Y) 4.77/2.01 4.77/2.01 Used ordering: Knuth-Bendix order [KBO] with precedence:U3_GA_1 > app1_in_aag_1 > ._1 > app2_in_gga_2 > PERM_IN_GA_1 > U2_gga_1 > U1_aag_1 > U4_GA_1 > app1_out_aag_2 > app2_out_gga_1 > [] 4.77/2.01 4.77/2.01 and weight map: 4.77/2.01 4.77/2.01 []=2 4.77/2.01 ._1=3 4.77/2.01 U2_gga_1=3 4.77/2.01 app2_out_gga_1=7 4.77/2.01 app1_in_aag_1=4 4.77/2.01 U1_aag_1=3 4.77/2.01 U3_GA_1=2 4.77/2.01 U4_GA_1=1 4.77/2.01 PERM_IN_GA_1=7 4.77/2.01 app2_in_gga_2=5 4.77/2.01 app1_out_aag_2=1 4.77/2.01 4.77/2.01 The variable weight is 1 4.77/2.01 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (27) 4.77/2.01 Obligation: 4.77/2.01 Q DP problem: 4.77/2.01 P is empty. 4.77/2.01 R is empty. 4.77/2.01 The set Q consists of the following terms: 4.77/2.01 4.77/2.01 app2_in_gga(x0, x1) 4.77/2.01 app1_in_aag(x0) 4.77/2.01 U2_gga(x0) 4.77/2.01 U1_aag(x0) 4.77/2.01 4.77/2.01 We have to consider all (P,Q,R)-chains. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (28) PisEmptyProof (EQUIVALENT) 4.77/2.01 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.77/2.01 ---------------------------------------- 4.77/2.01 4.77/2.01 (29) 4.77/2.01 YES 4.77/2.06 EOF