/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 t_phi(g,a,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 42 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 33 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 34 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 3 ms] (14) IRSwT (15) TempFilterProof [SOUND, 37 ms] (16) IntTRS (17) RankingReductionPairProof [EQUIVALENT, 19 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: totient_phi(1, 1) :- !. totient_phi(M, Phi) :- t_phi(M, Phi, 1, 0). t_phi(M, Phi, M, Phi) :- !. t_phi(M, Phi, K, C) :- ','(<(K, M), ','(coprime(K, M), ','(!, ','(is(C1, +(C, 1)), ','(is(K1, +(K, 1)), t_phi(M, Phi, K1, C1)))))). t_phi(M, Phi, K, C) :- ','(<(K, M), ','(is(K1, +(K, 1)), t_phi(M, Phi, K1, C))). coprime(X, Y) :- gcd(X, Y, 1). gcd(X, 0, X) :- >(X, 0). gcd(X, Y, G) :- ','(>(Y, 0), ','(is(Z, mod(X, Y)), gcd(Y, Z, G))). Query: t_phi(g,a,g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(totient_phi (1) (1))", "(!)" ], [ "(totient_phi M Phi)", "(t_phi M Phi (1) (0))" ], [ "(t_phi M Phi M Phi)", "(!)" ], [ "(t_phi M Phi K C)", "(',' (< K M) (',' (coprime K M) (',' (!) (',' (is C1 (+ C (1))) (',' (is K1 (+ K (1))) (t_phi M Phi K1 C1))))))" ], [ "(t_phi M Phi K C)", "(',' (< K M) (',' (is K1 (+ K (1))) (t_phi M Phi K1 C)))" ], [ "(coprime X Y)", "(gcd X Y (1))" ], [ "(gcd X (0) X)", "(> X (0))" ], [ "(gcd X Y G)", "(',' (> Y (0)) (',' (is Z (mod X Y)) (gcd Y Z G)))" ] ] }, "graph": { "nodes": { "3640": { "goal": [{ "clause": -1, "scope": -1, "term": "(> (1) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "type": "Nodes", "3638": { "goal": [{ "clause": 6, "scope": 3, "term": "(gcd T43 T44 (1))" }], "kb": { "nonunifying": [[ "(t_phi T44 T2 T43 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T32", "T43", "T44" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "3639": { "goal": [{ "clause": 7, "scope": 3, "term": "(gcd T43 T44 (1))" }], "kb": { "nonunifying": [[ "(t_phi T44 T2 T43 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T32", "T43", "T44" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "3795": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X76 (+ T72 (1))) (t_phi T70 T74 X76 T73))" }], "kb": { "nonunifying": [[ "(t_phi T70 T2 T72 T73)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T72", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T70", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T70", "T73", "T72" ], "free": [ "X5", "X6", "X76" ], "exprvars": [ "T70", "T72" ] } }, "3796": { "goal": [], "kb": { "nonunifying": [[ "(t_phi T70 T2 T72 T73)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T72", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T70", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T70", "T73", "T72" ], "free": [ "X5", "X6", "X76" ], "exprvars": [ "T70", "T72" ] } }, "3797": { "goal": [{ "clause": -1, "scope": -1, "term": "(t_phi T70 T74 T75 T73)" }], "kb": { "nonunifying": [[ "(t_phi T70 T2 T72 T73)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T75", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T72", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T72", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T70", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T70", "T75", "T73", "T72" ], "free": [ "X5", "X6", "X76" ], "exprvars": [ "T70", "T75", "T72" ] } }, "10": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 3, "scope": 1, "term": "(t_phi T9 T2 T9 T10)" }, { "clause": 4, "scope": 1, "term": "(t_phi T9 T2 T9 T10)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "3637": { "goal": [ { "clause": 6, "scope": 3, "term": "(gcd T43 T44 (1))" }, { "clause": 7, "scope": 3, "term": "(gcd T43 T44 (1))" } ], "kb": { "nonunifying": [[ "(t_phi T44 T2 T43 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T32", "T43", "T44" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "12": { "goal": [ { "clause": 3, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" }, { "clause": 4, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" } ], "kb": { "nonunifying": [[ "(t_phi T1 T2 T3 T4)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T3" ], "free": [ "X5", "X6" ], "exprvars": [] } }, "3790": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T72 T70) (',' (is X76 (+ T72 (1))) (t_phi T70 T74 X76 T73)))" }], "kb": { "nonunifying": [[ "(t_phi T70 T2 T72 T73)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T70", "T72", "T73" ], "free": [ "X5", "X6", "X76" ], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3791": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 3, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" }], "kb": { "nonunifying": [[ "(t_phi T1 T2 T3 T4)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T3" ], "free": [ "X5", "X6" ], "exprvars": [] } }, "18": { "goal": [{ "clause": 4, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" }], "kb": { "nonunifying": [[ "(t_phi T1 T2 T3 T4)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T3" ], "free": [ "X5", "X6" ], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T31 T29) (',' (coprime T31 T29) (',' (!_1) (',' (is X31 (+ T32 (1))) (',' (is X32 (+ T31 (1))) (t_phi T29 T33 X32 X31))))))" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T29", "T31", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [] } }, "3406": { "goal": [], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [ "T31", "T29" ] } }, "3405": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (coprime T31 T29) (',' (!_1) (',' (is X31 (+ T32 (1))) (',' (is X32 (+ T31 (1))) (t_phi T29 T33 X32 X31)))))" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [ "T31", "T29" ] } }, "3503": { "goal": [{ "clause": -1, "scope": -1, "term": "(gcd T43 T44 (1))" }], "kb": { "nonunifying": [[ "(t_phi T44 T2 T43 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T32", "T43", "T44" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(t_phi T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T3" ], "free": [], "exprvars": [] } }, "3502": { "goal": [{ "clause": 5, "scope": 2, "term": "(coprime T31 T29)" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29" ] } }, "4": { "goal": [ { "clause": 2, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" }, { "clause": 3, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" }, { "clause": 4, "scope": 1, "term": "(t_phi T1 T2 T3 T4)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T3" ], "free": [], "exprvars": [] } }, "3501": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (is X31 (+ T32 (1))) (',' (is X32 (+ T31 (1))) (t_phi T29 T33 X32 X31))))" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [] } }, "3500": { "goal": [{ "clause": -1, "scope": -1, "term": "(coprime T31 T29)" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6" ], "exprvars": [ "T31", "T29" ] } }, "3641": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T31", "T29", "T44", "T43" ] } }, "3785": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X31 (+ T32 (1))) (',' (is X32 (+ T31 (1))) (t_phi T29 T33 X32 X31)))" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [] } }, "3786": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3787": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X32 (+ T31 (1))) (t_phi T29 T33 X32 T57))" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T57", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T32", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T31", "T57", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [ "T57", "T32" ] } }, "3788": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3789": { "goal": [{ "clause": -1, "scope": -1, "term": "(t_phi T29 T33 T58 T57)" }], "kb": { "nonunifying": [[ "(t_phi T29 T2 T31 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T57", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T32", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T58", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" } ] }, "ground": [ "T31", "T58", "T57", "T29", "T32" ], "free": [ "X5", "X6", "X31", "X32" ], "exprvars": [ "T31", "T58", "T57", "T32" ] } }, "20": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3769": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T56 (0)) (',' (is X60 (mod T55 T56)) (gcd T56 X60 (1))))" }], "kb": { "nonunifying": [[ "(t_phi T56 T2 T55 T32)", "(t_phi X5 X6 X5 X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T29", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T32", "T55", "T56" ], "free": [ "X5", "X6", "X60" ], "exprvars": [ "T31", "T29", "T56", "T44", "T55", "T43" ] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 10, "label": "EVAL with clause\nt_phi(X5, X6, X5, X6) :- !_1.\nand substitutionT1 -> T9,\nX5 -> T9,\nT2 -> T10,\nX6 -> T10,\nT3 -> T9,\nT4 -> T10" }, { "from": 4, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 15, "label": "CUT" }, { "from": 12, "to": 17, "label": "PARALLEL" }, { "from": 12, "to": 18, "label": "PARALLEL" }, { "from": 15, "to": 16, "label": "SUCCESS" }, { "from": 17, "to": 19, "label": "ONLY EVAL with clause\nt_phi(X27, X28, X29, X30) :- ','(<(X29, X27), ','(coprime(X29, X27), ','(!_1, ','(is(X31, +(X30, 1)), ','(is(X32, +(X29, 1)), t_phi(X27, X28, X32, X31)))))).\nand substitutionT1 -> T29,\nX27 -> T29,\nT2 -> T33,\nX28 -> T33,\nT3 -> T31,\nX29 -> T31,\nT4 -> T32,\nX30 -> T32,\nT30 -> T33" }, { "from": 18, "to": 3790, "label": "ONLY EVAL with clause\nt_phi(X72, X73, X74, X75) :- ','(<(X74, X72), ','(is(X76, +(X74, 1)), t_phi(X72, X73, X76, X75))).\nand substitutionT1 -> T70,\nX72 -> T70,\nT2 -> T74,\nX73 -> T74,\nT3 -> T72,\nX74 -> T72,\nT4 -> T73,\nX75 -> T73,\nT71 -> T74" }, { "from": 19, "to": 20, "label": "IS ERROR" }, { "from": 19, "to": 3405, "label": "ARITHCOMP SUCCESS" }, { "from": 19, "to": 3406, "label": "ARITHCOMP FAIL" }, { "from": 3405, "to": 3500, "label": "SPLIT 1" }, { "from": 3405, "to": 3501, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT29 is ground" }, { "from": 3500, "to": 3502, "label": "CASE" }, { "from": 3501, "to": 3785, "label": "CUT" }, { "from": 3502, "to": 3503, "label": "ONLY EVAL with clause\ncoprime(X42, X43) :- gcd(X42, X43, 1).\nand substitutionT31 -> T43,\nX42 -> T43,\nT29 -> T44,\nX43 -> T44" }, { "from": 3503, "to": 3637, "label": "CASE" }, { "from": 3637, "to": 3638, "label": "PARALLEL" }, { "from": 3637, "to": 3639, "label": "PARALLEL" }, { "from": 3638, "to": 3640, "label": "EVAL with clause\ngcd(X49, 0, X49) :- >(X49, 0).\nand substitutionT43 -> 1,\nX49 -> 1,\nT44 -> 0,\nT50 -> 1" }, { "from": 3638, "to": 3641, "label": "EVAL-BACKTRACK" }, { "from": 3639, "to": 3769, "label": "ONLY EVAL with clause\ngcd(X57, X58, X59) :- ','(>(X58, 0), ','(is(X60, mod(X57, X58)), gcd(X58, X60, X59))).\nand substitutionT43 -> T55,\nX57 -> T55,\nT44 -> T56,\nX58 -> T56,\nX59 -> 1" }, { "from": 3785, "to": 3786, "label": "IS ERROR" }, { "from": 3785, "to": 3787, "label": "\nX31 -> T57" }, { "from": 3787, "to": 3788, "label": "IS ERROR" }, { "from": 3787, "to": 3789, "label": "\nX32 -> T58" }, { "from": 3789, "to": 3, "label": "INSTANCE with matching:\nT1 -> T29\nT2 -> T33\nT3 -> T58\nT4 -> T57" }, { "from": 3790, "to": 3791, "label": "IS ERROR" }, { "from": 3790, "to": 3795, "label": "ARITHCOMP SUCCESS" }, { "from": 3790, "to": 3796, "label": "ARITHCOMP FAIL" }, { "from": 3795, "to": 3797, "label": "\nX76 -> T75" }, { "from": 3797, "to": 3, "label": "INSTANCE with matching:\nT1 -> T70\nT2 -> T74\nT3 -> T75\nT4 -> T73" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f3785_in(T32, T31, T29) -> f3787_in(T31, T29, T57, T32) :|: T57 = T32 + 1 f3785_in(x, x1, x2) -> f3786_in :|: TRUE f3786_out -> f3785_out(x3, x4, x5) :|: TRUE f3787_out(x6, x7, x8, x9) -> f3785_out(x9, x6, x7) :|: TRUE f3787_in(x10, x11, x12, x13) -> f3789_in(x11, x14, x12, x10, x13) :|: x14 = x10 + 1 f3787_in(x15, x16, x17, x18) -> f3788_in :|: TRUE f3788_out -> f3787_out(x19, x20, x21, x22) :|: TRUE f3789_out(x23, x24, x25, x26, x27) -> f3787_out(x26, x23, x25, x27) :|: TRUE f3795_in(T72, T70, T73) -> f3797_in(T70, T75, T73, T72) :|: T75 = T72 + 1 f3797_out(x28, x29, x30, x31) -> f3795_out(x31, x28, x30) :|: TRUE f3638_in(1, 0, x32) -> f3640_in :|: TRUE f3638_in(x33, x34, x35) -> f3641_in :|: TRUE f3640_out -> f3638_out(1, 0, x36) :|: TRUE f3641_out -> f3638_out(x37, x38, x39) :|: TRUE f3_out(x40, x41, x42) -> f3789_out(x40, x41, x42, x43, x44) :|: TRUE f3789_in(x45, x46, x47, x48, x49) -> f3_in(x45, x46, x47) :|: TRUE f3790_out(x50, x51, x52) -> f18_out(x51, x50, x52) :|: TRUE f18_in(x53, x54, x55) -> f3790_in(x54, x53, x55) :|: TRUE f12_in(T1, T3, T4) -> f17_in(T1, T3, T4) :|: TRUE f18_out(x56, x57, x58) -> f12_out(x56, x57, x58) :|: TRUE f12_in(x59, x60, x61) -> f18_in(x59, x60, x61) :|: TRUE f17_out(x62, x63, x64) -> f12_out(x62, x63, x64) :|: TRUE f3639_in(x65, x66, x67) -> f3769_in(x66, x65, x67) :|: TRUE f3769_out(x68, x69, x70) -> f3639_out(x69, x68, x70) :|: TRUE f19_out(x71, x72, x73) -> f17_out(x72, x71, x73) :|: TRUE f17_in(x74, x75, x76) -> f19_in(x75, x74, x76) :|: TRUE f3501_out(x77, x78, x79) -> f3405_out(x78, x79, x77) :|: TRUE f3500_out(x80, x81, x82) -> f3501_in(x82, x80, x81) :|: TRUE f3405_in(x83, x84, x85) -> f3500_in(x83, x84, x85) :|: TRUE f4_out(x86, x87, x88) -> f3_out(x86, x87, x88) :|: TRUE f3_in(x89, x90, x91) -> f4_in(x89, x90, x91) :|: TRUE f3797_in(x92, x93, x94, x95) -> f3_in(x92, x93, x94) :|: TRUE f3_out(x96, x97, x98) -> f3797_out(x96, x97, x98, x99) :|: TRUE f4_in(T9, T9, T10) -> f10_in(T9, T10) :|: TRUE f10_out(x100, x101) -> f4_out(x100, x100, x101) :|: TRUE f4_in(x102, x103, x104) -> f12_in(x102, x103, x104) :|: TRUE f12_out(x105, x106, x107) -> f4_out(x105, x106, x107) :|: TRUE f20_out -> f19_out(x108, x109, x110) :|: TRUE f19_in(x111, x112, x113) -> f20_in :|: TRUE f3405_out(x114, x115, x116) -> f19_out(x114, x115, x116) :|: x114 < x115 f3406_out(x117, x118, x119) -> f19_out(x117, x118, x119) :|: x117 >= x118 f19_in(x120, x121, x122) -> f3406_in(x120, x121, x122) :|: x120 >= x121 f19_in(x123, x124, x125) -> f3405_in(x123, x124, x125) :|: x123 < x124 f3785_out(x126, x127, x128) -> f3501_out(x126, x127, x128) :|: TRUE f3501_in(x129, x130, x131) -> f3785_in(x129, x130, x131) :|: TRUE f3790_in(x132, x133, x134) -> f3796_in(x133, x134, x132) :|: x132 >= x133 f3790_in(x135, x136, x137) -> f3795_in(x135, x136, x137) :|: x135 < x136 f3796_out(x138, x139, x140) -> f3790_out(x140, x138, x139) :|: x140 >= x138 f3791_out -> f3790_out(x141, x142, x143) :|: TRUE f3790_in(x144, x145, x146) -> f3791_in :|: TRUE f3795_out(x147, x148, x149) -> f3790_out(x147, x148, x149) :|: x147 < x148 f3502_in(x150, x151, x152) -> f3503_in(x150, x151, x152) :|: TRUE f3503_out(x153, x154, x155) -> f3502_out(x153, x154, x155) :|: TRUE f3502_out(x156, x157, x158) -> f3500_out(x156, x157, x158) :|: TRUE f3500_in(x159, x160, x161) -> f3502_in(x159, x160, x161) :|: TRUE f3503_in(x162, x163, x164) -> f3637_in(x162, x163, x164) :|: TRUE f3637_out(x165, x166, x167) -> f3503_out(x165, x166, x167) :|: TRUE f3637_in(x168, x169, x170) -> f3639_in(x168, x169, x170) :|: TRUE f3639_out(x171, x172, x173) -> f3637_out(x171, x172, x173) :|: TRUE f3638_out(x174, x175, x176) -> f3637_out(x174, x175, x176) :|: TRUE f3637_in(x177, x178, x179) -> f3638_in(x177, x178, x179) :|: TRUE Start term: f3_in(T1, T3, T4) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f3795_in(T72, T70, T73) -> f3797_in(T70, T75, T73, T72) :|: T75 = T72 + 1 f18_in(x53, x54, x55) -> f3790_in(x54, x53, x55) :|: TRUE f12_in(x59, x60, x61) -> f18_in(x59, x60, x61) :|: TRUE f3_in(x89, x90, x91) -> f4_in(x89, x90, x91) :|: TRUE f3797_in(x92, x93, x94, x95) -> f3_in(x92, x93, x94) :|: TRUE f4_in(x102, x103, x104) -> f12_in(x102, x103, x104) :|: TRUE f3790_in(x135, x136, x137) -> f3795_in(x135, x136, x137) :|: x135 < x136 ---------------------------------------- (4) Obligation: Rules: f3795_in(T72, T70, T73) -> f3797_in(T70, T75, T73, T72) :|: T75 = T72 + 1 f18_in(x53, x54, x55) -> f3790_in(x54, x53, x55) :|: TRUE f12_in(x59, x60, x61) -> f18_in(x59, x60, x61) :|: TRUE f3_in(x89, x90, x91) -> f4_in(x89, x90, x91) :|: TRUE f3797_in(x92, x93, x94, x95) -> f3_in(x92, x93, x94) :|: TRUE f4_in(x102, x103, x104) -> f12_in(x102, x103, x104) :|: TRUE f3790_in(x135, x136, x137) -> f3795_in(x135, x136, x137) :|: x135 < x136 ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f3795_in(T72:0, T70:0, T73:0) -> f3795_in(T72:0 + 1, T70:0, T73:0) :|: T72:0 + 1 < T70:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f3795_in(T72:0, T70:0, T73:0) -> f3795_in(arith, T70:0, T73:0) :|: T72:0 + 1 < T70:0 && arith = T72:0 + 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3795_in(T72:0, T70:0, T73:0) -> f3795_in(arith, T70:0, T73:0) :|: T72:0 + 1 < T70:0 && arith = T72:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f3795_in(T72:0, T70:0, T73:0) -> f3795_in(arith, T70:0, T73:0) :|: T72:0 + 1 < T70:0 && arith = T72:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f3795_in(T72:0:0, T70:0:0, T73:0:0) -> f3795_in(T72:0:0 + 1, T70:0:0, T73:0:0) :|: T72:0:0 + 1 < T70:0:0 ---------------------------------------- (13) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f3795_in(x1, x2, x3) -> f3795_in(x1, x2) ---------------------------------------- (14) Obligation: Rules: f3795_in(T72:0:0, T70:0:0) -> f3795_in(T72:0:0 + 1, T70:0:0) :|: T72:0:0 + 1 < T70:0:0 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3795_in(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f3795_in(T72:0:0, T70:0:0) -> f3795_in(c, T70:0:0) :|: c = T72:0:0 + 1 && T72:0:0 + 1 < T70:0:0 ---------------------------------------- (17) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3795_in ] = -1*f3795_in_1 + f3795_in_2 The following rules are decreasing: f3795_in(T72:0:0, T70:0:0) -> f3795_in(c, T70:0:0) :|: c = T72:0:0 + 1 && T72:0:0 + 1 < T70:0:0 The following rules are bounded: f3795_in(T72:0:0, T70:0:0) -> f3795_in(c, T70:0:0) :|: c = T72:0:0 + 1 && T72:0:0 + 1 < T70:0:0 ---------------------------------------- (18) YES