YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern mergesort(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 33 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) QDP (24) TransformationProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPQMonotonicMRRProof [EQUIVALENT, 92 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE ---------------------------------------- (0) Obligation: Clauses: mergesort([], []). mergesort(.(X, []), .(X, [])). mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))). split([], [], []). split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys). merge([], Xs, Xs). merge(Xs, [], Xs). merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(=(X, Y), merge(.(X, Xs), Ys, Zs)). Query: mergesort(g,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 20, "program": { "directives": [], "clauses": [ [ "(mergesort ([]) ([]))", null ], [ "(mergesort (. X ([])) (. X ([])))", null ], [ "(mergesort (. X (. Y Xs)) Ys)", "(',' (split (. X (. Y Xs)) X1s X2s) (',' (mergesort X1s Y1s) (',' (mergesort X2s Y2s) (merge Y1s Y2s Ys))))" ], [ "(split ([]) ([]) ([]))", null ], [ "(split (. X Xs) (. X Ys) Zs)", "(split Xs Zs Ys)" ], [ "(merge ([]) Xs Xs)", null ], [ "(merge Xs ([]) Xs)", null ], [ "(merge (. X Xs) (. Y Ys) (. X Zs))", "(',' (= X Y) (merge (. X Xs) Ys Zs))" ] ] }, "graph": { "nodes": { "44": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "231": { "goal": [ { "clause": 3, "scope": 4, "term": "(split T37 X61 X60)" }, { "clause": 4, "scope": 4, "term": "(split T37 X61 X60)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "235": { "goal": [{ "clause": 3, "scope": 4, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "237": { "goal": [{ "clause": 4, "scope": 4, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "160": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T16 (. T17 T18)) X22 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "161": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T21 X24) (',' (mergesort T22 X25) (merge X24 X25 T20)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": [ "X24", "X25" ], "exprvars": [] } }, "480": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T21 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X24"], "exprvars": [] } }, "481": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T22 X25) (merge T44 X25 T20))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T44" ], "free": ["X25"], "exprvars": [] } }, "241": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "244": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [ { "clause": 3, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" }, { "clause": 4, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "245": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T43 X79 X78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": [ "X78", "X79" ], "exprvars": [] } }, "202": { "goal": [{ "clause": 4, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "246": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T30 T31) X43 X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } }, "209": { "goal": [ { "clause": 3, "scope": 3, "term": "(split (. T30 T31) X43 X42)" }, { "clause": 4, "scope": 3, "term": "(split (. T30 T31) X43 X42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } }, "62": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (split (. T16 (. T17 T18)) X22 X23) (',' (mergesort X22 X24) (',' (mergesort X23 X25) (merge X24 X25 T20))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23", "X24", "X25" ], "exprvars": [] } }, "63": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "21": { "goal": [ { "clause": 0, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "22": { "goal": [{ "clause": 0, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "23": { "goal": [ { "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "490": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T22 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X25"], "exprvars": [] } }, "491": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "492": { "goal": [ { "clause": 5, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "493": { "goal": [{ "clause": 5, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "494": { "goal": [ { "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "495": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": 4, "scope": 3, "term": "(split (. T30 T31) X43 X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } }, "496": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "497": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "498": { "goal": [{ "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "499": { "goal": [{ "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "500": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "501": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "502": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "503": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (= T68 T70) (merge (. T68 T69) T71 T73))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T68", "T69", "T70", "T71" ], "free": [], "exprvars": [] } }, "504": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "505": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T75 T69) T71 T73)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T69", "T71", "T75" ], "free": [], "exprvars": [] } }, "506": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 20, "to": 21, "label": "CASE" }, { "from": 21, "to": 22, "label": "PARALLEL" }, { "from": 21, "to": 23, "label": "PARALLEL" }, { "from": 22, "to": 28, "label": "EVAL with clause\nmergesort([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 22, "to": 30, "label": "EVAL-BACKTRACK" }, { "from": 23, "to": 38, "label": "PARALLEL" }, { "from": 23, "to": 40, "label": "PARALLEL" }, { "from": 28, "to": 35, "label": "SUCCESS" }, { "from": 38, "to": 42, "label": "EVAL with clause\nmergesort(.(X5, []), .(X5, [])).\nand substitutionX5 -> T7,\nT1 -> .(T7, []),\nT2 -> .(T7, [])" }, { "from": 38, "to": 43, "label": "EVAL-BACKTRACK" }, { "from": 40, "to": 62, "label": "EVAL with clause\nmergesort(.(X18, .(X19, X20)), X21) :- ','(split(.(X18, .(X19, X20)), X22, X23), ','(mergesort(X22, X24), ','(mergesort(X23, X25), merge(X24, X25, X21)))).\nand substitutionX18 -> T16,\nX19 -> T17,\nX20 -> T18,\nT1 -> .(T16, .(T17, T18)),\nT2 -> T20,\nX21 -> T20,\nT19 -> T20" }, { "from": 40, "to": 63, "label": "EVAL-BACKTRACK" }, { "from": 42, "to": 44, "label": "SUCCESS" }, { "from": 62, "to": 160, "label": "SPLIT 1" }, { "from": 62, "to": 161, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT17 is ground\nT18 is ground\nT21 is ground\nT22 is ground\nreplacements:X22 -> T21,\nX23 -> T22" }, { "from": 160, "to": 201, "label": "CASE" }, { "from": 161, "to": 480, "label": "SPLIT 1" }, { "from": 161, "to": 481, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT44 is ground\nreplacements:X24 -> T44" }, { "from": 201, "to": 202, "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" }, { "from": 202, "to": 203, "label": "ONLY EVAL with clause\nsplit(.(X38, X39), .(X38, X40), X41) :- split(X39, X41, X40).\nand substitutionT16 -> T29,\nX38 -> T29,\nT17 -> T30,\nT18 -> T31,\nX39 -> .(T30, T31),\nX40 -> X42,\nX22 -> .(T29, X42),\nX23 -> X43,\nX41 -> X43" }, { "from": 203, "to": 209, "label": "CASE" }, { "from": 209, "to": 210, "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" }, { "from": 210, "to": 227, "label": "ONLY EVAL with clause\nsplit(.(X56, X57), .(X56, X58), X59) :- split(X57, X59, X58).\nand substitutionT30 -> T36,\nX56 -> T36,\nT31 -> T37,\nX57 -> T37,\nX58 -> X60,\nX43 -> .(T36, X60),\nX42 -> X61,\nX59 -> X61" }, { "from": 227, "to": 231, "label": "CASE" }, { "from": 231, "to": 235, "label": "PARALLEL" }, { "from": 231, "to": 237, "label": "PARALLEL" }, { "from": 235, "to": 241, "label": "EVAL with clause\nsplit([], [], []).\nand substitutionT37 -> [],\nX61 -> [],\nX60 -> []" }, { "from": 235, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 245, "label": "EVAL with clause\nsplit(.(X74, X75), .(X74, X76), X77) :- split(X75, X77, X76).\nand substitutionX74 -> T42,\nX75 -> T43,\nT37 -> .(T42, T43),\nX76 -> X78,\nX61 -> .(T42, X78),\nX60 -> X79,\nX77 -> X79" }, { "from": 237, "to": 246, "label": "EVAL-BACKTRACK" }, { "from": 241, "to": 244, "label": "SUCCESS" }, { "from": 245, "to": 227, "label": "INSTANCE with matching:\nT37 -> T43\nX61 -> X79\nX60 -> X78" }, { "from": 480, "to": 20, "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> X24" }, { "from": 481, "to": 490, "label": "SPLIT 1" }, { "from": 481, "to": 491, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT45 is ground\nreplacements:X25 -> T45" }, { "from": 490, "to": 20, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> X25" }, { "from": 491, "to": 492, "label": "CASE" }, { "from": 492, "to": 493, "label": "PARALLEL" }, { "from": 492, "to": 494, "label": "PARALLEL" }, { "from": 493, "to": 495, "label": "EVAL with clause\nmerge([], X86, X86).\nand substitutionT44 -> [],\nT45 -> T52,\nX86 -> T52,\nT20 -> T52" }, { "from": 493, "to": 496, "label": "EVAL-BACKTRACK" }, { "from": 494, "to": 498, "label": "PARALLEL" }, { "from": 494, "to": 499, "label": "PARALLEL" }, { "from": 495, "to": 497, "label": "SUCCESS" }, { "from": 498, "to": 500, "label": "EVAL with clause\nmerge(X91, [], X91).\nand substitutionT44 -> T57,\nX91 -> T57,\nT45 -> [],\nT20 -> T57" }, { "from": 498, "to": 501, "label": "EVAL-BACKTRACK" }, { "from": 499, "to": 503, "label": "EVAL with clause\nmerge(.(X102, X103), .(X104, X105), .(X102, X106)) :- ','(=(X102, X104), merge(.(X102, X103), X105, X106)).\nand substitutionX102 -> T68,\nX103 -> T69,\nT44 -> .(T68, T69),\nX104 -> T70,\nX105 -> T71,\nT45 -> .(T70, T71),\nX106 -> T73,\nT20 -> .(T68, T73),\nT72 -> T73" }, { "from": 499, "to": 504, "label": "EVAL-BACKTRACK" }, { "from": 500, "to": 502, "label": "SUCCESS" }, { "from": 503, "to": 505, "label": "UNIFY CASE with substitutionT68 -> T75,\nT70 -> T75" }, { "from": 503, "to": 506, "label": "UNIFY-BACKTRACK" }, { "from": 505, "to": 491, "label": "INSTANCE with matching:\nT44 -> .(T75, T69)\nT45 -> T71\nT20 -> T73" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) 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: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) ---------------------------------------- (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: F20_IN(.(T16, .(T17, T18))) -> U1^1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) F20_IN(.(T16, .(T17, T18))) -> F62_IN(T16, T17, T18) F227_IN(.(T42, T43)) -> U2^1(f227_in(T43), .(T42, T43)) F227_IN(.(T42, T43)) -> F227_IN(T43) F491_IN(.(T75, T69), .(T75, T71)) -> U3^1(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) F491_IN(.(T75, T69), .(T75, T71)) -> F491_IN(.(T75, T69), T71) F160_IN(T29, T36, T37) -> U4^1(f227_in(T37), T29, T36, T37) F160_IN(T29, T36, T37) -> F227_IN(T37) F62_IN(T16, T17, T18) -> U5^1(f160_in(T16, T17, T18), T16, T17, T18) F62_IN(T16, T17, T18) -> F160_IN(T16, T17, T18) U5^1(f160_out1(T21, T22), T16, T17, T18) -> U6^1(f161_in(T21, T22), T16, T17, T18, T21, T22) U5^1(f160_out1(T21, T22), T16, T17, T18) -> F161_IN(T21, T22) F161_IN(T21, T22) -> U7^1(f20_in(T21), T21, T22) F161_IN(T21, T22) -> F20_IN(T21) U7^1(f20_out1(T44), T21, T22) -> U8^1(f481_in(T22, T44), T21, T22, T44) U7^1(f20_out1(T44), T21, T22) -> F481_IN(T22, T44) F481_IN(T22, T44) -> U9^1(f20_in(T22), T22, T44) F481_IN(T22, T44) -> F20_IN(T22) U9^1(f20_out1(T45), T22, T44) -> U10^1(f491_in(T44, T45), T22, T44, T45) U9^1(f20_out1(T45), T22, T44) -> F491_IN(T44, T45) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 11 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F491_IN(.(T75, T69), .(T75, T71)) -> F491_IN(.(T75, T69), T71) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) 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: F491_IN(.(T75, T69), .(T75, T71)) -> F491_IN(.(T75, T69), T71) R is empty. The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) 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]. f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: F491_IN(.(T75, T69), .(T75, T71)) -> F491_IN(.(T75, T69), T71) 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: *F491_IN(.(T75, T69), .(T75, T71)) -> F491_IN(.(T75, T69), T71) 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: F227_IN(.(T42, T43)) -> F227_IN(T43) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) 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: F227_IN(.(T42, T43)) -> F227_IN(T43) R is empty. The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) 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]. f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: F227_IN(.(T42, T43)) -> F227_IN(T43) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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: *F227_IN(.(T42, T43)) -> F227_IN(T43) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: F20_IN(.(T16, .(T17, T18))) -> F62_IN(T16, T17, T18) F62_IN(T16, T17, T18) -> U5^1(f160_in(T16, T17, T18), T16, T17, T18) U5^1(f160_out1(T21, T22), T16, T17, T18) -> F161_IN(T21, T22) F161_IN(T21, T22) -> U7^1(f20_in(T21), T21, T22) U7^1(f20_out1(T44), T21, T22) -> F481_IN(T22, T44) F481_IN(T22, T44) -> F20_IN(T22) F161_IN(T21, T22) -> F20_IN(T21) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule F62_IN(T16, T17, T18) -> U5^1(f160_in(T16, T17, T18), T16, T17, T18) at position [0] we obtained the following new rules [LPAR04]: (F62_IN(T16, T17, T18) -> U5^1(U4(f227_in(T18), T16, T17, T18), T16, T17, T18),F62_IN(T16, T17, T18) -> U5^1(U4(f227_in(T18), T16, T17, T18), T16, T17, T18)) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: F20_IN(.(T16, .(T17, T18))) -> F62_IN(T16, T17, T18) U5^1(f160_out1(T21, T22), T16, T17, T18) -> F161_IN(T21, T22) F161_IN(T21, T22) -> U7^1(f20_in(T21), T21, T22) U7^1(f20_out1(T44), T21, T22) -> F481_IN(T22, T44) F481_IN(T22, T44) -> F20_IN(T22) F161_IN(T21, T22) -> F20_IN(T21) F62_IN(T16, T17, T18) -> U5^1(U4(f227_in(T18), T16, T17, T18), T16, T17, T18) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: F20_IN(.(T16, .(T17, T18))) -> F62_IN(T16, T17, T18) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + 2*x_2 POL(F161_IN(x_1, x_2)) = x_1 + x_2 POL(F20_IN(x_1)) = x_1 POL(F481_IN(x_1, x_2)) = x_1 POL(F62_IN(x_1, x_2, x_3)) = 2 + 2*x_3 POL(U1(x_1, x_2)) = 0 POL(U10(x_1, x_2, x_3, x_4)) = 0 POL(U2(x_1, x_2)) = 2*x_1 POL(U3(x_1, x_2, x_3)) = 0 POL(U4(x_1, x_2, x_3, x_4)) = 2*x_1 POL(U5(x_1, x_2, x_3, x_4)) = 0 POL(U5^1(x_1, x_2, x_3, x_4)) = x_1 POL(U6(x_1, x_2, x_3, x_4, x_5, x_6)) = 0 POL(U7(x_1, x_2, x_3)) = 0 POL(U7^1(x_1, x_2, x_3)) = x_2 + x_3 POL(U8(x_1, x_2, x_3, x_4)) = 0 POL(U9(x_1, x_2, x_3)) = 0 POL([]) = 0 POL(f160_in(x_1, x_2, x_3)) = 2 + 2*x_3 POL(f160_out1(x_1, x_2)) = x_1 + x_2 POL(f161_in(x_1, x_2)) = 0 POL(f161_out1(x_1, x_2, x_3)) = 0 POL(f20_in(x_1)) = 0 POL(f20_out1(x_1)) = 0 POL(f227_in(x_1)) = 1 + x_1 POL(f227_out1(x_1, x_2)) = 1 + x_1 + x_2 POL(f481_in(x_1, x_2)) = 0 POL(f481_out1(x_1, x_2)) = 0 POL(f491_in(x_1, x_2)) = 2 POL(f491_out1(x_1)) = 0 POL(f62_in(x_1, x_2, x_3)) = 0 POL(f62_out1(x_1, x_2, x_3, x_4, x_5)) = 0 ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U5^1(f160_out1(T21, T22), T16, T17, T18) -> F161_IN(T21, T22) F161_IN(T21, T22) -> U7^1(f20_in(T21), T21, T22) U7^1(f20_out1(T44), T21, T22) -> F481_IN(T22, T44) F481_IN(T22, T44) -> F20_IN(T22) F161_IN(T21, T22) -> F20_IN(T21) F62_IN(T16, T17, T18) -> U5^1(U4(f227_in(T18), T16, T17, T18), T16, T17, T18) The TRS R consists of the following rules: f20_in([]) -> f20_out1([]) f20_in(.(T7, [])) -> f20_out1(.(T7, [])) f20_in(.(T16, .(T17, T18))) -> U1(f62_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f62_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f20_out1(T20) f227_in([]) -> f227_out1([], []) f227_in(.(T42, T43)) -> U2(f227_in(T43), .(T42, T43)) U2(f227_out1(X79, X78), .(T42, T43)) -> f227_out1(.(T42, X78), X79) f491_in([], T52) -> f491_out1(T52) f491_in(T57, []) -> f491_out1(T57) f491_in(.(T75, T69), .(T75, T71)) -> U3(f491_in(.(T75, T69), T71), .(T75, T69), .(T75, T71)) U3(f491_out1(T73), .(T75, T69), .(T75, T71)) -> f491_out1(.(T75, T73)) f160_in(T29, T36, T37) -> U4(f227_in(T37), T29, T36, T37) U4(f227_out1(X61, X60), T29, T36, T37) -> f160_out1(.(T29, X61), .(T36, X60)) f62_in(T16, T17, T18) -> U5(f160_in(T16, T17, T18), T16, T17, T18) U5(f160_out1(T21, T22), T16, T17, T18) -> U6(f161_in(T21, T22), T16, T17, T18, T21, T22) U6(f161_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f62_out1(T21, T22, X24, X25, T20) f161_in(T21, T22) -> U7(f20_in(T21), T21, T22) U7(f20_out1(T44), T21, T22) -> U8(f481_in(T22, T44), T21, T22, T44) U8(f481_out1(X25, T20), T21, T22, T44) -> f161_out1(T44, X25, T20) f481_in(T22, T44) -> U9(f20_in(T22), T22, T44) U9(f20_out1(T45), T22, T44) -> U10(f491_in(T44, T45), T22, T44, T45) U10(f491_out1(T20), T22, T44, T45) -> f481_out1(T45, T20) The set Q consists of the following terms: f20_in([]) f20_in(.(x0, [])) f20_in(.(x0, .(x1, x2))) U1(f62_out1(x0, x1, x2, x3, x4), .(x5, .(x6, x7))) f227_in([]) f227_in(.(x0, x1)) U2(f227_out1(x0, x1), .(x2, x3)) f491_in([], x0) f491_in(x0, []) f491_in(.(x0, x1), .(x0, x2)) U3(f491_out1(x0), .(x1, x2), .(x1, x3)) f160_in(x0, x1, x2) U4(f227_out1(x0, x1), x2, x3, x4) f62_in(x0, x1, x2) U5(f160_out1(x0, x1), x2, x3, x4) U6(f161_out1(x0, x1, x2), x3, x4, x5, x6, x7) f161_in(x0, x1) U7(f20_out1(x0), x1, x2) U8(f481_out1(x0, x1), x2, x3, x4) f481_in(x0, x1) U9(f20_out1(x0), x1, x2) U10(f491_out1(x0), x1, x2, x3) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 6 less nodes. ---------------------------------------- (29) TRUE