/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern flat(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 9 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 2 ms] (10) QDP (11) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) QDP (15) UsableRulesProof [EQUIVALENT, 1 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) NonTerminationLoopProof [COMPLETE, 0 ms] (20) NO (21) PrologToPiTRSProof [SOUND, 0 ms] (22) PiTRS (23) DependencyPairsProof [EQUIVALENT, 5 ms] (24) PiDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) PiDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) PiDP (29) PiDPToQDPProof [SOUND, 7 ms] (30) QDP (31) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (32) QDP (33) DependencyGraphProof [EQUIVALENT, 0 ms] (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QReductionProof [EQUIVALENT, 0 ms] (38) QDP (39) NonTerminationLoopProof [COMPLETE, 0 ms] (40) NO (41) PrologToTRSTransformerProof [SOUND, 0 ms] (42) QTRS (43) DependencyPairsProof [EQUIVALENT, 0 ms] (44) QDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) QDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) QDP (49) UsableRulesReductionPairsProof [EQUIVALENT, 1 ms] (50) QDP (51) NonTerminationLoopProof [COMPLETE, 0 ms] (52) NO (53) PrologToDTProblemTransformerProof [SOUND, 0 ms] (54) TRIPLES (55) TriplesToPiDPProof [SOUND, 0 ms] (56) PiDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) PiDP (59) PiDPToQDPProof [SOUND, 1 ms] (60) QDP (61) MRRProof [EQUIVALENT, 0 ms] (62) QDP (63) NonTerminationLoopProof [COMPLETE, 0 ms] (64) NO (65) PrologToIRSwTTransformerProof [SOUND, 0 ms] (66) IRSwT (67) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (68) IRSwT (69) IntTRSCompressionProof [EQUIVALENT, 22 ms] (70) IRSwT (71) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (72) IRSwT (73) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (74) IRSwT (75) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (76) IRSwT ---------------------------------------- (0) Obligation: Clauses: right(tree(X, XS1, XS2), XS2). flat(niltree, nil). flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS)). flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS). Query: flat(a,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: flat_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) ---------------------------------------- (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: FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x6, x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x6, x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) The argument filtering Pi contains the following mapping: cons(x1, x2) = cons(x1, x2) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(X, YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(cons(X, YS)) -> U1_AG(X, YS, right_in_aa) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) 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. The following dependency pairs can be deleted: FLAT_IN_AG(cons(X, YS)) -> U1_AG(X, YS, right_in_aa) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(FLAT_IN_AG(x_1)) = x_1 POL(U1_AG(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(right_in_aa) = 0 POL(right_out_aa) = 0 ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(X, YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) 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. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) 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]. right_in_aa ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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 = FLAT_IN_AG(ZS) evaluates to t =FLAT_IN_AG(ZS) 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 FLAT_IN_AG(ZS) to FLAT_IN_AG(ZS). ---------------------------------------- (20) NO ---------------------------------------- (21) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: flat_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (22) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) ---------------------------------------- (23) 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: FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (26) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (27) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) The argument filtering Pi contains the following mapping: cons(x1, x2) = cons(x1, x2) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(cons(X, YS)) -> U1_AG(YS, right_in_aa) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (31) 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. The following dependency pairs can be deleted: FLAT_IN_AG(cons(X, YS)) -> U1_AG(YS, right_in_aa) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(FLAT_IN_AG(x_1)) = x_1 POL(U1_AG(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(right_in_aa) = 0 POL(right_out_aa) = 0 ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) 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. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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]. right_in_aa ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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 = FLAT_IN_AG(ZS) evaluates to t =FLAT_IN_AG(ZS) 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 FLAT_IN_AG(ZS) to FLAT_IN_AG(ZS). ---------------------------------------- (40) NO ---------------------------------------- (41) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "36": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "type": "Nodes", "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "3": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 T49)) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "225": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "7": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T26 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "40": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 6, "label": "PARALLEL" }, { "from": 3, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 26, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 6, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 36, "label": "PARALLEL" }, { "from": 7, "to": 37, "label": "PARALLEL" }, { "from": 26, "to": 30, "label": "SUCCESS" }, { "from": 36, "to": 38, "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T18,\nT1 -> tree(T15, niltree, T18),\nX17 -> T17,\nT2 -> cons(T15, T17),\nT16 -> T18" }, { "from": 36, "to": 40, "label": "EVAL-BACKTRACK" }, { "from": 37, "to": 224, "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T47,\nX41 -> T45,\nX42 -> T46,\nX43 -> T48,\nX44 -> T49,\nT1 -> tree(T47, tree(T45, T46, T48), T49),\nT2 -> T44,\nX45 -> T44,\nT40 -> T45,\nT41 -> T46,\nT39 -> T47,\nT42 -> T48,\nT43 -> T49" }, { "from": 37, "to": 225, "label": "EVAL-BACKTRACK" }, { "from": 38, "to": 43, "label": "CASE" }, { "from": 43, "to": 92, "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T24,\nX25 -> T24,\nX26 -> niltree,\nT18 -> T26,\nX27 -> T26,\nX18 -> T26,\nT25 -> T26" }, { "from": 92, "to": 1, "label": "INSTANCE with matching:\nT1 -> T26\nT2 -> T17" }, { "from": 224, "to": 1, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, T49))\nT2 -> T44" } ], "type": "Graph" } } ---------------------------------------- (42) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(nil) -> f1_out1 f1_in(cons(T24, T17)) -> U1(f1_in(T17), cons(T24, T17)) U1(f1_out1, cons(T24, T17)) -> f1_out1 f1_in(T44) -> U2(f1_in(T44), T44) U2(f1_out1, T44) -> f1_out1 Q is empty. ---------------------------------------- (43) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(cons(T24, T17)) -> U1^1(f1_in(T17), cons(T24, T17)) F1_IN(cons(T24, T17)) -> F1_IN(T17) F1_IN(T44) -> U2^1(f1_in(T44), T44) F1_IN(T44) -> F1_IN(T44) The TRS R consists of the following rules: f1_in(nil) -> f1_out1 f1_in(cons(T24, T17)) -> U1(f1_in(T17), cons(T24, T17)) U1(f1_out1, cons(T24, T17)) -> f1_out1 f1_in(T44) -> U2(f1_in(T44), T44) U2(f1_out1, T44) -> f1_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T44) -> F1_IN(T44) F1_IN(cons(T24, T17)) -> F1_IN(T17) The TRS R consists of the following rules: f1_in(nil) -> f1_out1 f1_in(cons(T24, T17)) -> U1(f1_in(T17), cons(T24, T17)) U1(f1_out1, cons(T24, T17)) -> f1_out1 f1_in(T44) -> U2(f1_in(T44), T44) U2(f1_out1, T44) -> f1_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T44) -> F1_IN(T44) F1_IN(cons(T24, T17)) -> F1_IN(T17) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) 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. The following dependency pairs can be deleted: F1_IN(cons(T24, T17)) -> F1_IN(T17) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(F1_IN(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T44) -> F1_IN(T44) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) 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 = F1_IN(T44) evaluates to t =F1_IN(T44) 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 F1_IN(T44) to F1_IN(T44). ---------------------------------------- (52) NO ---------------------------------------- (53) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "44": { "goal": [ { "clause": 2, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [{ "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "46": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 (tree T49 T50 T51))) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "29": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 (nil))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "252": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T185 T186 (tree T187 T188 (tree T189 T190 T191))) T184)" }], "kb": { "nonunifying": [ [ "(flat T1 T184)", "(flat (niltree) (nil))" ], [ "(flat T1 T184)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T184"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "231": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "253": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [ { "clause": 1, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" } ], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "233": { "goal": [ { "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" } ], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "234": { "goal": [{ "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "235": { "goal": [{ "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "236": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T135 (niltree) (tree T140 T141 T142)) X106) (flat X106 T139))" }], "kb": { "nonunifying": [[ "(flat T1 (cons T135 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T135", "T139" ], "free": [ "X40", "X41", "X42", "X106" ], "exprvars": [] } }, "237": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": 0, "scope": 5, "term": "(',' (right (tree T135 (niltree) (tree T140 T141 T142)) X106) (flat X106 T139))" }], "kb": { "nonunifying": [[ "(flat T1 (cons T135 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T135", "T139" ], "free": [ "X40", "X41", "X42", "X106" ], "exprvars": [] } }, "217": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T158 T159 T160) T139)" }], "kb": { "nonunifying": [[ "(flat T1 (cons T154 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T139", "T154" ], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "218": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [ [ "(flat T1 T2)", "(flat (niltree) (nil))" ], [ "(flat T1 T2)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "219": { "goal": [ { "clause": 0, "scope": 3, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "10": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "35": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(flat T1 (nil))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [[ "(flat T1 T2)", "(flat (niltree) (nil))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": 0, "scope": 3, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "221": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T71 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [], "exprvars": [] } }, "223": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T93 T94 (tree T95 T96 T97)) (cons T91 T92))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T91", "T92" ], "free": [], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "41": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [ { "clause": 1, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 2, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 10, "label": "CASE" }, { "from": 10, "to": 18, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 10, "to": 19, "label": "EVAL-BACKTRACK" }, { "from": 18, "to": 29, "label": "SUCCESS" }, { "from": 19, "to": 217, "label": "EVAL with clause\nflat(tree(X40, niltree, X41), cons(X40, X42)) :- ','(right(tree(X40, niltree, X41), X43), flat(X43, X42)).\nand substitutionX40 -> T55,\nX41 -> T58,\nT1 -> tree(T55, niltree, T58),\nX42 -> T57,\nT2 -> cons(T55, T57),\nT56 -> T58" }, { "from": 19, "to": 218, "label": "EVAL-BACKTRACK" }, { "from": 29, "to": 35, "label": "BACKTRACK\nfor clause: flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS))because of non-unification" }, { "from": 35, "to": 39, "label": "EVAL with clause\nflat(tree(X10, tree(X11, X12, X13), X14), X15) :- flat(tree(X11, X12, tree(X10, X13, X14)), X15).\nand substitutionX10 -> T17,\nX11 -> T15,\nX12 -> T16,\nX13 -> T18,\nX14 -> T19,\nT1 -> tree(T17, tree(T15, T16, T18), T19),\nX15 -> nil,\nT11 -> T15,\nT12 -> T16,\nT10 -> T17,\nT13 -> T18,\nT14 -> T19" }, { "from": 35, "to": 41, "label": "EVAL-BACKTRACK" }, { "from": 39, "to": 42, "label": "CASE" }, { "from": 42, "to": 44, "label": "BACKTRACK\nfor clause: flat(niltree, nil)because of non-unification" }, { "from": 44, "to": 45, "label": "BACKTRACK\nfor clause: flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS))because of non-unification" }, { "from": 45, "to": 46, "label": "EVAL with clause\nflat(tree(X31, tree(X32, X33, X34), X35), X36) :- flat(tree(X32, X33, tree(X31, X34, X35)), X36).\nand substitutionT15 -> T47,\nX31 -> T47,\nX32 -> T45,\nX33 -> T46,\nX34 -> T48,\nT16 -> tree(T45, T46, T48),\nT17 -> T49,\nT18 -> T50,\nT19 -> T51,\nX35 -> tree(T49, T50, T51),\nX36 -> nil,\nT39 -> T45,\nT40 -> T46,\nT38 -> T47,\nT41 -> T48,\nT42 -> T49,\nT43 -> T50,\nT44 -> T51" }, { "from": 45, "to": 47, "label": "EVAL-BACKTRACK" }, { "from": 46, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, tree(T49, T50, T51)))\nT2 -> nil" }, { "from": 217, "to": 219, "label": "CASE" }, { "from": 218, "to": 230, "label": "EVAL with clause\nflat(tree(X83, tree(X84, X85, X86), X87), X88) :- flat(tree(X84, X85, tree(X83, X86, X87)), X88).\nand substitutionX83 -> T112,\nX84 -> T110,\nX85 -> T111,\nX86 -> T113,\nX87 -> T114,\nT1 -> tree(T112, tree(T110, T111, T113), T114),\nT2 -> T109,\nX88 -> T109,\nT105 -> T110,\nT106 -> T111,\nT104 -> T112,\nT107 -> T113,\nT108 -> T114" }, { "from": 218, "to": 231, "label": "EVAL-BACKTRACK" }, { "from": 219, "to": 220, "label": "PARALLEL" }, { "from": 219, "to": 221, "label": "PARALLEL" }, { "from": 220, "to": 222, "label": "ONLY EVAL with clause\nright(tree(X56, X57, X58), X58).\nand substitutionT55 -> T69,\nX56 -> T69,\nX57 -> niltree,\nT58 -> T71,\nX58 -> T71,\nX43 -> T71,\nT70 -> T71" }, { "from": 221, "to": 223, "label": "FAILURE" }, { "from": 222, "to": 2, "label": "INSTANCE with matching:\nT1 -> T71\nT2 -> T57" }, { "from": 223, "to": 226, "label": "EVAL with clause\nflat(tree(X71, tree(X72, X73, X74), X75), X76) :- flat(tree(X72, X73, tree(X71, X74, X75)), X76).\nand substitutionX71 -> T95,\nX72 -> T93,\nX73 -> T94,\nX74 -> T96,\nX75 -> T97,\nT1 -> tree(T95, tree(T93, T94, T96), T97),\nT55 -> T91,\nT57 -> T92,\nX76 -> cons(T91, T92),\nT87 -> T93,\nT88 -> T94,\nT86 -> T95,\nT89 -> T96,\nT90 -> T97" }, { "from": 223, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T93, T94, tree(T95, T96, T97))\nT2 -> cons(T91, T92)" }, { "from": 230, "to": 232, "label": "CASE" }, { "from": 232, "to": 233, "label": "BACKTRACK\nfor clause: flat(niltree, nil)because of non-unification" }, { "from": 233, "to": 234, "label": "PARALLEL" }, { "from": 233, "to": 235, "label": "PARALLEL" }, { "from": 234, "to": 236, "label": "EVAL with clause\nflat(tree(X103, niltree, X104), cons(X103, X105)) :- ','(right(tree(X103, niltree, X104), X106), flat(X106, X105)).\nand substitutionT110 -> T135,\nX103 -> T135,\nT111 -> niltree,\nT112 -> T140,\nT113 -> T141,\nT114 -> T142,\nX104 -> tree(T140, T141, T142),\nX105 -> T139,\nT109 -> cons(T135, T139),\nT136 -> T140,\nT137 -> T141,\nT138 -> T142" }, { "from": 234, "to": 237, "label": "EVAL-BACKTRACK" }, { "from": 235, "to": 252, "label": "EVAL with clause\nflat(tree(X128, tree(X129, X130, X131), X132), X133) :- flat(tree(X129, X130, tree(X128, X131, X132)), X133).\nand substitutionT110 -> T187,\nX128 -> T187,\nX129 -> T185,\nX130 -> T186,\nX131 -> T188,\nT111 -> tree(T185, T186, T188),\nT112 -> T189,\nT113 -> T190,\nT114 -> T191,\nX132 -> tree(T189, T190, T191),\nT109 -> T184,\nX133 -> T184,\nT178 -> T185,\nT179 -> T186,\nT177 -> T187,\nT180 -> T188,\nT181 -> T189,\nT182 -> T190,\nT183 -> T191" }, { "from": 235, "to": 253, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 238, "label": "CASE" }, { "from": 238, "to": 239, "label": "ONLY EVAL with clause\nright(tree(X113, X114, X115), X115).\nand substitutionT135 -> T154,\nX113 -> T154,\nX114 -> niltree,\nT140 -> T158,\nT141 -> T159,\nT142 -> T160,\nX115 -> tree(T158, T159, T160),\nX106 -> tree(T158, T159, T160),\nT155 -> T158,\nT156 -> T159,\nT157 -> T160" }, { "from": 239, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T158, T159, T160)\nT2 -> T139" }, { "from": 252, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T185, T186, tree(T187, T188, tree(T189, T190, T191)))\nT2 -> T184" } ], "type": "Graph" } } ---------------------------------------- (54) Obligation: Triples: flatA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) :- flatA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil). flatA(tree(X1, niltree, X2), cons(X1, X3)) :- flatA(X2, X3). flatA(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) :- flatA(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)). flatA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatA(tree(X1, X3, X4), X5). flatA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Clauses: flatcA(niltree, nil). flatcA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) :- flatcA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil). flatcA(tree(X1, niltree, X2), cons(X1, X3)) :- flatcA(X2, X3). flatcA(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) :- flatcA(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)). flatcA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatcA(tree(X1, X3, X4), X5). flatcA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatcA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Afs: flatA(x1, x2) = flatA(x2) ---------------------------------------- (55) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: flatA_in_2: (f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> U1_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> U2_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> U3_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7))) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U4_AG(X1, X2, X3, X4, X5, flatA_in_ag(tree(X1, X3, X4), X5)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U5_AG(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AG(x8) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U3_AG(x6, x7, x8) U4_AG(x1, x2, x3, x4, x5, x6) = U4_AG(x2, x5, x6) U5_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U5_AG(x8, x9) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (56) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> U1_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> U2_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> U3_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7))) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U4_AG(X1, X2, X3, X4, X5, flatA_in_ag(tree(X1, X3, X4), X5)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U5_AG(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AG(x8) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U3_AG(x6, x7, x8) U4_AG(x1, x2, x3, x4, x5, x6) = U4_AG(x2, x5, x6) U5_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U5_AG(x8, x9) We have to consider all (P,R,Pi)-chains ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 5 less nodes. ---------------------------------------- (58) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (59) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X8) -> FLATA_IN_AG(X8) FLATA_IN_AG(nil) -> FLATA_IN_AG(nil) FLATA_IN_AG(cons(X1, X3)) -> FLATA_IN_AG(X3) FLATA_IN_AG(cons(X6, X7)) -> FLATA_IN_AG(cons(X6, X7)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) MRRProof (EQUIVALENT) 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. Strictly oriented dependency pairs: FLATA_IN_AG(cons(X1, X3)) -> FLATA_IN_AG(X3) Used ordering: Polynomial interpretation [POLO]: POL(FLATA_IN_AG(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(nil) = 0 ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X8) -> FLATA_IN_AG(X8) FLATA_IN_AG(nil) -> FLATA_IN_AG(nil) FLATA_IN_AG(cons(X6, X7)) -> FLATA_IN_AG(cons(X6, X7)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (63) 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 = FLATA_IN_AG(X8) evaluates to t =FLATA_IN_AG(X8) 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 FLATA_IN_AG(X8) to FLATA_IN_AG(X8). ---------------------------------------- (64) NO ---------------------------------------- (65) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 4, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "177": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T26 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "115": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "116": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 T49)) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "117": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "216": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "20": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "32": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 4, "to": 5, "label": "CASE" }, { "from": 5, "to": 8, "label": "PARALLEL" }, { "from": 5, "to": 9, "label": "PARALLEL" }, { "from": 8, "to": 17, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 8, "to": 20, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 31, "label": "PARALLEL" }, { "from": 9, "to": 32, "label": "PARALLEL" }, { "from": 17, "to": 28, "label": "SUCCESS" }, { "from": 31, "to": 115, "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T18,\nT1 -> tree(T15, niltree, T18),\nX17 -> T17,\nT2 -> cons(T15, T17),\nT16 -> T18" }, { "from": 31, "to": 116, "label": "EVAL-BACKTRACK" }, { "from": 32, "to": 215, "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T47,\nX41 -> T45,\nX42 -> T46,\nX43 -> T48,\nX44 -> T49,\nT1 -> tree(T47, tree(T45, T46, T48), T49),\nT2 -> T44,\nX45 -> T44,\nT40 -> T45,\nT41 -> T46,\nT39 -> T47,\nT42 -> T48,\nT43 -> T49" }, { "from": 32, "to": 216, "label": "EVAL-BACKTRACK" }, { "from": 115, "to": 117, "label": "CASE" }, { "from": 117, "to": 177, "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T24,\nX25 -> T24,\nX26 -> niltree,\nT18 -> T26,\nX27 -> T26,\nX18 -> T26,\nT25 -> T26" }, { "from": 177, "to": 4, "label": "INSTANCE with matching:\nT1 -> T26\nT2 -> T17" }, { "from": 215, "to": 4, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, T49))\nT2 -> T44" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Rules: f4_out(T17) -> f177_out(T17) :|: TRUE f177_in(x) -> f4_in(x) :|: TRUE f4_out(T44) -> f215_out(T44) :|: TRUE f215_in(x1) -> f4_in(x1) :|: TRUE f31_in(cons(x2, x3)) -> f115_in(x2, x3) :|: TRUE f115_out(x4, x5) -> f31_out(cons(x4, x5)) :|: TRUE f31_in(T2) -> f116_in :|: TRUE f116_out -> f31_out(x6) :|: TRUE f117_out(x7, x8) -> f115_out(x7, x8) :|: TRUE f115_in(x9, x10) -> f117_in(x9, x10) :|: TRUE f117_in(x11, x12) -> f177_in(x12) :|: TRUE f177_out(x13) -> f117_out(x14, x13) :|: TRUE f5_in(x15) -> f8_in(x15) :|: TRUE f9_out(x16) -> f5_out(x16) :|: TRUE f8_out(x17) -> f5_out(x17) :|: TRUE f5_in(x18) -> f9_in(x18) :|: TRUE f215_out(x19) -> f32_out(x19) :|: TRUE f216_out -> f32_out(x20) :|: TRUE f32_in(x21) -> f215_in(x21) :|: TRUE f32_in(x22) -> f216_in :|: TRUE f9_in(x23) -> f31_in(x23) :|: TRUE f31_out(x24) -> f9_out(x24) :|: TRUE f32_out(x25) -> f9_out(x25) :|: TRUE f9_in(x26) -> f32_in(x26) :|: TRUE f5_out(x27) -> f4_out(x27) :|: TRUE f4_in(x28) -> f5_in(x28) :|: TRUE Start term: f4_in(T2) ---------------------------------------- (67) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f177_in(x) -> f4_in(x) :|: TRUE f215_in(x1) -> f4_in(x1) :|: TRUE f31_in(cons(x2, x3)) -> f115_in(x2, x3) :|: TRUE f115_in(x9, x10) -> f117_in(x9, x10) :|: TRUE f117_in(x11, x12) -> f177_in(x12) :|: TRUE f5_in(x18) -> f9_in(x18) :|: TRUE f32_in(x21) -> f215_in(x21) :|: TRUE f9_in(x23) -> f31_in(x23) :|: TRUE f9_in(x26) -> f32_in(x26) :|: TRUE f4_in(x28) -> f5_in(x28) :|: TRUE ---------------------------------------- (68) Obligation: Rules: f177_in(x) -> f4_in(x) :|: TRUE f215_in(x1) -> f4_in(x1) :|: TRUE f31_in(cons(x2, x3)) -> f115_in(x2, x3) :|: TRUE f115_in(x9, x10) -> f117_in(x9, x10) :|: TRUE f117_in(x11, x12) -> f177_in(x12) :|: TRUE f5_in(x18) -> f9_in(x18) :|: TRUE f32_in(x21) -> f215_in(x21) :|: TRUE f9_in(x23) -> f31_in(x23) :|: TRUE f9_in(x26) -> f32_in(x26) :|: TRUE f4_in(x28) -> f5_in(x28) :|: TRUE ---------------------------------------- (69) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (70) Obligation: Rules: f5_in(x18:0) -> f5_in(x18:0) :|: TRUE f5_in(cons(x2:0, x3:0)) -> f5_in(x3:0) :|: TRUE ---------------------------------------- (71) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (72) Obligation: Rules: f5_in(x18:0) -> f5_in(x18:0) :|: TRUE f5_in(cons(x2:0, x3:0)) -> f5_in(x3:0) :|: TRUE ---------------------------------------- (73) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5_in(x18:0) -> f5_in(x18:0) :|: TRUE (2) f5_in(cons(x2:0, x3:0)) -> f5_in(x3:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (74) Obligation: Termination digraph: Nodes: (1) f5_in(x18:0) -> f5_in(x18:0) :|: TRUE (2) f5_in(cons(x2:0, x3:0)) -> f5_in(x3:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (75) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: cons(x1, x2) -> cons(x2) ---------------------------------------- (76) Obligation: Rules: f5_in(x18:0) -> f5_in(x18:0) :|: TRUE f5_in(cons(x3:0)) -> f5_in(x3:0) :|: TRUE