/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern star(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 11 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: star(X1, []). star(.(X, U), .(X, W)) :- ','(app(U, V, W), star(.(X, U), W)). app([], L, L). app(.(X, L), M, .(X, N)) :- app(L, M, N). Query: star(g,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: star_in_2: (b,b) app_in_3: (b,f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, V, W)) STAR_IN_GG(.(X, U), .(X, W)) -> APP_IN_GAG(U, V, W) APP_IN_GAG(.(X, L), M, .(X, N)) -> U3_GAG(X, L, M, N, app_in_gag(L, M, N)) APP_IN_GAG(.(X, L), M, .(X, N)) -> APP_IN_GAG(L, M, N) U1_GG(X, U, W, app_out_gag(U, V, W)) -> U2_GG(X, U, W, star_in_gg(.(X, U), W)) U1_GG(X, U, W, app_out_gag(U, V, W)) -> STAR_IN_GG(.(X, U), W) The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) STAR_IN_GG(x1, x2) = STAR_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) APP_IN_GAG(x1, x2, x3) = APP_IN_GAG(x1, x3) U3_GAG(x1, x2, x3, x4, x5) = U3_GAG(x5) U2_GG(x1, x2, x3, x4) = U2_GG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, V, W)) STAR_IN_GG(.(X, U), .(X, W)) -> APP_IN_GAG(U, V, W) APP_IN_GAG(.(X, L), M, .(X, N)) -> U3_GAG(X, L, M, N, app_in_gag(L, M, N)) APP_IN_GAG(.(X, L), M, .(X, N)) -> APP_IN_GAG(L, M, N) U1_GG(X, U, W, app_out_gag(U, V, W)) -> U2_GG(X, U, W, star_in_gg(.(X, U), W)) U1_GG(X, U, W, app_out_gag(U, V, W)) -> STAR_IN_GG(.(X, U), W) The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) STAR_IN_GG(x1, x2) = STAR_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) APP_IN_GAG(x1, x2, x3) = APP_IN_GAG(x1, x3) U3_GAG(x1, x2, x3, x4, x5) = U3_GAG(x5) U2_GG(x1, x2, x3, x4) = U2_GG(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAG(.(X, L), M, .(X, N)) -> APP_IN_GAG(L, M, N) The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) APP_IN_GAG(x1, x2, x3) = APP_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAG(.(X, L), M, .(X, N)) -> APP_IN_GAG(L, M, N) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APP_IN_GAG(x1, x2, x3) = APP_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GAG(.(X, L), .(X, N)) -> APP_IN_GAG(L, N) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *APP_IN_GAG(.(X, L), .(X, N)) -> APP_IN_GAG(L, N) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GG(X, U, W, app_out_gag(U, V, W)) -> STAR_IN_GG(.(X, U), W) STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, V, W)) The TRS R consists of the following rules: star_in_gg(X1, []) -> star_out_gg(X1, []) star_in_gg(.(X, U), .(X, W)) -> U1_gg(X, U, W, app_in_gag(U, V, W)) app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) U1_gg(X, U, W, app_out_gag(U, V, W)) -> U2_gg(X, U, W, star_in_gg(.(X, U), W)) U2_gg(X, U, W, star_out_gg(.(X, U), W)) -> star_out_gg(.(X, U), .(X, W)) The argument filtering Pi contains the following mapping: star_in_gg(x1, x2) = star_in_gg(x1, x2) [] = [] star_out_gg(x1, x2) = star_out_gg .(x1, x2) = .(x1, x2) U1_gg(x1, x2, x3, x4) = U1_gg(x1, x2, x3, x4) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) U2_gg(x1, x2, x3, x4) = U2_gg(x4) STAR_IN_GG(x1, x2) = STAR_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GG(X, U, W, app_out_gag(U, V, W)) -> STAR_IN_GG(.(X, U), W) STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, V, W)) The TRS R consists of the following rules: app_in_gag([], L, L) -> app_out_gag([], L, L) app_in_gag(.(X, L), M, .(X, N)) -> U3_gag(X, L, M, N, app_in_gag(L, M, N)) U3_gag(X, L, M, N, app_out_gag(L, M, N)) -> app_out_gag(.(X, L), M, .(X, N)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) app_in_gag(x1, x2, x3) = app_in_gag(x1, x3) app_out_gag(x1, x2, x3) = app_out_gag(x2) U3_gag(x1, x2, x3, x4, x5) = U3_gag(x5) STAR_IN_GG(x1, x2) = STAR_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GG(X, U, W, app_out_gag(V)) -> STAR_IN_GG(.(X, U), W) STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, W)) The TRS R consists of the following rules: app_in_gag([], L) -> app_out_gag(L) app_in_gag(.(X, L), .(X, N)) -> U3_gag(app_in_gag(L, N)) U3_gag(app_out_gag(M)) -> app_out_gag(M) The set Q consists of the following terms: app_in_gag(x0, x1) U3_gag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *STAR_IN_GG(.(X, U), .(X, W)) -> U1_GG(X, U, W, app_in_gag(U, W)) The graph contains the following edges 1 > 1, 2 > 1, 1 > 2, 2 > 3 *U1_GG(X, U, W, app_out_gag(V)) -> STAR_IN_GG(.(X, U), W) The graph contains the following edges 3 >= 2 ---------------------------------------- (20) YES