/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern app(g,a,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) CutEliminatorProof [SOUND, 0 ms] (2) Prolog (3) PrologToPiTRSProof [SOUND, 0 ms] (4) PiTRS (5) DependencyPairsProof [EQUIVALENT, 9 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) PiDP (9) UsableRulesProof [EQUIVALENT, 0 ms] (10) PiDP (11) PiDPToQDPProof [SOUND, 0 ms] (12) QDP (13) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (14) QDP (15) PrologToPiTRSProof [SOUND, 0 ms] (16) PiTRS (17) DependencyPairsProof [EQUIVALENT, 2 ms] (18) PiDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) PiDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) PiDP (23) PiDPToQDPProof [SOUND, 0 ms] (24) QDP (25) TransformationProof [SOUND, 0 ms] (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QReductionProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [SOUND, 0 ms] (32) QDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) QDP (35) QReductionProof [EQUIVALENT, 0 ms] (36) QDP (37) QDPQMonotonicMRRProof [EQUIVALENT, 17 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) PrologToTRSTransformerProof [SOUND, 0 ms] (42) QTRS (43) QTRSRRRProof [EQUIVALENT, 60 ms] (44) QTRS (45) QTRSRRRProof [EQUIVALENT, 0 ms] (46) QTRS (47) QTRSRRRProof [EQUIVALENT, 5 ms] (48) QTRS (49) Overlay + Local Confluence [EQUIVALENT, 0 ms] (50) QTRS (51) DependencyPairsProof [EQUIVALENT, 0 ms] (52) QDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) QDP (55) QReductionProof [EQUIVALENT, 0 ms] (56) QDP (57) NonTerminationLoopProof [COMPLETE, 0 ms] (58) NO (59) PrologToDTProblemTransformerProof [SOUND, 0 ms] (60) TRIPLES (61) TriplesToPiDPProof [SOUND, 0 ms] (62) PiDP (63) DependencyGraphProof [EQUIVALENT, 0 ms] (64) AND (65) PiDP (66) PiDPToQDPProof [SOUND, 0 ms] (67) QDP (68) NonTerminationLoopProof [COMPLETE, 0 ms] (69) NO (70) PiDP (71) PiDPToQDPProof [SOUND, 0 ms] (72) QDP (73) QDPSizeChangeProof [EQUIVALENT, 0 ms] (74) YES (75) PrologToIRSwTTransformerProof [SOUND, 0 ms] (76) IRSwT (77) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (78) IRSwT (79) IntTRSCompressionProof [EQUIVALENT, 54 ms] (80) IRSwT (81) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (82) IRSwT (83) IRSwTTerminationDigraphProof [EQUIVALENT, 9 ms] (84) AND (85) IRSwT (86) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (87) IRSwT (88) TempFilterProof [SOUND, 3 ms] (89) IRSwT (90) IRSwTToQDPProof [SOUND, 0 ms] (91) QDP (92) QDPSizeChangeProof [EQUIVALENT, 0 ms] (93) YES (94) IRSwT ---------------------------------------- (0) Obligation: Clauses: app([], L, L) :- !. app(X, Y, .(H, Z)) :- ','(head(X, H), ','(tail(X, T), app(T, Y, Z))). head([], X1). head(.(X, X2), X). tail([], []). tail(.(X3, Xs), Xs). Query: app(g,a,a) ---------------------------------------- (1) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (2) Obligation: Clauses: app([], L, L). app(X, Y, .(H, Z)) :- ','(head(X, H), ','(tail(X, T), app(T, Y, Z))). head([], X1). head(.(X, X2), X). tail([], []). tail(.(X3, Xs), Xs). Query: app(g,a,a) ---------------------------------------- (3) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: app_in_3: (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (4) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x6) ---------------------------------------- (5) 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: APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) APP_IN_GAA(X, Y, .(H, Z)) -> HEAD_IN_GA(X, H) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> TAIL_IN_GA(X, T) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> U3_GAA(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) APP_IN_GAA(X, Y, .(H, Z)) -> HEAD_IN_GA(X, H) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> TAIL_IN_GA(X, T) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> U3_GAA(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (10) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) The TRS R consists of the following rules: tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) The argument filtering Pi contains the following mapping: [] = [] head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga .(x1, x2) = .(x1, x2) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (11) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, head_out_ga) -> U2_GAA(tail_in_ga(X)) U2_GAA(tail_out_ga(T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) The TRS R consists of the following rules: tail_in_ga([]) -> tail_out_ga([]) tail_in_ga(.(X3, Xs)) -> tail_out_ga(Xs) head_in_ga([]) -> head_out_ga head_in_ga(.(X, X2)) -> head_out_ga The set Q consists of the following terms: tail_in_ga(x0) head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: tail_in_ga(.(X3, Xs)) -> tail_out_ga(Xs) head_in_ga(.(X, X2)) -> head_out_ga Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + 2*x_2 POL(APP_IN_GAA(x_1)) = 2*x_1 POL(U1_GAA(x_1, x_2)) = x_1 + x_2 POL(U2_GAA(x_1)) = x_1 POL([]) = 0 POL(head_in_ga(x_1)) = x_1 POL(head_out_ga) = 0 POL(tail_in_ga(x_1)) = x_1 POL(tail_out_ga(x_1)) = 2*x_1 ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, head_out_ga) -> U2_GAA(tail_in_ga(X)) U2_GAA(tail_out_ga(T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) The TRS R consists of the following rules: head_in_ga([]) -> head_out_ga tail_in_ga([]) -> tail_out_ga([]) The set Q consists of the following terms: tail_in_ga(x0) head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: app_in_3: (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (16) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) ---------------------------------------- (17) 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: APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) APP_IN_GAA(X, Y, .(H, Z)) -> HEAD_IN_GA(X, H) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> TAIL_IN_GA(X, T) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> U3_GAA(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x1, x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) APP_IN_GAA(X, Y, .(H, Z)) -> HEAD_IN_GA(X, H) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> TAIL_IN_GA(X, T) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> U3_GAA(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x1, x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U3_GAA(x1, x2, x3, x4, x5, x6) = U3_GAA(x1, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) The TRS R consists of the following rules: app_in_gaa([], L, L) -> app_out_gaa([], L, L) app_in_gaa(X, Y, .(H, Z)) -> U1_gaa(X, Y, H, Z, head_in_ga(X, H)) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) U1_gaa(X, Y, H, Z, head_out_ga(X, H)) -> U2_gaa(X, Y, H, Z, tail_in_ga(X, T)) tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) U2_gaa(X, Y, H, Z, tail_out_ga(X, T)) -> U3_gaa(X, Y, H, Z, T, app_in_gaa(T, Y, Z)) U3_gaa(X, Y, H, Z, T, app_out_gaa(T, Y, Z)) -> app_out_gaa(X, Y, .(H, Z)) The argument filtering Pi contains the following mapping: app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U1_gaa(x1, x2, x3, x4, x5) = U1_gaa(x1, x5) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) U2_gaa(x1, x2, x3, x4, x5) = U2_gaa(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U3_gaa(x1, x2, x3, x4, x5, x6) = U3_gaa(x1, x6) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GAA(X, Y, H, Z, head_out_ga(X, H)) -> U2_GAA(X, Y, H, Z, tail_in_ga(X, T)) U2_GAA(X, Y, H, Z, tail_out_ga(X, T)) -> APP_IN_GAA(T, Y, Z) APP_IN_GAA(X, Y, .(H, Z)) -> U1_GAA(X, Y, H, Z, head_in_ga(X, H)) The TRS R consists of the following rules: tail_in_ga([], []) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs), Xs) -> tail_out_ga(.(X3, Xs), Xs) head_in_ga([], X1) -> head_out_ga([], X1) head_in_ga(.(X, X2), X) -> head_out_ga(.(X, X2), X) The argument filtering Pi contains the following mapping: [] = [] head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) .(x1, x2) = .(x1, x2) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x5) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA(X, head_out_ga(X)) -> U2_GAA(X, tail_in_ga(X)) U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) The TRS R consists of the following rules: tail_in_ga([]) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs)) -> tail_out_ga(.(X3, Xs), Xs) head_in_ga([]) -> head_out_ga([]) head_in_ga(.(X, X2)) -> head_out_ga(.(X, X2)) The set Q consists of the following terms: tail_in_ga(x0) head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (SOUND) By narrowing [LPAR04] the rule U1_GAA(X, head_out_ga(X)) -> U2_GAA(X, tail_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])),U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], []))) (U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)),U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) The TRS R consists of the following rules: tail_in_ga([]) -> tail_out_ga([], []) tail_in_ga(.(X3, Xs)) -> tail_out_ga(.(X3, Xs), Xs) head_in_ga([]) -> head_out_ga([]) head_in_ga(.(X, X2)) -> head_out_ga(.(X, X2)) The set Q consists of the following terms: tail_in_ga(x0) head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) The TRS R consists of the following rules: head_in_ga([]) -> head_out_ga([]) head_in_ga(.(X, X2)) -> head_out_ga(.(X, X2)) The set Q consists of the following terms: tail_in_ga(x0) head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (29) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. tail_in_ga(x0) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) The TRS R consists of the following rules: head_in_ga([]) -> head_out_ga([]) head_in_ga(.(X, X2)) -> head_out_ga(.(X, X2)) The set Q consists of the following terms: head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (31) TransformationProof (SOUND) By narrowing [LPAR04] the rule APP_IN_GAA(X) -> U1_GAA(X, head_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])),APP_IN_GAA([]) -> U1_GAA([], head_out_ga([]))) (APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))),APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1)))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])) APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) The TRS R consists of the following rules: head_in_ga([]) -> head_out_ga([]) head_in_ga(.(X, X2)) -> head_out_ga(.(X, X2)) The set Q consists of the following terms: head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])) APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) R is empty. The set Q consists of the following terms: head_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. head_in_ga(x0) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])) APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) QDPQMonotonicMRRProof (EQUIVALENT) 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. Strictly oriented dependency pairs: U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) -> U2_GAA(.(x0, x1), tail_out_ga(.(x0, x1), x1)) APP_IN_GAA(.(x0, x1)) -> U1_GAA(.(x0, x1), head_out_ga(.(x0, x1))) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2 + 2*x_2 POL(APP_IN_GAA(x_1)) = 2*x_1 POL(U1_GAA(x_1, x_2)) = x_1 POL(U2_GAA(x_1, x_2)) = x_2 POL([]) = 0 POL(head_out_ga(x_1)) = 2 POL(tail_out_ga(x_1, x_2)) = 2*x_2 ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U2_GAA(X, tail_out_ga(X, T)) -> APP_IN_GAA(T) we obtained the following new rules [LPAR04]: (U2_GAA([], tail_out_ga([], [])) -> APP_IN_GAA([]),U2_GAA([], tail_out_ga([], [])) -> APP_IN_GAA([])) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GAA([], head_out_ga([])) -> U2_GAA([], tail_out_ga([], [])) APP_IN_GAA([]) -> U1_GAA([], head_out_ga([])) U2_GAA([], tail_out_ga([], [])) -> APP_IN_GAA([]) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (41) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 5, "program": { "directives": [], "clauses": [ [ "(app ([]) L L)", "(!)" ], [ "(app X Y (. H Z))", "(',' (head X H) (',' (tail X T) (app T Y Z)))" ], [ "(head ([]) X1)", null ], [ "(head (. X X2) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X3 Xs) Xs)", null ] ] }, "graph": { "nodes": { "33": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "44": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }, { "clause": 5, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [{ "clause": 4, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "46": { "goal": [{ "clause": 5, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) T28 T29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }, { "clause": 3, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" } ], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "type": "Nodes", "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T49 T40 T41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T49"], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(app T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }, { "clause": 5, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "229": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "40": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "41": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "31": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(app ([]) T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "32": { "goal": [{ "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [[ "(app T1 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X6"], "exprvars": [] } }, "43": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 31, "label": "EVAL with clause\napp([], X6, X6) :- !_1.\nand substitutionT1 -> [],\nT2 -> T6,\nX6 -> T6,\nT3 -> T6" }, { "from": 6, "to": 32, "label": "EVAL-BACKTRACK" }, { "from": 31, "to": 33, "label": "CUT" }, { "from": 32, "to": 37, "label": "EVAL with clause\napp(X16, X17, .(X18, X19)) :- ','(head(X16, X18), ','(tail(X16, X20), app(X20, X17, X19))).\nand substitutionT1 -> T15,\nX16 -> T15,\nT2 -> T20,\nX17 -> T20,\nX18 -> T19,\nX19 -> T21,\nT3 -> .(T19, T21),\nT17 -> T19,\nT16 -> T20,\nT18 -> T21" }, { "from": 32, "to": 38, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 34, "label": "SUCCESS" }, { "from": 37, "to": 39, "label": "CASE" }, { "from": 39, "to": 40, "label": "PARALLEL" }, { "from": 39, "to": 41, "label": "PARALLEL" }, { "from": 40, "to": 42, "label": "EVAL with clause\nhead([], X26).\nand substitutionT15 -> [],\nT19 -> T27,\nX26 -> T27,\nT20 -> T28,\nT21 -> T29" }, { "from": 40, "to": 43, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 226, "label": "EVAL with clause\nhead(.(X37, X38), X37).\nand substitutionX37 -> T38,\nX38 -> T39,\nT15 -> .(T38, T39),\nT19 -> T38,\nT20 -> T40,\nT21 -> T41" }, { "from": 41, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 42, "to": 44, "label": "CASE" }, { "from": 44, "to": 45, "label": "PARALLEL" }, { "from": 44, "to": 46, "label": "PARALLEL" }, { "from": 45, "to": 47, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX20 -> []" }, { "from": 46, "to": 56, "label": "BACKTRACK\nfor clause: tail(.(X3, Xs), Xs)because of non-unification" }, { "from": 47, "to": 5, "label": "INSTANCE with matching:\nT1 -> []\nT2 -> T28\nT3 -> T29" }, { "from": 226, "to": 228, "label": "CASE" }, { "from": 228, "to": 229, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 229, "to": 230, "label": "ONLY EVAL with clause\ntail(.(X45, X46), X46).\nand substitutionT38 -> T48,\nX45 -> T48,\nT39 -> T49,\nX46 -> T49,\nX20 -> T49" }, { "from": 230, "to": 5, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T40\nT3 -> T41" } ], "type": "Graph" } } ---------------------------------------- (42) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in([]) -> f5_out1 f5_in([]) -> U1(f5_in([]), []) U1(f5_out1, []) -> f5_out1 f5_in(.(T48, T49)) -> U2(f5_in(T49), .(T48, T49)) U2(f5_out1, .(T48, T49)) -> f5_out1 Q is empty. ---------------------------------------- (43) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U1(x_1, x_2)) = x_1 + 2*x_2 POL(U2(x_1, x_2)) = x_1 + x_2 POL([]) = 0 POL(f5_in(x_1)) = 2 + 2*x_1 POL(f5_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f5_in([]) -> f5_out1 ---------------------------------------- (44) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in([]) -> U1(f5_in([]), []) U1(f5_out1, []) -> f5_out1 f5_in(.(T48, T49)) -> U2(f5_in(T49), .(T48, T49)) U2(f5_out1, .(T48, T49)) -> f5_out1 Q is empty. ---------------------------------------- (45) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U1(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U2(x_1, x_2)) = x_1 + x_2 POL([]) = 0 POL(f5_in(x_1)) = 2*x_1 POL(f5_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f5_in(.(T48, T49)) -> U2(f5_in(T49), .(T48, T49)) U2(f5_out1, .(T48, T49)) -> f5_out1 ---------------------------------------- (46) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in([]) -> U1(f5_in([]), []) U1(f5_out1, []) -> f5_out1 Q is empty. ---------------------------------------- (47) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U1(x_1, x_2)) = 2*x_1 + x_2 POL([]) = 0 POL(f5_in(x_1)) = 2*x_1 POL(f5_out1) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U1(f5_out1, []) -> f5_out1 ---------------------------------------- (48) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in([]) -> U1(f5_in([]), []) Q is empty. ---------------------------------------- (49) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (50) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in([]) -> U1(f5_in([]), []) The set Q consists of the following terms: f5_in([]) ---------------------------------------- (51) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN([]) -> F5_IN([]) The TRS R consists of the following rules: f5_in([]) -> U1(f5_in([]), []) The set Q consists of the following terms: f5_in([]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN([]) -> F5_IN([]) R is empty. The set Q consists of the following terms: f5_in([]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f5_in([]) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: F5_IN([]) -> F5_IN([]) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F5_IN([]) evaluates to t =F5_IN([]) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F5_IN([]) to F5_IN([]). ---------------------------------------- (58) NO ---------------------------------------- (59) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(app ([]) L L)", "(!)" ], [ "(app X Y (. H Z))", "(',' (head X H) (',' (tail X T) (app T Y Z)))" ], [ "(head ([]) X1)", null ], [ "(head (. X X2) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X3 Xs) Xs)", null ] ] }, "graph": { "nodes": { "66": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X14) (app X14 T22 T23))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X14"], "exprvars": [] } }, "67": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(app ([]) T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (tail ([]) X14) (app X14 T22 T23))" }, { "clause": 5, "scope": 3, "term": "(',' (tail ([]) X14) (app X14 T22 T23))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X14"], "exprvars": [] } }, "58": { "goal": [{ "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [[ "(app T1 T2 T3)", "(app ([]) X5 X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X5"], "exprvars": [] } }, "59": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "140": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (tail (. T32 T33) X14) (app X14 T34 T35))" }, { "clause": 5, "scope": 4, "term": "(',' (tail (. T32 T33) X14) (app X14 T34 T35))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": ["X14"], "exprvars": [] } }, "141": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (tail (. T32 T33) X14) (app X14 T34 T35))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": ["X14"], "exprvars": [] } }, "142": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T43 T34 T35)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": [], "exprvars": [] } }, "132": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "2": { "goal": [ { "clause": 0, "scope": 1, "term": "(app T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T32 T33) X14) (app X14 T34 T35))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": ["X14"], "exprvars": [] } }, "139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "71": { "goal": [{ "clause": 4, "scope": 3, "term": "(',' (tail ([]) X14) (app X14 T22 T23))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X14"], "exprvars": [] } }, "61": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T10 T14) (',' (tail T10 X14) (app X14 T15 T16)))" }], "kb": { "nonunifying": [[ "(app T10 T2 T3)", "(app ([]) X5 X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X5", "X14" ], "exprvars": [] } }, "72": { "goal": [{ "clause": 5, "scope": 3, "term": "(',' (tail ([]) X14) (app X14 T22 T23))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X14"], "exprvars": [] } }, "62": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "63": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (head T10 T14) (',' (tail T10 X14) (app X14 T15 T16)))" }, { "clause": 3, "scope": 2, "term": "(',' (head T10 T14) (',' (tail T10 X14) (app X14 T15 T16)))" } ], "kb": { "nonunifying": [[ "(app T10 T2 T3)", "(app ([]) X5 X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X5", "X14" ], "exprvars": [] } }, "96": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) T22 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (head T10 T14) (',' (tail T10 X14) (app X14 T15 T16)))" }], "kb": { "nonunifying": [[ "(app T10 T2 T3)", "(app ([]) X5 X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X5", "X14" ], "exprvars": [] } }, "65": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (head T10 T14) (',' (tail T10 X14) (app X14 T15 T16)))" }], "kb": { "nonunifying": [[ "(app T10 T2 T3)", "(app ([]) X5 X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [ "X5", "X14" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 57, "label": "EVAL with clause\napp([], X5, X5) :- !_1.\nand substitutionT1 -> [],\nT2 -> T5,\nX5 -> T5,\nT3 -> T5" }, { "from": 2, "to": 58, "label": "EVAL-BACKTRACK" }, { "from": 57, "to": 59, "label": "CUT" }, { "from": 58, "to": 61, "label": "EVAL with clause\napp(X10, X11, .(X12, X13)) :- ','(head(X10, X12), ','(tail(X10, X14), app(X14, X11, X13))).\nand substitutionT1 -> T10,\nX10 -> T10,\nT2 -> T15,\nX11 -> T15,\nX12 -> T14,\nX13 -> T16,\nT3 -> .(T14, T16),\nT12 -> T14,\nT11 -> T15,\nT13 -> T16" }, { "from": 58, "to": 62, "label": "EVAL-BACKTRACK" }, { "from": 59, "to": 60, "label": "SUCCESS" }, { "from": 61, "to": 63, "label": "CASE" }, { "from": 63, "to": 64, "label": "PARALLEL" }, { "from": 63, "to": 65, "label": "PARALLEL" }, { "from": 64, "to": 66, "label": "EVAL with clause\nhead([], X19).\nand substitutionT10 -> [],\nT14 -> T21,\nX19 -> T21,\nT15 -> T22,\nT16 -> T23" }, { "from": 64, "to": 67, "label": "EVAL-BACKTRACK" }, { "from": 65, "to": 138, "label": "EVAL with clause\nhead(.(X30, X31), X30).\nand substitutionX30 -> T32,\nX31 -> T33,\nT10 -> .(T32, T33),\nT14 -> T32,\nT15 -> T34,\nT16 -> T35" }, { "from": 65, "to": 139, "label": "EVAL-BACKTRACK" }, { "from": 66, "to": 68, "label": "CASE" }, { "from": 68, "to": 71, "label": "PARALLEL" }, { "from": 68, "to": 72, "label": "PARALLEL" }, { "from": 71, "to": 96, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX14 -> []" }, { "from": 72, "to": 132, "label": "BACKTRACK\nfor clause: tail(.(X3, Xs), Xs)because of non-unification" }, { "from": 96, "to": 1, "label": "INSTANCE with matching:\nT1 -> []\nT2 -> T22\nT3 -> T23" }, { "from": 138, "to": 140, "label": "CASE" }, { "from": 140, "to": 141, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 141, "to": 142, "label": "ONLY EVAL with clause\ntail(.(X38, X39), X39).\nand substitutionT32 -> T42,\nX38 -> T42,\nT33 -> T43,\nX39 -> T43,\nX14 -> T43" }, { "from": 142, "to": 1, "label": "INSTANCE with matching:\nT1 -> T43\nT2 -> T34\nT3 -> T35" } ], "type": "Graph" } } ---------------------------------------- (60) Obligation: Triples: appA([], X1, .(X2, X3)) :- appA([], X1, X3). appA(.(X1, X2), X3, .(X1, X4)) :- appA(X2, X3, X4). Clauses: appcA([], X1, X1). appcA([], X1, .(X2, X3)) :- appcA([], X1, X3). appcA(.(X1, X2), X3, .(X1, X4)) :- appcA(X2, X3, X4). Afs: appA(x1, x2, x3) = appA(x1) ---------------------------------------- (61) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: appA_in_3: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GAA([], X1, .(X2, X3)) -> U1_GAA(X1, X2, X3, appA_in_gaa([], X1, X3)) APPA_IN_GAA([], X1, .(X2, X3)) -> APPA_IN_GAA([], X1, X3) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) [] = [] .(x1, x2) = .(x2) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x4) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (62) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GAA([], X1, .(X2, X3)) -> U1_GAA(X1, X2, X3, appA_in_gaa([], X1, X3)) APPA_IN_GAA([], X1, .(X2, X3)) -> APPA_IN_GAA([], X1, X3) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) [] = [] .(x1, x2) = .(x2) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x4) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (63) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 2 less nodes. ---------------------------------------- (64) Complex Obligation (AND) ---------------------------------------- (65) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GAA([], X1, .(X2, X3)) -> APPA_IN_GAA([], X1, X3) R is empty. The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x2) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (66) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: APPA_IN_GAA([]) -> APPA_IN_GAA([]) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (68) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = APPA_IN_GAA([]) evaluates to t =APPA_IN_GAA([]) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from APPA_IN_GAA([]) to APPA_IN_GAA([]). ---------------------------------------- (69) NO ---------------------------------------- (70) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (71) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) 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: *APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (74) YES ---------------------------------------- (75) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(app ([]) L L)", "(!)" ], [ "(app X Y (. H Z))", "(',' (head X H) (',' (tail X T) (app T Y Z)))" ], [ "(head ([]) X1)", null ], [ "(head (. X X2) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X3 Xs) Xs)", null ] ] }, "graph": { "nodes": { "55": { "goal": [{ "clause": 5, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }, { "clause": 3, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" } ], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "27": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(app ([]) T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "28": { "goal": [{ "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [[ "(app T1 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X6"], "exprvars": [] } }, "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) T28 T29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "233": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(app T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "235": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }, { "clause": 5, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "236": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (tail (. T38 T39) X20) (app X20 T40 T41))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T39" ], "free": ["X20"], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T49 T40 T41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T49"], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (head T15 T19) (',' (tail T15 X20) (app X20 T20 T21)))" }], "kb": { "nonunifying": [[ "(app T15 T2 T3)", "(app ([]) X6 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X6", "X20" ], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }, { "clause": 5, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } }, "54": { "goal": [{ "clause": 4, "scope": 3, "term": "(',' (tail ([]) X20) (app X20 T28 T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X20"], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 27, "label": "EVAL with clause\napp([], X6, X6) :- !_1.\nand substitutionT1 -> [],\nT2 -> T6,\nX6 -> T6,\nT3 -> T6" }, { "from": 4, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 27, "to": 29, "label": "CUT" }, { "from": 28, "to": 35, "label": "EVAL with clause\napp(X16, X17, .(X18, X19)) :- ','(head(X16, X18), ','(tail(X16, X20), app(X20, X17, X19))).\nand substitutionT1 -> T15,\nX16 -> T15,\nT2 -> T20,\nX17 -> T20,\nX18 -> T19,\nX19 -> T21,\nT3 -> .(T19, T21),\nT17 -> T19,\nT16 -> T20,\nT18 -> T21" }, { "from": 28, "to": 36, "label": "EVAL-BACKTRACK" }, { "from": 29, "to": 30, "label": "SUCCESS" }, { "from": 35, "to": 48, "label": "CASE" }, { "from": 48, "to": 49, "label": "PARALLEL" }, { "from": 48, "to": 50, "label": "PARALLEL" }, { "from": 49, "to": 51, "label": "EVAL with clause\nhead([], X26).\nand substitutionT15 -> [],\nT19 -> T27,\nX26 -> T27,\nT20 -> T28,\nT21 -> T29" }, { "from": 49, "to": 52, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 233, "label": "EVAL with clause\nhead(.(X37, X38), X37).\nand substitutionX37 -> T38,\nX38 -> T39,\nT15 -> .(T38, T39),\nT19 -> T38,\nT20 -> T40,\nT21 -> T41" }, { "from": 50, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 51, "to": 53, "label": "CASE" }, { "from": 53, "to": 54, "label": "PARALLEL" }, { "from": 53, "to": 55, "label": "PARALLEL" }, { "from": 54, "to": 231, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX20 -> []" }, { "from": 55, "to": 232, "label": "BACKTRACK\nfor clause: tail(.(X3, Xs), Xs)because of non-unification" }, { "from": 231, "to": 3, "label": "INSTANCE with matching:\nT1 -> []\nT2 -> T28\nT3 -> T29" }, { "from": 233, "to": 235, "label": "CASE" }, { "from": 235, "to": 236, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 236, "to": 237, "label": "ONLY EVAL with clause\ntail(.(X45, X46), X46).\nand substitutionT38 -> T48,\nX45 -> T48,\nT39 -> T49,\nX46 -> T49,\nX20 -> T49" }, { "from": 237, "to": 3, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T40\nT3 -> T41" } ], "type": "Graph" } } ---------------------------------------- (76) Obligation: Rules: f237_in(T49) -> f3_in(T49) :|: TRUE f3_out(x) -> f237_out(x) :|: TRUE f3_out([]) -> f231_out :|: TRUE f231_in -> f3_in([]) :|: TRUE f48_in(T15) -> f50_in(T15) :|: TRUE f48_in(x1) -> f49_in(x1) :|: TRUE f50_out(x2) -> f48_out(x2) :|: TRUE f49_out(x3) -> f48_out(x3) :|: TRUE f50_in(x4) -> f234_in :|: TRUE f233_out(T38, T39) -> f50_out(.(T38, T39)) :|: TRUE f234_out -> f50_out(x5) :|: TRUE f50_in(.(x6, x7)) -> f233_in(x6, x7) :|: TRUE f235_in(x8, x9) -> f236_in(x8, x9) :|: TRUE f236_out(x10, x11) -> f235_out(x10, x11) :|: TRUE f35_in(x12) -> f48_in(x12) :|: TRUE f48_out(x13) -> f35_out(x13) :|: TRUE f235_out(x14, x15) -> f233_out(x14, x15) :|: TRUE f233_in(x16, x17) -> f235_in(x16, x17) :|: TRUE f237_out(x18) -> f236_out(x19, x18) :|: TRUE f236_in(x20, x21) -> f237_in(x21) :|: TRUE f28_out(T1) -> f4_out(T1) :|: TRUE f4_in([]) -> f27_in :|: TRUE f4_in(x22) -> f28_in(x22) :|: TRUE f27_out -> f4_out([]) :|: TRUE f231_out -> f54_out :|: TRUE f54_in -> f231_in :|: TRUE f53_in -> f54_in :|: TRUE f53_in -> f55_in :|: TRUE f55_out -> f53_out :|: TRUE f54_out -> f53_out :|: TRUE f4_out(x23) -> f3_out(x23) :|: TRUE f3_in(x24) -> f4_in(x24) :|: TRUE f36_out -> f28_out(x25) :|: TRUE f28_in(x26) -> f35_in(x26) :|: TRUE f28_in(x27) -> f36_in :|: TRUE f35_out(x28) -> f28_out(x28) :|: TRUE f53_out -> f51_out :|: TRUE f51_in -> f53_in :|: TRUE f51_out -> f49_out([]) :|: TRUE f49_in([]) -> f51_in :|: TRUE f52_out -> f49_out(x29) :|: TRUE f49_in(x30) -> f52_in :|: TRUE Start term: f3_in(T1) ---------------------------------------- (77) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f237_in(T49) -> f3_in(T49) :|: TRUE f231_in -> f3_in([]) :|: TRUE f48_in(T15) -> f50_in(T15) :|: TRUE f48_in(x1) -> f49_in(x1) :|: TRUE f50_in(.(x6, x7)) -> f233_in(x6, x7) :|: TRUE f235_in(x8, x9) -> f236_in(x8, x9) :|: TRUE f35_in(x12) -> f48_in(x12) :|: TRUE f233_in(x16, x17) -> f235_in(x16, x17) :|: TRUE f236_in(x20, x21) -> f237_in(x21) :|: TRUE f4_in(x22) -> f28_in(x22) :|: TRUE f54_in -> f231_in :|: TRUE f53_in -> f54_in :|: TRUE f3_in(x24) -> f4_in(x24) :|: TRUE f28_in(x26) -> f35_in(x26) :|: TRUE f51_in -> f53_in :|: TRUE f49_in([]) -> f51_in :|: TRUE ---------------------------------------- (78) Obligation: Rules: f237_in(T49) -> f3_in(T49) :|: TRUE f231_in -> f3_in([]) :|: TRUE f48_in(T15) -> f50_in(T15) :|: TRUE f48_in(x1) -> f49_in(x1) :|: TRUE f50_in(.(x6, x7)) -> f233_in(x6, x7) :|: TRUE f235_in(x8, x9) -> f236_in(x8, x9) :|: TRUE f35_in(x12) -> f48_in(x12) :|: TRUE f233_in(x16, x17) -> f235_in(x16, x17) :|: TRUE f236_in(x20, x21) -> f237_in(x21) :|: TRUE f4_in(x22) -> f28_in(x22) :|: TRUE f54_in -> f231_in :|: TRUE f53_in -> f54_in :|: TRUE f3_in(x24) -> f4_in(x24) :|: TRUE f28_in(x26) -> f35_in(x26) :|: TRUE f51_in -> f53_in :|: TRUE f49_in([]) -> f51_in :|: TRUE ---------------------------------------- (79) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (80) Obligation: Rules: f35_in([]) -> f35_in([]) :|: TRUE f35_in(.(x6:0, x7:0)) -> f35_in(x7:0) :|: TRUE ---------------------------------------- (81) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (82) Obligation: Rules: f35_in([]) -> f35_in([]) :|: TRUE f35_in(.(x6:0, x7:0)) -> f35_in(x7:0) :|: TRUE ---------------------------------------- (83) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f35_in([]) -> f35_in([]) :|: TRUE (2) f35_in(.(x6:0, x7:0)) -> f35_in(x7:0) :|: TRUE Arcs: (1) -> (1) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (84) Complex Obligation (AND) ---------------------------------------- (85) Obligation: Termination digraph: Nodes: (1) f35_in(.(x6:0, x7:0)) -> f35_in(x7:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (86) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (87) Obligation: Rules: f35_in(.(x7:0)) -> f35_in(x7:0) :|: TRUE ---------------------------------------- (88) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f35_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (89) Obligation: Rules: f35_in(.(x7:0)) -> f35_in(x7:0) ---------------------------------------- (90) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: f35_in(.(x7:0)) -> f35_in(x7:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (92) 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: *f35_in(.(x7:0)) -> f35_in(x7:0) The graph contains the following edges 1 > 1 ---------------------------------------- (93) YES ---------------------------------------- (94) Obligation: Termination digraph: Nodes: (1) f35_in([]) -> f35_in([]) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated!