/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 shanoi(g,g,g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 61 ms] (2) AND (3) IRSwT (4) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (5) TRUE (6) IRSwT (7) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IRSwTTerminationDigraphProof [EQUIVALENT, 47 ms] (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (18) IRSwT (19) TempFilterProof [SOUND, 40 ms] (20) IntTRS (21) RankingReductionPairProof [EQUIVALENT, 13 ms] (22) YES ---------------------------------------- (0) Obligation: Clauses: shanoi(1, A, B, C, .(mv(A, C), [])). shanoi(N, A, B, C, M) :- ','(>(N, 1), ','(is(N1, -(N, 1)), ','(shanoi(N1, A, C, B, M1), ','(shanoi(N1, B, A, C, M2), ','(append(M1, .(mv(A, C), []), T), append(T, M2, M)))))). append([], L, L). append(.(H, L), L1, .(H, R)) :- append(L, L1, R). demo :- ','(=(Size, 15), ','(format('Towers of Hanoi for ~w elements', .(Size, [])), ','(time(X1, A), ','(nl, ','(nl, ','(shanoi(Size, a, b, c, Sol), ','(time(T, Sol), ','(format('The solution is: ~w', .(Sol, [])), ','(nl, ','(format('Solved in ~w msec.', .(T, [])), nl)))))))))). Query: shanoi(g,g,g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(shanoi (1) A B C (. (mv A C) ([])))", null ], [ "(shanoi N A B C M)", "(',' (> N (1)) (',' (is N1 (- N (1))) (',' (shanoi N1 A C B M1) (',' (shanoi N1 B A C M2) (',' (append M1 (. (mv A C) ([])) T) (append T M2 M))))))" ], [ "(append ([]) L L)", null ], [ "(append (. H L) L1 (. H R))", "(append L L1 R)" ], [ "(demo)", "(',' (= Size (15)) (',' (format ('Towers of Hanoi for ~w elements') (. Size ([]))) (',' (time X1 A) (',' (nl) (',' (nl) (',' (shanoi Size (a) (b) (c) Sol) (',' (time T Sol) (',' (format ('The solution is: ~w') (. Sol ([]))) (',' (nl) (',' (format ('Solved in ~w msec.') (. T ([]))) (nl)))))))))))" ] ] }, "graph": { "nodes": { "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T32 (1)) (',' (is X36 (- T32 (1))) (',' (shanoi X36 T33 T35 T34 X37) (',' (shanoi X36 T34 T33 T35 X38) (',' (append X37 (. (mv T33 T35) ([])) X39) (append X39 X38 T37))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33", "T34", "T35" ], "free": [ "X36", "X37", "X38", "X39" ], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1264": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi T38 T33 T35 T34 X37) (',' (shanoi T38 T34 T33 T35 X38) (',' (append X37 (. (mv T33 T35) ([])) X39) (append X39 X38 T37))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T32", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T32", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T35", "T34", "T33", "T38", "T32" ], "free": [ "X36", "X37", "X38", "X39" ], "exprvars": [ "T38", "T32" ] } }, "2350": { "goal": [ { "clause": 2, "scope": 2, "term": "(append T69 T58 T37)" }, { "clause": 3, "scope": 2, "term": "(append T69 T58 T37)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T69" ], "free": [], "exprvars": [] } }, "type": "Nodes", "2151": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T69 T58 T37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T69" ], "free": [], "exprvars": [] } }, "2071": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T45 (. (mv T33 T35) ([])) X39) (append X39 T58 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T33", "T45", "T58" ], "free": ["X39"], "exprvars": [] } }, "2148": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T45 (. (mv T33 T35) ([])) X39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T33", "T45" ], "free": ["X39"], "exprvars": [] } }, "16": { "goal": [{ "clause": 0, "scope": 1, "term": "(shanoi T1 T2 T3 T4 T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 1, "scope": 1, "term": "(shanoi T1 T2 T3 T4 T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2065": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi T38 T34 T33 T35 X38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T34", "T33", "T38" ], "free": ["X38"], "exprvars": [] } }, "2361": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2360": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T90 T91 T93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T90", "T91" ], "free": [], "exprvars": [] } }, "187": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T32", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T35", "T34", "T33", "T32" ], "free": [ "X36", "X37", "X38", "X39" ], "exprvars": ["T32"] } }, "1844": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi T38 T34 T33 T35 X38) (',' (append T45 (. (mv T33 T35) ([])) X39) (append X39 X38 T37)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T34", "T33", "T38", "T45" ], "free": [ "X38", "X39" ], "exprvars": [] } }, "2359": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi T1 T2 T3 T4 T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X36 (- T32 (1))) (',' (shanoi X36 T33 T35 T34 X37) (',' (shanoi X36 T34 T33 T35 X38) (',' (append X37 (. (mv T33 T35) ([])) X39) (append X39 X38 T37)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T32", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T35", "T34", "T33", "T32" ], "free": [ "X36", "X37", "X38", "X39" ], "exprvars": ["T32"] } }, "2358": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(shanoi T1 T2 T3 T4 T5)" }, { "clause": 1, "scope": 1, "term": "(shanoi T1 T2 T3 T4 T5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1840": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi T38 T33 T35 T34 X37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T32", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T32", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T35", "T34", "T33", "T38" ], "free": ["X37"], "exprvars": [ "T38", "T32" ] } }, "2357": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2356": { "goal": [{ "clause": 3, "scope": 2, "term": "(append T69 T58 T37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T69" ], "free": [], "exprvars": [] } }, "2355": { "goal": [{ "clause": 2, "scope": 2, "term": "(append T69 T58 T37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T58", "T69" ], "free": [], "exprvars": [] } }, "20": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 16, "label": "PARALLEL" }, { "from": 4, "to": 17, "label": "PARALLEL" }, { "from": 16, "to": 18, "label": "EVAL with clause\nshanoi(1, X14, X15, X16, .(mv(X14, X16), [])).\nand substitutionT1 -> 1,\nT2 -> T18,\nX14 -> T18,\nT3 -> T19,\nX15 -> T19,\nT4 -> T20,\nX16 -> T20,\nT5 -> .(mv(T18, T20), [])" }, { "from": 16, "to": 19, "label": "EVAL-BACKTRACK" }, { "from": 17, "to": 23, "label": "ONLY EVAL with clause\nshanoi(X31, X32, X33, X34, X35) :- ','(>(X31, 1), ','(is(X36, -(X31, 1)), ','(shanoi(X36, X32, X34, X33, X37), ','(shanoi(X36, X33, X32, X34, X38), ','(append(X37, .(mv(X32, X34), []), X39), append(X39, X38, X35)))))).\nand substitutionT1 -> T32,\nX31 -> T32,\nT2 -> T33,\nX32 -> T33,\nT3 -> T34,\nX33 -> T34,\nT4 -> T35,\nX34 -> T35,\nT5 -> T37,\nX35 -> T37,\nT36 -> T37" }, { "from": 18, "to": 20, "label": "SUCCESS" }, { "from": 23, "to": 24, "label": "IS ERROR" }, { "from": 23, "to": 124, "label": "ARITHCOMP SUCCESS" }, { "from": 23, "to": 187, "label": "ARITHCOMP FAIL" }, { "from": 124, "to": 1264, "label": "\nX36 -> T38" }, { "from": 1264, "to": 1840, "label": "SPLIT 1" }, { "from": 1264, "to": 1844, "label": "SPLIT 2\nnew knowledge:\nT38 is ground\nT33 is ground\nT35 is ground\nT34 is ground\nT45 is ground\nreplacements:X37 -> T45" }, { "from": 1840, "to": 3, "label": "INSTANCE with matching:\nT1 -> T38\nT2 -> T33\nT3 -> T35\nT4 -> T34\nT5 -> X37" }, { "from": 1844, "to": 2065, "label": "SPLIT 1" }, { "from": 1844, "to": 2071, "label": "SPLIT 2\nnew knowledge:\nT38 is ground\nT34 is ground\nT33 is ground\nT35 is ground\nT58 is ground\nreplacements:X38 -> T58" }, { "from": 2065, "to": 3, "label": "INSTANCE with matching:\nT1 -> T38\nT2 -> T34\nT3 -> T33\nT4 -> T35\nT5 -> X38" }, { "from": 2071, "to": 2148, "label": "SPLIT 1" }, { "from": 2071, "to": 2151, "label": "SPLIT 2\nnew knowledge:\nT45 is ground\nT33 is ground\nT35 is ground\nT69 is ground\nreplacements:X39 -> T69" }, { "from": 2148, "to": 2151, "label": "INSTANCE with matching:\nT69 -> T45\nT58 -> .(mv(T33, T35), [])\nT37 -> X39" }, { "from": 2151, "to": 2350, "label": "CASE" }, { "from": 2350, "to": 2355, "label": "PARALLEL" }, { "from": 2350, "to": 2356, "label": "PARALLEL" }, { "from": 2355, "to": 2357, "label": "EVAL with clause\nappend([], X74, X74).\nand substitutionT69 -> [],\nT58 -> T80,\nX74 -> T80,\nT37 -> T80" }, { "from": 2355, "to": 2358, "label": "EVAL-BACKTRACK" }, { "from": 2356, "to": 2360, "label": "EVAL with clause\nappend(.(X83, X84), X85, .(X83, X86)) :- append(X84, X85, X86).\nand substitutionX83 -> T89,\nX84 -> T90,\nT69 -> .(T89, T90),\nT58 -> T91,\nX85 -> T91,\nX86 -> T93,\nT37 -> .(T89, T93),\nT92 -> T93" }, { "from": 2356, "to": 2361, "label": "EVAL-BACKTRACK" }, { "from": 2357, "to": 2359, "label": "SUCCESS" }, { "from": 2360, "to": 2151, "label": "INSTANCE with matching:\nT69 -> T90\nT58 -> T91\nT37 -> T93" } ], "type": "Graph" } } ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Rules: f2151_in(T69, T58) -> f2350_in(T69, T58) :|: TRUE f2350_out(x, x1) -> f2151_out(x, x1) :|: TRUE f2356_in(x2, x3) -> f2361_in :|: TRUE f2356_in(.(T89, T90), T91) -> f2360_in(T90, T91) :|: TRUE f2360_out(x4, x5) -> f2356_out(.(x6, x4), x5) :|: TRUE f2361_out -> f2356_out(x7, x8) :|: TRUE f2350_in(x9, x10) -> f2355_in(x9, x10) :|: TRUE f2356_out(x11, x12) -> f2350_out(x11, x12) :|: TRUE f2355_out(x13, x14) -> f2350_out(x13, x14) :|: TRUE f2350_in(x15, x16) -> f2356_in(x15, x16) :|: TRUE f2360_in(x17, x18) -> f2151_in(x17, x18) :|: TRUE f2151_out(x19, x20) -> f2360_out(x19, x20) :|: TRUE f4_out(T1, T2, T3, T4) -> f3_out(T1, T2, T3, T4) :|: TRUE f3_in(x21, x22, x23, x24) -> f4_in(x21, x22, x23, x24) :|: TRUE f17_out(x25, x26, x27, x28) -> f4_out(x25, x26, x27, x28) :|: TRUE f4_in(x29, x30, x31, x32) -> f16_in(x29, x30, x31, x32) :|: TRUE f16_out(x33, x34, x35, x36) -> f4_out(x33, x34, x35, x36) :|: TRUE f4_in(x37, x38, x39, x40) -> f17_in(x37, x38, x39, x40) :|: TRUE f23_out(T32, T33, T35, T34) -> f17_out(T32, T33, T34, T35) :|: TRUE f17_in(x41, x42, x43, x44) -> f23_in(x41, x42, x44, x43) :|: TRUE f23_in(x45, x46, x47, x48) -> f24_in :|: TRUE f187_out(x49, x50, x51, x52) -> f23_out(x52, x51, x49, x50) :|: x52 <= 1 f24_out -> f23_out(x53, x54, x55, x56) :|: TRUE f124_out(x57, x58, x59, x60) -> f23_out(x57, x58, x59, x60) :|: x57 > 1 f23_in(x61, x62, x63, x64) -> f124_in(x61, x62, x63, x64) :|: x61 > 1 f23_in(x65, x66, x67, x68) -> f187_in(x67, x68, x66, x65) :|: x65 <= 1 f1264_out(x69, x70, x71, x72, x73) -> f124_out(x73, x70, x71, x72) :|: TRUE f124_in(x74, x75, x76, x77) -> f1264_in(x78, x75, x76, x77, x74) :|: x78 = x74 - 1 f1840_out(x79, x80, x81, x82) -> f1844_in(x79, x82, x80, x81, x83) :|: TRUE f1844_out(x84, x85, x86, x87, x88) -> f1264_out(x84, x86, x87, x85, x89) :|: TRUE f1264_in(x90, x91, x92, x93, x94) -> f1840_in(x90, x91, x92, x93) :|: TRUE f2065_out(x95, x96, x97, x98) -> f2071_in(x99, x97, x98, x100) :|: TRUE f1844_in(x101, x102, x103, x104, x105) -> f2065_in(x101, x102, x103, x104) :|: TRUE f2071_out(x106, x107, x108, x109) -> f1844_out(x110, x111, x107, x108, x106) :|: TRUE f2151_out(x112, x113) -> f2071_out(x114, x115, x116, x113) :|: TRUE f2071_in(x117, x118, x119, x120) -> f2148_in(x117, x118, x119) :|: TRUE f2148_out(x121, x122, x123) -> f2151_in(x124, x125) :|: TRUE f2148_in(x126, x127, x128) -> f2151_in(x126, .(mv(x127, x128), [])) :|: TRUE f2151_out(x129, .(mv(x130, x131), [])) -> f2148_out(x129, x130, x131) :|: TRUE Start term: f3_in(T1, T2, T3, T4) ---------------------------------------- (4) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (5) TRUE ---------------------------------------- (6) Obligation: Rules: f2151_in(T69, T58) -> f2350_in(T69, T58) :|: TRUE f2350_out(x, x1) -> f2151_out(x, x1) :|: TRUE f2356_in(x2, x3) -> f2361_in :|: TRUE f2356_in(.(T89, T90), T91) -> f2360_in(T90, T91) :|: TRUE f2360_out(x4, x5) -> f2356_out(.(x6, x4), x5) :|: TRUE f2361_out -> f2356_out(x7, x8) :|: TRUE f2148_in(T45, T33, T35) -> f2151_in(T45, .(mv(T33, T35), [])) :|: TRUE f2151_out(x9, .(mv(x10, x11), [])) -> f2148_out(x9, x10, x11) :|: TRUE f2357_in -> f2357_out :|: TRUE f23_in(x12, x13, x14, x15) -> f24_in :|: TRUE f187_out(x16, x17, x18, x19) -> f23_out(x19, x18, x16, x17) :|: x19 <= 1 f24_out -> f23_out(x20, x21, x22, x23) :|: TRUE f124_out(x24, x25, x26, x27) -> f23_out(x24, x25, x26, x27) :|: x24 > 1 f23_in(x28, x29, x30, x31) -> f124_in(x28, x29, x30, x31) :|: x28 > 1 f23_in(x32, x33, x34, x35) -> f187_in(x34, x35, x33, x32) :|: x32 <= 1 f17_out(T1, T2, T3, T4) -> f4_out(T1, T2, T3, T4) :|: TRUE f4_in(x36, x37, x38, x39) -> f16_in(x36, x37, x38, x39) :|: TRUE f16_out(x40, x41, x42, x43) -> f4_out(x40, x41, x42, x43) :|: TRUE f4_in(x44, x45, x46, x47) -> f17_in(x44, x45, x46, x47) :|: TRUE f23_out(x48, x49, x50, x51) -> f17_out(x48, x49, x51, x50) :|: TRUE f17_in(x52, x53, x54, x55) -> f23_in(x52, x53, x55, x54) :|: TRUE f1264_out(x56, x57, x58, x59, x60) -> f124_out(x60, x57, x58, x59) :|: TRUE f124_in(x61, x62, x63, x64) -> f1264_in(x65, x62, x63, x64, x61) :|: x65 = x61 - 1 f2065_in(x66, x67, x68, x69) -> f3_in(x66, x67, x68, x69) :|: TRUE f3_out(x70, x71, x72, x73) -> f2065_out(x70, x71, x72, x73) :|: TRUE f1840_out(x74, x75, x76, x77) -> f1844_in(x74, x77, x75, x76, x78) :|: TRUE f1844_out(x79, x80, x81, x82, x83) -> f1264_out(x79, x81, x82, x80, x84) :|: TRUE f1264_in(x85, x86, x87, x88, x89) -> f1840_in(x85, x86, x87, x88) :|: TRUE f2350_in(x90, x91) -> f2355_in(x90, x91) :|: TRUE f2356_out(x92, x93) -> f2350_out(x92, x93) :|: TRUE f2355_out(x94, x95) -> f2350_out(x94, x95) :|: TRUE f2350_in(x96, x97) -> f2356_in(x96, x97) :|: TRUE f2357_out -> f2355_out([], T80) :|: TRUE f2358_out -> f2355_out(x98, x99) :|: TRUE f2355_in([], x100) -> f2357_in :|: TRUE f2355_in(x101, x102) -> f2358_in :|: TRUE f2360_in(x103, x104) -> f2151_in(x103, x104) :|: TRUE f2151_out(x105, x106) -> f2360_out(x105, x106) :|: TRUE f4_out(x107, x108, x109, x110) -> f3_out(x107, x108, x109, x110) :|: TRUE f3_in(x111, x112, x113, x114) -> f4_in(x111, x112, x113, x114) :|: TRUE f2065_out(x115, x116, x117, x118) -> f2071_in(x119, x117, x118, x120) :|: TRUE f1844_in(x121, x122, x123, x124, x125) -> f2065_in(x121, x122, x123, x124) :|: TRUE f2071_out(x126, x127, x128, x129) -> f1844_out(x130, x131, x127, x128, x126) :|: TRUE f2151_out(x132, x133) -> f2071_out(x134, x135, x136, x133) :|: TRUE f2071_in(x137, x138, x139, x140) -> f2148_in(x137, x138, x139) :|: TRUE f2148_out(x141, x142, x143) -> f2151_in(x144, x145) :|: TRUE f3_out(x146, x147, x148, x149) -> f1840_out(x146, x147, x148, x149) :|: TRUE f1840_in(x150, x151, x152, x153) -> f3_in(x150, x151, x152, x153) :|: TRUE Start term: f3_in(T1, T2, T3, T4) ---------------------------------------- (7) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f23_in(x28, x29, x30, x31) -> f124_in(x28, x29, x30, x31) :|: x28 > 1 f4_in(x44, x45, x46, x47) -> f17_in(x44, x45, x46, x47) :|: TRUE f17_in(x52, x53, x54, x55) -> f23_in(x52, x53, x55, x54) :|: TRUE f124_in(x61, x62, x63, x64) -> f1264_in(x65, x62, x63, x64, x61) :|: x65 = x61 - 1 f1264_in(x85, x86, x87, x88, x89) -> f1840_in(x85, x86, x87, x88) :|: TRUE f3_in(x111, x112, x113, x114) -> f4_in(x111, x112, x113, x114) :|: TRUE f1840_in(x150, x151, x152, x153) -> f3_in(x150, x151, x152, x153) :|: TRUE ---------------------------------------- (8) Obligation: Rules: f23_in(x28, x29, x30, x31) -> f124_in(x28, x29, x30, x31) :|: x28 > 1 f4_in(x44, x45, x46, x47) -> f17_in(x44, x45, x46, x47) :|: TRUE f17_in(x52, x53, x54, x55) -> f23_in(x52, x53, x55, x54) :|: TRUE f124_in(x61, x62, x63, x64) -> f1264_in(x65, x62, x63, x64, x61) :|: x65 = x61 - 1 f1264_in(x85, x86, x87, x88, x89) -> f1840_in(x85, x86, x87, x88) :|: TRUE f3_in(x111, x112, x113, x114) -> f4_in(x111, x112, x113, x114) :|: TRUE f1840_in(x150, x151, x152, x153) -> f3_in(x150, x151, x152, x153) :|: TRUE ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f3_in(x111:0, x112:0, x113:0, x114:0) -> f3_in(x111:0 - 1, x112:0, x114:0, x113:0) :|: x111:0 > 1 ---------------------------------------- (11) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (12) Obligation: Rules: f3_in(x111:0, x112:0, x113:0, x114:0) -> f3_in(arith, x112:0, x114:0, x113:0) :|: x111:0 > 1 && arith = x111:0 - 1 ---------------------------------------- (13) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3_in(x111:0, x112:0, x113:0, x114:0) -> f3_in(arith, x112:0, x114:0, x113:0) :|: x111:0 > 1 && arith = x111:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f3_in(x111:0, x112:0, x113:0, x114:0) -> f3_in(arith, x112:0, x114:0, x113:0) :|: x111:0 > 1 && arith = x111:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f3_in(x111:0:0, x112:0:0, x113:0:0, x114:0:0) -> f3_in(x111:0:0 - 1, x112:0:0, x114:0:0, x113:0:0) :|: x111:0:0 > 1 ---------------------------------------- (17) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f3_in(x1, x2, x3, x4) -> f3_in(x1) ---------------------------------------- (18) Obligation: Rules: f3_in(x111:0:0) -> f3_in(x111:0:0 - 1) :|: x111:0:0 > 1 ---------------------------------------- (19) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (20) Obligation: Rules: f3_in(x111:0:0) -> f3_in(c) :|: c = x111:0:0 - 1 && x111:0:0 > 1 ---------------------------------------- (21) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3_in ] = f3_in_1 The following rules are decreasing: f3_in(x111:0:0) -> f3_in(c) :|: c = x111:0:0 - 1 && x111:0:0 > 1 The following rules are bounded: f3_in(x111:0:0) -> f3_in(c) :|: c = x111:0:0 - 1 && x111:0:0 > 1 ---------------------------------------- (22) YES