/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern p(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 0 ms] (2) QTRS (3) Overlay + Local Confluence [EQUIVALENT, 0 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) NonInfProof [EQUIVALENT, 52 ms] (22) AND (23) QDP (24) DependencyGraphProof [EQUIVALENT, 0 ms] (25) TRUE (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) TRUE ---------------------------------------- (0) Obligation: Clauses: p(X, Y) :- ','(less(X, Y), ','(!, p(s(X), Y))). less(0, s(X1)). less(s(X), s(Y)) :- less(X, Y). Query: p(g,g) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 2, "program": { "directives": [], "clauses": [ [ "(p X Y)", "(',' (less X Y) (',' (!) (p (s X) Y)))" ], [ "(less (0) (s X1))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "88": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "89": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s T9) T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "118": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T24 T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T24", "T25" ], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T9 T10) (',' (!_1) (p (s T9) T10)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "82": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "83": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_1) (p (s T9) T10))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "84": { "goal": [ { "clause": 1, "scope": 2, "term": "(less T9 T10)" }, { "clause": 2, "scope": 2, "term": "(less T9 T10)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "85": { "goal": [{ "clause": 1, "scope": 2, "term": "(less T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "86": { "goal": [{ "clause": 2, "scope": 2, "term": "(less T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "87": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "ONLY EVAL with clause\np(X8, X9) :- ','(less(X8, X9), ','(!_1, p(s(X8), X9))).\nand substitutionT1 -> T9,\nX8 -> T9,\nT2 -> T10,\nX9 -> T10" }, { "from": 9, "to": 82, "label": "SPLIT 1" }, { "from": 9, "to": 83, "label": "SPLIT 2\nnew knowledge:\nT9 is ground\nT10 is ground" }, { "from": 82, "to": 84, "label": "CASE" }, { "from": 83, "to": 132, "label": "CUT" }, { "from": 84, "to": 85, "label": "PARALLEL" }, { "from": 84, "to": 86, "label": "PARALLEL" }, { "from": 85, "to": 87, "label": "EVAL with clause\nless(0, s(X18)).\nand substitutionT9 -> 0,\nX18 -> T19,\nT10 -> s(T19)" }, { "from": 85, "to": 88, "label": "EVAL-BACKTRACK" }, { "from": 86, "to": 118, "label": "EVAL with clause\nless(s(X23), s(X24)) :- less(X23, X24).\nand substitutionX23 -> T24,\nT9 -> s(T24),\nX24 -> T25,\nT10 -> s(T25)" }, { "from": 86, "to": 123, "label": "EVAL-BACKTRACK" }, { "from": 87, "to": 89, "label": "SUCCESS" }, { "from": 118, "to": 82, "label": "INSTANCE with matching:\nT9 -> T24\nT10 -> T25" }, { "from": 132, "to": 2, "label": "INSTANCE with matching:\nT1 -> s(T9)\nT2 -> T10" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in(T9, T10) -> U1(f9_in(T9, T10), T9, T10) U1(f9_out1, T9, T10) -> f2_out1 f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 f83_in(T9, T10) -> U3(f2_in(s(T9), T10), T9, T10) U3(f2_out1, T9, T10) -> f83_out1 f9_in(T9, T10) -> U4(f82_in(T9, T10), T9, T10) U4(f82_out1, T9, T10) -> U5(f83_in(T9, T10), T9, T10) U5(f83_out1, T9, T10) -> f9_out1 Q is empty. ---------------------------------------- (3) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in(T9, T10) -> U1(f9_in(T9, T10), T9, T10) U1(f9_out1, T9, T10) -> f2_out1 f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 f83_in(T9, T10) -> U3(f2_in(s(T9), T10), T9, T10) U3(f2_out1, T9, T10) -> f83_out1 f9_in(T9, T10) -> U4(f82_in(T9, T10), T9, T10) U4(f82_out1, T9, T10) -> U5(f83_in(T9, T10), T9, T10) U5(f83_out1, T9, T10) -> f9_out1 The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T9, T10) -> U1^1(f9_in(T9, T10), T9, T10) F2_IN(T9, T10) -> F9_IN(T9, T10) F82_IN(s(T24), s(T25)) -> U2^1(f82_in(T24, T25), s(T24), s(T25)) F82_IN(s(T24), s(T25)) -> F82_IN(T24, T25) F83_IN(T9, T10) -> U3^1(f2_in(s(T9), T10), T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) F9_IN(T9, T10) -> F82_IN(T9, T10) U4^1(f82_out1, T9, T10) -> U5^1(f83_in(T9, T10), T9, T10) U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) The TRS R consists of the following rules: f2_in(T9, T10) -> U1(f9_in(T9, T10), T9, T10) U1(f9_out1, T9, T10) -> f2_out1 f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 f83_in(T9, T10) -> U3(f2_in(s(T9), T10), T9, T10) U3(f2_out1, T9, T10) -> f83_out1 f9_in(T9, T10) -> U4(f82_in(T9, T10), T9, T10) U4(f82_out1, T9, T10) -> U5(f83_in(T9, T10), T9, T10) U5(f83_out1, T9, T10) -> f9_out1 The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(s(T24), s(T25)) -> F82_IN(T24, T25) The TRS R consists of the following rules: f2_in(T9, T10) -> U1(f9_in(T9, T10), T9, T10) U1(f9_out1, T9, T10) -> f2_out1 f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 f83_in(T9, T10) -> U3(f2_in(s(T9), T10), T9, T10) U3(f2_out1, T9, T10) -> f83_out1 f9_in(T9, T10) -> U4(f82_in(T9, T10), T9, T10) U4(f82_out1, T9, T10) -> U5(f83_in(T9, T10), T9, T10) U5(f83_out1, T9, T10) -> f9_out1 The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(s(T24), s(T25)) -> F82_IN(T24, T25) R is empty. The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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]. f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: F82_IN(s(T24), s(T25)) -> F82_IN(T24, T25) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) 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: *F82_IN(s(T24), s(T25)) -> F82_IN(T24, T25) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T9, T10) -> F9_IN(T9, T10) F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) The TRS R consists of the following rules: f2_in(T9, T10) -> U1(f9_in(T9, T10), T9, T10) U1(f9_out1, T9, T10) -> f2_out1 f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 f83_in(T9, T10) -> U3(f2_in(s(T9), T10), T9, T10) U3(f2_out1, T9, T10) -> f83_out1 f9_in(T9, T10) -> U4(f82_in(T9, T10), T9, T10) U4(f82_out1, T9, T10) -> U5(f83_in(T9, T10), T9, T10) U5(f83_out1, T9, T10) -> f9_out1 The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T9, T10) -> F9_IN(T9, T10) F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) The TRS R consists of the following rules: f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 The set Q consists of the following terms: f2_in(x0, x1) U1(f9_out1, x0, x1) f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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]. f2_in(x0, x1) U1(f9_out1, x0, x1) f83_in(x0, x1) U3(f2_out1, x0, x1) f9_in(x0, x1) U4(f82_out1, x0, x1) U5(f83_out1, x0, x1) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T9, T10) -> F9_IN(T9, T10) F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) The TRS R consists of the following rules: f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 The set Q consists of the following terms: f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) NonInfProof (EQUIVALENT) The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: Note that final constraints are written in bold face. For Pair F2_IN(T9, T10) -> F9_IN(T9, T10) the following chains were created: *We consider the chain F83_IN(x6, x7) -> F2_IN(s(x6), x7), F2_IN(x8, x9) -> F9_IN(x8, x9) which results in the following constraint: (1) (F2_IN(s(x6), x7)=F2_IN(x8, x9) ==> F2_IN(x8, x9)_>=_F9_IN(x8, x9)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (F2_IN(s(x6), x7)_>=_F9_IN(s(x6), x7)) For Pair F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) the following chains were created: *We consider the chain F2_IN(x10, x11) -> F9_IN(x10, x11), F9_IN(x12, x13) -> U4^1(f82_in(x12, x13), x12, x13) which results in the following constraint: (1) (F9_IN(x10, x11)=F9_IN(x12, x13) ==> F9_IN(x12, x13)_>=_U4^1(f82_in(x12, x13), x12, x13)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (F9_IN(x10, x11)_>=_U4^1(f82_in(x10, x11), x10, x11)) For Pair U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) the following chains were created: *We consider the chain F9_IN(x22, x23) -> U4^1(f82_in(x22, x23), x22, x23), U4^1(f82_out1, x24, x25) -> F83_IN(x24, x25) which results in the following constraint: (1) (U4^1(f82_in(x22, x23), x22, x23)=U4^1(f82_out1, x24, x25) ==> U4^1(f82_out1, x24, x25)_>=_F83_IN(x24, x25)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (f82_in(x22, x23)=f82_out1 ==> U4^1(f82_out1, x22, x23)_>=_F83_IN(x22, x23)) We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on f82_in(x22, x23)=f82_out1 which results in the following new constraints: (3) (f82_out1=f82_out1 ==> U4^1(f82_out1, 0, s(x40))_>=_F83_IN(0, s(x40))) (4) (U2(f82_in(x42, x41), s(x42), s(x41))=f82_out1 & (f82_in(x42, x41)=f82_out1 ==> U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41)) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) We simplified constraint (3) using rules (I), (II) which results in the following new constraint: (5) (U4^1(f82_out1, 0, s(x40))_>=_F83_IN(0, s(x40))) We simplified constraint (4) using rule (VII) which results in the following new constraint: (6) (f82_in(x42, x41)=x43 & s(x42)=x44 & s(x41)=x45 & U2(x43, x44, x45)=f82_out1 & (f82_in(x42, x41)=f82_out1 ==> U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41)) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) We simplified constraint (6) using rule (V) (with possible (I) afterwards) using induction on U2(x43, x44, x45)=f82_out1 which results in the following new constraint: (7) (f82_out1=f82_out1 & f82_in(x42, x41)=f82_out1 & s(x42)=s(x47) & s(x41)=s(x46) & (f82_in(x42, x41)=f82_out1 ==> U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41)) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) We simplified constraint (7) using rules (I), (II) which results in the following new constraint: (8) (f82_in(x42, x41)=f82_out1 & x42=x47 & x41=x46 & (f82_in(x42, x41)=f82_out1 ==> U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41)) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) We simplified constraint (8) using rule (VI) where we applied the induction hypothesis (f82_in(x42, x41)=f82_out1 ==> U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41)) with sigma = [ ] which results in the following new constraint: (9) (x42=x47 & x41=x46 & U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) We simplified constraint (9) using rule (IV) which results in the following new constraint: (10) (U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) For Pair F83_IN(T9, T10) -> F2_IN(s(T9), T10) the following chains were created: *We consider the chain U4^1(f82_out1, x34, x35) -> F83_IN(x34, x35), F83_IN(x36, x37) -> F2_IN(s(x36), x37) which results in the following constraint: (1) (F83_IN(x34, x35)=F83_IN(x36, x37) ==> F83_IN(x36, x37)_>=_F2_IN(s(x36), x37)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (F83_IN(x34, x35)_>=_F2_IN(s(x34), x35)) To summarize, we get the following constraints P__>=_ for the following pairs. *F2_IN(T9, T10) -> F9_IN(T9, T10) *(F2_IN(s(x6), x7)_>=_F9_IN(s(x6), x7)) *F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) *(F9_IN(x10, x11)_>=_U4^1(f82_in(x10, x11), x10, x11)) *U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) *(U4^1(f82_out1, 0, s(x40))_>=_F83_IN(0, s(x40))) *(U4^1(f82_out1, x42, x41)_>=_F83_IN(x42, x41) ==> U4^1(f82_out1, s(x42), s(x41))_>=_F83_IN(s(x42), s(x41))) *F83_IN(T9, T10) -> F2_IN(s(T9), T10) *(F83_IN(x34, x35)_>=_F2_IN(s(x34), x35)) The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. Using the following integer polynomial ordering the resulting constraints can be solved Polynomial interpretation [NONINF]: POL(0) = 0 POL(F2_IN(x_1, x_2)) = 1 - x_1 + x_2 POL(F83_IN(x_1, x_2)) = -x_1 + x_2 POL(F9_IN(x_1, x_2)) = -x_1 + x_2 POL(U2(x_1, x_2, x_3)) = 0 POL(U4^1(x_1, x_2, x_3)) = -x_1 - x_2 + x_3 POL(c) = -1 POL(f82_in(x_1, x_2)) = 0 POL(f82_out1) = 0 POL(s(x_1)) = 1 + x_1 The following pairs are in P_>: F2_IN(T9, T10) -> F9_IN(T9, T10) The following pairs are in P_bound: U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) The following rules are usable: f82_out1 -> f82_in(0, s(T19)) U2(f82_in(T24, T25), s(T24), s(T25)) -> f82_in(s(T24), s(T25)) f82_out1 -> U2(f82_out1, s(T24), s(T25)) ---------------------------------------- (22) Complex Obligation (AND) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) U4^1(f82_out1, T9, T10) -> F83_IN(T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) The TRS R consists of the following rules: f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 The set Q consists of the following terms: f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (25) TRUE ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T9, T10) -> F9_IN(T9, T10) F9_IN(T9, T10) -> U4^1(f82_in(T9, T10), T9, T10) F83_IN(T9, T10) -> F2_IN(s(T9), T10) The TRS R consists of the following rules: f82_in(0, s(T19)) -> f82_out1 f82_in(s(T24), s(T25)) -> U2(f82_in(T24, T25), s(T24), s(T25)) U2(f82_out1, s(T24), s(T25)) -> f82_out1 The set Q consists of the following terms: f82_in(0, s(x0)) f82_in(s(x0), s(x1)) U2(f82_out1, s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (28) TRUE