/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern hanoi(g,g,g,g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 15 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 22 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 45 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 33 ms] (16) IntTRS (17) PolynomialOrderProcessor [EQUIVALENT, 12 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: hanoi(1, A, B, C, .(to(A, B), Zs), Zs). hanoi(N, A, B, C, Xs, Zs) :- ','(>(N, 1), ','(is(N1, -(N, 1)), ','(hanoi(N1, A, C, B, Xs, .(to(A, B), Ys)), hanoi(N1, C, B, A, Ys, Zs)))). Query: hanoi(g,g,g,g,a,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(hanoi (1) A B C (. (to A B) Zs) Zs)", null ], [ "(hanoi N A B C Xs Zs)", "(',' (> N (1)) (',' (is N1 (- N (1))) (',' (hanoi N1 A C B Xs (. (to A B) Ys)) (hanoi N1 C B A Ys Zs))))" ] ] }, "graph": { "nodes": { "22": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T41 (1)) (',' (is X41 (- T41 (1))) (',' (hanoi X41 T42 T44 T43 T47 (. (to T42 T43) X42)) (hanoi X41 T44 T43 T42 X42 T48))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42", "T43", "T44" ], "free": [ "X41", "X42" ], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": 0, "scope": 1, "term": "(hanoi T1 T2 T3 T4 T5 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": 1, "scope": 1, "term": "(hanoi T1 T2 T3 T4 T5 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "type": "Nodes", "1712": { "goal": [{ "clause": -1, "scope": -1, "term": "(hanoi T49 T42 T44 T43 T47 (. (to T42 T43) X42))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T49", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T41", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T41", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T42", "T44", "T49", "T43" ], "free": ["X42"], "exprvars": [ "T41", "T49" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(hanoi T1 T2 T3 T4 T5 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1711": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (hanoi T49 T42 T44 T43 T47 (. (to T42 T43) X42)) (hanoi T49 T44 T43 T42 X42 T48))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T49", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T41", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T41", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T42", "T41", "T44", "T49", "T43" ], "free": [ "X41", "X42" ], "exprvars": [ "T41", "T49" ] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(hanoi T1 T2 T3 T4 T5 T6)" }, { "clause": 1, "scope": 1, "term": "(hanoi T1 T2 T3 T4 T5 T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1708": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T41", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T42", "T41", "T44", "T43" ], "free": [ "X41", "X42" ], "exprvars": ["T41"] } }, "1707": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X41 (- T41 (1))) (',' (hanoi X41 T42 T44 T43 T47 (. (to T42 T43) X42)) (hanoi X41 T44 T43 T42 X42 T48)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T41", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T42", "T41", "T44", "T43" ], "free": [ "X41", "X42" ], "exprvars": ["T41"] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1713": { "goal": [{ "clause": -1, "scope": -1, "term": "(hanoi T49 T44 T43 T42 T60 T61)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T44", "T49", "T43" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 18, "label": "PARALLEL" }, { "from": 4, "to": 19, "label": "PARALLEL" }, { "from": 18, "to": 20, "label": "EVAL with clause\nhanoi(1, X17, X18, X19, .(to(X17, X18), X20), X20).\nand substitutionT1 -> 1,\nT2 -> T23,\nX17 -> T23,\nT3 -> T24,\nX18 -> T24,\nT4 -> T25,\nX19 -> T25,\nX20 -> T26,\nT5 -> .(to(T23, T24), T26),\nT6 -> T26" }, { "from": 18, "to": 21, "label": "EVAL-BACKTRACK" }, { "from": 19, "to": 23, "label": "ONLY EVAL with clause\nhanoi(X35, X36, X37, X38, X39, X40) :- ','(>(X35, 1), ','(is(X41, -(X35, 1)), ','(hanoi(X41, X36, X38, X37, X39, .(to(X36, X37), X42)), hanoi(X41, X38, X37, X36, X42, X40)))).\nand substitutionT1 -> T41,\nX35 -> T41,\nT2 -> T42,\nX36 -> T42,\nT3 -> T43,\nX37 -> T43,\nT4 -> T44,\nX38 -> T44,\nT5 -> T47,\nX39 -> T47,\nT6 -> T48,\nX40 -> T48,\nT45 -> T47,\nT46 -> T48" }, { "from": 20, "to": 22, "label": "SUCCESS" }, { "from": 23, "to": 24, "label": "IS ERROR" }, { "from": 23, "to": 1707, "label": "ARITHCOMP SUCCESS" }, { "from": 23, "to": 1708, "label": "ARITHCOMP FAIL" }, { "from": 1707, "to": 1711, "label": "\nX41 -> T49" }, { "from": 1711, "to": 1712, "label": "SPLIT 1" }, { "from": 1711, "to": 1713, "label": "SPLIT 2\nnew knowledge:\nT49 is ground\nT42 is ground\nT44 is ground\nT43 is ground\nreplacements:X42 -> T60,\nT48 -> T61" }, { "from": 1712, "to": 1, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T42\nT3 -> T44\nT4 -> T43\nT5 -> T47\nT6 -> .(to(T42, T43), X42)" }, { "from": 1713, "to": 1, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T44\nT3 -> T43\nT4 -> T42\nT5 -> T60\nT6 -> T61" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f1_in(T1, T2, T3, T4) -> f4_in(T1, T2, T3, T4) :|: TRUE f4_out(x, x1, x2, x3) -> f1_out(x, x1, x2, x3) :|: TRUE f1713_in(T49, T44, T43, T42) -> f1_in(T49, T44, T43, T42) :|: TRUE f1_out(x4, x5, x6, x7) -> f1713_out(x4, x5, x6, x7) :|: TRUE f1712_out(x8, x9, x10, x11) -> f1713_in(x8, x10, x11, x9) :|: TRUE f1711_in(x12, x13, x14, x15, x16) -> f1712_in(x12, x13, x14, x15) :|: TRUE f1713_out(x17, x18, x19, x20) -> f1711_out(x17, x20, x18, x19, x21) :|: TRUE f4_in(x22, x23, x24, x25) -> f18_in(x22, x23, x24, x25) :|: TRUE f4_in(x26, x27, x28, x29) -> f19_in(x26, x27, x28, x29) :|: TRUE f18_out(x30, x31, x32, x33) -> f4_out(x30, x31, x32, x33) :|: TRUE f19_out(x34, x35, x36, x37) -> f4_out(x34, x35, x36, x37) :|: TRUE f1707_out(x38, x39, x40, x41) -> f23_out(x38, x39, x40, x41) :|: x38 > 1 f23_in(x42, x43, x44, x45) -> f24_in :|: TRUE f23_in(x46, x47, x48, x49) -> f1708_in(x47, x46, x48, x49) :|: x46 <= 1 f1708_out(x50, x51, x52, x53) -> f23_out(x51, x50, x52, x53) :|: x51 <= 1 f24_out -> f23_out(x54, x55, x56, x57) :|: TRUE f23_in(x58, x59, x60, x61) -> f1707_in(x58, x59, x60, x61) :|: x58 > 1 f19_in(x62, x63, x64, x65) -> f23_in(x62, x63, x65, x64) :|: TRUE f23_out(x66, x67, x68, x69) -> f19_out(x66, x67, x69, x68) :|: TRUE f1711_out(x70, x71, x72, x73, x74) -> f1707_out(x74, x71, x72, x73) :|: TRUE f1707_in(x75, x76, x77, x78) -> f1711_in(x79, x76, x77, x78, x75) :|: x79 = x75 - 1 f1712_in(x80, x81, x82, x83) -> f1_in(x80, x81, x82, x83) :|: TRUE f1_out(x84, x85, x86, x87) -> f1712_out(x84, x85, x86, x87) :|: TRUE Start term: f1_in(T1, T2, T3, T4) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f1_in(T1, T2, T3, T4) -> f4_in(T1, T2, T3, T4) :|: TRUE f1711_in(x12, x13, x14, x15, x16) -> f1712_in(x12, x13, x14, x15) :|: TRUE f4_in(x26, x27, x28, x29) -> f19_in(x26, x27, x28, x29) :|: TRUE f23_in(x58, x59, x60, x61) -> f1707_in(x58, x59, x60, x61) :|: x58 > 1 f19_in(x62, x63, x64, x65) -> f23_in(x62, x63, x65, x64) :|: TRUE f1707_in(x75, x76, x77, x78) -> f1711_in(x79, x76, x77, x78, x75) :|: x79 = x75 - 1 f1712_in(x80, x81, x82, x83) -> f1_in(x80, x81, x82, x83) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f1_in(T1, T2, T3, T4) -> f4_in(T1, T2, T3, T4) :|: TRUE f1711_in(x12, x13, x14, x15, x16) -> f1712_in(x12, x13, x14, x15) :|: TRUE f4_in(x26, x27, x28, x29) -> f19_in(x26, x27, x28, x29) :|: TRUE f23_in(x58, x59, x60, x61) -> f1707_in(x58, x59, x60, x61) :|: x58 > 1 f19_in(x62, x63, x64, x65) -> f23_in(x62, x63, x65, x64) :|: TRUE f1707_in(x75, x76, x77, x78) -> f1711_in(x79, x76, x77, x78, x75) :|: x79 = x75 - 1 f1712_in(x80, x81, x82, x83) -> f1_in(x80, x81, x82, x83) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1_in(T1:0, T2:0, T3:0, T4:0) -> f1_in(T1:0 - 1, T2:0, T4:0, T3:0) :|: T1:0 > 1 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1_in(T1:0, T2:0, T3:0, T4:0) -> f1_in(arith, T2:0, T4:0, T3:0) :|: T1:0 > 1 && arith = T1:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_in(T1:0, T2:0, T3:0, T4:0) -> f1_in(arith, T2:0, T4:0, T3:0) :|: T1:0 > 1 && arith = T1:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f1_in(T1:0, T2:0, T3:0, T4:0) -> f1_in(arith, T2:0, T4:0, T3:0) :|: T1:0 > 1 && arith = T1:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f1_in(T1:0:0, T2:0:0, T3:0:0, T4:0:0) -> f1_in(T1:0:0 - 1, T2:0:0, T4:0:0, T3:0:0) :|: T1:0:0 > 1 ---------------------------------------- (13) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1_in(x1, x2, x3, x4) -> f1_in(x1) ---------------------------------------- (14) Obligation: Rules: f1_in(T1:0:0) -> f1_in(T1:0:0 - 1) :|: T1:0:0 > 1 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f1_in(T1:0:0) -> f1_in(c) :|: c = T1:0:0 - 1 && T1:0:0 > 1 ---------------------------------------- (17) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1_in(x)] = x The following rules are decreasing: f1_in(T1:0:0) -> f1_in(c) :|: c = T1:0:0 - 1 && T1:0:0 > 1 The following rules are bounded: f1_in(T1:0:0) -> f1_in(c) :|: c = T1:0:0 - 1 && T1:0:0 > 1 ---------------------------------------- (18) YES