YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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, 48 ms] (2) AND (3) IRSwT (4) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (5) TRUE (6) IRSwT (7) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IntTRSCompressionProof [EQUIVALENT, 53 ms] (10) IRSwT (11) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (14) IRSwT (15) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (16) IRSwT (17) TempFilterProof [SOUND, 2 ms] (18) IRSwT (19) IRSwTToQDPProof [SOUND, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES ---------------------------------------- (0) Obligation: Clauses: shanoi(s(0), A, B, C, .(mv(A, C), [])). shanoi(s(s(X)), A, B, C, M) :- ','(eq(N1, s(X)), ','(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). eq(X, X). 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 (s (0)) A B C (. (mv A C) ([])))", null ], [ "(shanoi (s (s X)) A B C M)", "(',' (eq N1 (s X)) (',' (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)" ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "25": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq X35 (s T31)) (',' (shanoi X35 T32 T34 T33 X36) (',' (shanoi X35 T33 T32 T34 X37) (',' (append X36 (. (mv T32 T34) ([])) X38) (append X38 X37 T36)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33", "T34" ], "free": [ "X35", "X36", "X37", "X38" ], "exprvars": [] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "372": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi (s T54) T33 T32 T34 X37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33", "T34", "T54" ], "free": ["X37"], "exprvars": [] } }, "394": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T106 T107 T109)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T106", "T107" ], "free": [], "exprvars": [] } }, "373": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T61 (. (mv T32 T34) ([])) X38) (append X38 T74 T36))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T34", "T61", "T74" ], "free": ["X38"], "exprvars": [] } }, "395": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "376": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T61 (. (mv T32 T34) ([])) X38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T34", "T61" ], "free": ["X38"], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T85 T74 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T85" ], "free": [], "exprvars": [] } }, "378": { "goal": [ { "clause": 2, "scope": 3, "term": "(append T85 T74 T36)" }, { "clause": 3, "scope": 3, "term": "(append T85 T74 T36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T85" ], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": 2, "scope": 3, "term": "(append T85 T74 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T85" ], "free": [], "exprvars": [] } }, "12": { "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": [] } }, "14": { "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": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "380": { "goal": [{ "clause": 3, "scope": 3, "term": "(append T85 T74 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T85" ], "free": [], "exprvars": [] } }, "381": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "382": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "383": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "362": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (eq X35 (s T31)) (',' (shanoi X35 T32 T34 T33 X36) (',' (shanoi X35 T33 T32 T34 X37) (',' (append X36 (. (mv T32 T34) ([])) X38) (append X38 X37 T36)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33", "T34" ], "free": [ "X35", "X36", "X37", "X38" ], "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": [] } }, "366": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi (s T54) T32 T34 T33 X36) (',' (shanoi (s T54) T33 T32 T34 X37) (',' (append X36 (. (mv T32 T34) ([])) X38) (append X38 X37 T36))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33", "T34", "T54" ], "free": [ "X36", "X37", "X38" ], "exprvars": [] } }, "368": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi (s T54) T32 T34 T33 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33", "T34", "T54" ], "free": ["X36"], "exprvars": [] } }, "6": { "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": [] } }, "369": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi (s T54) T33 T32 T34 X37) (',' (append T61 (. (mv T32 T34) ([])) X38) (append X38 X37 T36)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33", "T34", "T54", "T61" ], "free": [ "X37", "X38" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 12, "label": "PARALLEL" }, { "from": 6, "to": 14, "label": "PARALLEL" }, { "from": 12, "to": 15, "label": "EVAL with clause\nshanoi(s(0), X13, X14, X15, .(mv(X13, X15), [])).\nand substitutionT1 -> s(0),\nT2 -> T18,\nX13 -> T18,\nT3 -> T19,\nX14 -> T19,\nT4 -> T20,\nX15 -> T20,\nT5 -> .(mv(T18, T20), [])" }, { "from": 12, "to": 16, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 25, "label": "EVAL with clause\nshanoi(s(s(X30)), X31, X32, X33, X34) :- ','(eq(X35, s(X30)), ','(shanoi(X35, X31, X33, X32, X36), ','(shanoi(X35, X32, X31, X33, X37), ','(append(X36, .(mv(X31, X33), []), X38), append(X38, X37, X34))))).\nand substitutionX30 -> T31,\nT1 -> s(s(T31)),\nT2 -> T32,\nX31 -> T32,\nT3 -> T33,\nX32 -> T33,\nT4 -> T34,\nX33 -> T34,\nT5 -> T36,\nX34 -> T36,\nT35 -> T36" }, { "from": 14, "to": 26, "label": "EVAL-BACKTRACK" }, { "from": 15, "to": 17, "label": "SUCCESS" }, { "from": 25, "to": 362, "label": "CASE" }, { "from": 362, "to": 366, "label": "ONLY EVAL with clause\neq(X58, X58).\nand substitutionX35 -> s(T54),\nX58 -> s(T54),\nT31 -> T54,\nX59 -> s(T54)" }, { "from": 366, "to": 368, "label": "SPLIT 1" }, { "from": 366, "to": 369, "label": "SPLIT 2\nnew knowledge:\nT54 is ground\nT32 is ground\nT34 is ground\nT33 is ground\nT61 is ground\nreplacements:X36 -> T61" }, { "from": 368, "to": 3, "label": "INSTANCE with matching:\nT1 -> s(T54)\nT2 -> T32\nT3 -> T34\nT4 -> T33\nT5 -> X36" }, { "from": 369, "to": 372, "label": "SPLIT 1" }, { "from": 369, "to": 373, "label": "SPLIT 2\nnew knowledge:\nT54 is ground\nT33 is ground\nT32 is ground\nT34 is ground\nT74 is ground\nreplacements:X37 -> T74" }, { "from": 372, "to": 3, "label": "INSTANCE with matching:\nT1 -> s(T54)\nT2 -> T33\nT3 -> T32\nT4 -> T34\nT5 -> X37" }, { "from": 373, "to": 376, "label": "SPLIT 1" }, { "from": 373, "to": 377, "label": "SPLIT 2\nnew knowledge:\nT61 is ground\nT32 is ground\nT34 is ground\nT85 is ground\nreplacements:X38 -> T85" }, { "from": 376, "to": 377, "label": "INSTANCE with matching:\nT85 -> T61\nT74 -> .(mv(T32, T34), [])\nT36 -> X38" }, { "from": 377, "to": 378, "label": "CASE" }, { "from": 378, "to": 379, "label": "PARALLEL" }, { "from": 378, "to": 380, "label": "PARALLEL" }, { "from": 379, "to": 381, "label": "EVAL with clause\nappend([], X94, X94).\nand substitutionT85 -> [],\nT74 -> T96,\nX94 -> T96,\nT36 -> T96" }, { "from": 379, "to": 382, "label": "EVAL-BACKTRACK" }, { "from": 380, "to": 394, "label": "EVAL with clause\nappend(.(X103, X104), X105, .(X103, X106)) :- append(X104, X105, X106).\nand substitutionX103 -> T105,\nX104 -> T106,\nT85 -> .(T105, T106),\nT74 -> T107,\nX105 -> T107,\nX106 -> T109,\nT36 -> .(T105, T109),\nT108 -> T109" }, { "from": 380, "to": 395, "label": "EVAL-BACKTRACK" }, { "from": 381, "to": 383, "label": "SUCCESS" }, { "from": 394, "to": 377, "label": "INSTANCE with matching:\nT85 -> T106\nT74 -> T107\nT36 -> T109" } ], "type": "Graph" } } ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Rules: f377_in(T85, T74) -> f378_in(T85, T74) :|: TRUE f378_out(x, x1) -> f377_out(x, x1) :|: TRUE f395_out -> f380_out(x2, x3) :|: TRUE f394_out(T106, T107) -> f380_out(.(T105, T106), T107) :|: TRUE f380_in(x4, x5) -> f395_in :|: TRUE f380_in(.(x6, x7), x8) -> f394_in(x7, x8) :|: TRUE f377_out(x9, x10) -> f394_out(x9, x10) :|: TRUE f394_in(x11, x12) -> f377_in(x11, x12) :|: TRUE f378_in(x13, x14) -> f379_in(x13, x14) :|: TRUE f380_out(x15, x16) -> f378_out(x15, x16) :|: TRUE f379_out(x17, x18) -> f378_out(x17, x18) :|: TRUE f378_in(x19, x20) -> f380_in(x19, x20) :|: TRUE f6_out(T1, T2, T3, T4) -> f3_out(T1, T2, T3, T4) :|: TRUE f3_in(x21, x22, x23, x24) -> f6_in(x21, x22, x23, x24) :|: TRUE f12_out(x25, x26, x27, x28) -> f6_out(x25, x26, x27, x28) :|: TRUE f6_in(x29, x30, x31, x32) -> f14_in(x29, x30, x31, x32) :|: TRUE f14_out(x33, x34, x35, x36) -> f6_out(x33, x34, x35, x36) :|: TRUE f6_in(x37, x38, x39, x40) -> f12_in(x37, x38, x39, x40) :|: TRUE f14_in(x41, x42, x43, x44) -> f26_in :|: TRUE f26_out -> f14_out(x45, x46, x47, x48) :|: TRUE f25_out(T31, T32, T34, T33) -> f14_out(s(s(T31)), T32, T33, T34) :|: TRUE f14_in(s(s(x49)), x50, x51, x52) -> f25_in(x49, x50, x52, x51) :|: TRUE f362_out(x53, x54, x55, x56) -> f25_out(x53, x54, x55, x56) :|: TRUE f25_in(x57, x58, x59, x60) -> f362_in(x57, x58, x59, x60) :|: TRUE f366_out(x61, x62, x63, x64) -> f362_out(x61, x62, x63, x64) :|: TRUE f362_in(x65, x66, x67, x68) -> f366_in(x65, x66, x67, x68) :|: TRUE f369_out(x69, x70, x71, x72, x73) -> f366_out(x69, x71, x72, x70) :|: TRUE f368_out(x74, x75, x76, x77) -> f369_in(x74, x77, x75, x76, x78) :|: TRUE f366_in(x79, x80, x81, x82) -> f368_in(x79, x80, x81, x82) :|: TRUE f373_out(x83, x84, x85, x86) -> f369_out(x87, x88, x84, x85, x83) :|: TRUE f369_in(x89, x90, x91, x92, x93) -> f372_in(x89, x90, x91, x92) :|: TRUE f372_out(x94, x95, x96, x97) -> f373_in(x98, x96, x97, x99) :|: TRUE f376_out(x100, x101, x102) -> f377_in(x103, x104) :|: TRUE f373_in(x105, x106, x107, x108) -> f376_in(x105, x106, x107) :|: TRUE f377_out(x109, x110) -> f373_out(x111, x112, x113, x110) :|: TRUE f377_out(x114, .(mv(x115, x116), [])) -> f376_out(x114, x115, x116) :|: TRUE f376_in(x117, x118, x119) -> f377_in(x117, .(mv(x118, x119), [])) :|: 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: f376_out(T61, T32, T34) -> f377_in(T85, T74) :|: TRUE f373_in(x, x1, x2, x3) -> f376_in(x, x1, x2) :|: TRUE f377_out(x4, x5) -> f373_out(x6, x7, x8, x5) :|: TRUE f362_out(x9, x10, x11, x12) -> f25_out(x9, x10, x11, x12) :|: TRUE f25_in(x13, x14, x15, x16) -> f362_in(x13, x14, x15, x16) :|: TRUE f377_out(T106, T107) -> f394_out(T106, T107) :|: TRUE f394_in(x17, x18) -> f377_in(x17, x18) :|: TRUE f377_in(x19, x20) -> f378_in(x19, x20) :|: TRUE f378_out(x21, x22) -> f377_out(x21, x22) :|: TRUE f377_out(x23, .(mv(x24, x25), [])) -> f376_out(x23, x24, x25) :|: TRUE f376_in(x26, x27, x28) -> f377_in(x26, .(mv(x27, x28), [])) :|: TRUE f395_out -> f380_out(x29, x30) :|: TRUE f394_out(x31, x32) -> f380_out(.(x33, x31), x32) :|: TRUE f380_in(x34, x35) -> f395_in :|: TRUE f380_in(.(x36, x37), x38) -> f394_in(x37, x38) :|: TRUE f6_out(T1, T2, T3, T4) -> f3_out(T1, T2, T3, T4) :|: TRUE f3_in(x39, x40, x41, x42) -> f6_in(x39, x40, x41, x42) :|: TRUE f3_out(s(x43), x44, x45, x46) -> f372_out(x43, x44, x45, x46) :|: TRUE f372_in(x47, x48, x49, x50) -> f3_in(s(x47), x48, x49, x50) :|: TRUE f369_out(x51, x52, x53, x54, x55) -> f366_out(x51, x53, x54, x52) :|: TRUE f368_out(x56, x57, x58, x59) -> f369_in(x56, x59, x57, x58, x60) :|: TRUE f366_in(x61, x62, x63, x64) -> f368_in(x61, x62, x63, x64) :|: TRUE f366_out(x65, x66, x67, x68) -> f362_out(x65, x66, x67, x68) :|: TRUE f362_in(x69, x70, x71, x72) -> f366_in(x69, x70, x71, x72) :|: TRUE f379_in(x73, x74) -> f382_in :|: TRUE f379_in([], T96) -> f381_in :|: TRUE f381_out -> f379_out([], x75) :|: TRUE f382_out -> f379_out(x76, x77) :|: TRUE f378_in(x78, x79) -> f379_in(x78, x79) :|: TRUE f380_out(x80, x81) -> f378_out(x80, x81) :|: TRUE f379_out(x82, x83) -> f378_out(x82, x83) :|: TRUE f378_in(x84, x85) -> f380_in(x84, x85) :|: TRUE f381_in -> f381_out :|: TRUE f12_out(x86, x87, x88, x89) -> f6_out(x86, x87, x88, x89) :|: TRUE f6_in(x90, x91, x92, x93) -> f14_in(x90, x91, x92, x93) :|: TRUE f14_out(x94, x95, x96, x97) -> f6_out(x94, x95, x96, x97) :|: TRUE f6_in(x98, x99, x100, x101) -> f12_in(x98, x99, x100, x101) :|: TRUE f14_in(x102, x103, x104, x105) -> f26_in :|: TRUE f26_out -> f14_out(x106, x107, x108, x109) :|: TRUE f25_out(x110, x111, x112, x113) -> f14_out(s(s(x110)), x111, x113, x112) :|: TRUE f14_in(s(s(x114)), x115, x116, x117) -> f25_in(x114, x115, x117, x116) :|: TRUE f368_in(x118, x119, x120, x121) -> f3_in(s(x118), x119, x120, x121) :|: TRUE f3_out(s(x122), x123, x124, x125) -> f368_out(x122, x123, x124, x125) :|: TRUE f373_out(x126, x127, x128, x129) -> f369_out(x130, x131, x127, x128, x126) :|: TRUE f369_in(x132, x133, x134, x135, x136) -> f372_in(x132, x133, x134, x135) :|: TRUE f372_out(x137, x138, x139, x140) -> f373_in(x141, x139, x140, x142) :|: TRUE Start term: f3_in(T1, T2, T3, T4) ---------------------------------------- (7) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f25_in(x13, x14, x15, x16) -> f362_in(x13, x14, x15, x16) :|: TRUE f3_in(x39, x40, x41, x42) -> f6_in(x39, x40, x41, x42) :|: TRUE f366_in(x61, x62, x63, x64) -> f368_in(x61, x62, x63, x64) :|: TRUE f362_in(x69, x70, x71, x72) -> f366_in(x69, x70, x71, x72) :|: TRUE f6_in(x90, x91, x92, x93) -> f14_in(x90, x91, x92, x93) :|: TRUE f14_in(s(s(x114)), x115, x116, x117) -> f25_in(x114, x115, x117, x116) :|: TRUE f368_in(x118, x119, x120, x121) -> f3_in(s(x118), x119, x120, x121) :|: TRUE ---------------------------------------- (8) Obligation: Rules: f25_in(x13, x14, x15, x16) -> f362_in(x13, x14, x15, x16) :|: TRUE f3_in(x39, x40, x41, x42) -> f6_in(x39, x40, x41, x42) :|: TRUE f366_in(x61, x62, x63, x64) -> f368_in(x61, x62, x63, x64) :|: TRUE f362_in(x69, x70, x71, x72) -> f366_in(x69, x70, x71, x72) :|: TRUE f6_in(x90, x91, x92, x93) -> f14_in(x90, x91, x92, x93) :|: TRUE f14_in(s(s(x114)), x115, x116, x117) -> f25_in(x114, x115, x117, x116) :|: TRUE f368_in(x118, x119, x120, x121) -> f3_in(s(x118), x119, x120, x121) :|: TRUE ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f3_in(s(s(x114:0)), x40:0, x41:0, x42:0) -> f3_in(s(x114:0), x40:0, x42:0, x41:0) :|: TRUE ---------------------------------------- (11) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (12) Obligation: Rules: f3_in(s(s(x114:0)), x40:0, x41:0, x42:0) -> f3_in(s(x114:0), x40:0, x42:0, x41:0) :|: TRUE ---------------------------------------- (13) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3_in(s(s(x114:0)), x40:0, x41:0, x42:0) -> f3_in(s(x114:0), x40:0, x42:0, x41:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f3_in(s(s(x114:0)), x40:0, x41:0, x42:0) -> f3_in(s(x114:0), x40:0, x42:0, x41:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) 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) ---------------------------------------- (16) Obligation: Rules: f3_in(s(s(x114:0))) -> f3_in(s(x114:0)) :|: TRUE ---------------------------------------- (17) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (18) Obligation: Rules: f3_in(s(s(x114:0))) -> f3_in(s(x114:0)) ---------------------------------------- (19) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: f3_in(s(s(x114:0))) -> f3_in(s(x114:0)) R is empty. Q is empty. We have to consider all (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: *f3_in(s(s(x114:0))) -> f3_in(s(x114:0)) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES