/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 shanoi(g,g,g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 1 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) PiDPToQDPProof [SOUND, 0 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 88 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) TRUE ---------------------------------------- (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) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "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": { "29": { "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": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi (s T31) T18 T20 T19 X23) (',' (shanoi (s T31) T19 T18 T20 X24) (',' (append X23 (. (mv T18 T20) ([])) X25) (append X25 X24 T22))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19", "T20", "T31" ], "free": [ "X23", "X24", "X25" ], "exprvars": [] } }, "370": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "371": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi (s T31) T19 T18 T20 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19", "T20", "T31" ], "free": ["X24"], "exprvars": [] } }, "254": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T38 (. (mv T18 T20) ([])) X25) (append X25 T51 T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T38", "T51" ], "free": ["X25"], "exprvars": [] } }, "378": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T83 T84 T86)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84" ], "free": [], "exprvars": [] } }, "379": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(shanoi (s (0)) T9 T10 T11 T5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": [], "exprvars": [] } }, "361": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T38 (. (mv T18 T20) ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T38" ], "free": ["X25"], "exprvars": [] } }, "362": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T62 T51 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T62" ], "free": [], "exprvars": [] } }, "1": { "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": [] } }, "243": { "goal": [{ "clause": 1, "scope": 1, "term": "(shanoi T1 T2 T3 T4 T5)" }], "kb": { "nonunifying": [[ "(shanoi T1 T2 T3 T4 T5)", "(shanoi (s (0)) X4 X5 X6 (. (mv X4 X6) ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq X22 (s T17)) (',' (shanoi X22 T18 T20 T19 X23) (',' (shanoi X22 T19 T18 T20 X24) (',' (append X23 (. (mv T18 T20) ([])) X25) (append X25 X24 T22)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [ "X22", "X23", "X24", "X25" ], "exprvars": [] } }, "267": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "366": { "goal": [ { "clause": 2, "scope": 3, "term": "(append T62 T51 T22)" }, { "clause": 3, "scope": 3, "term": "(append T62 T51 T22)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T62" ], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (eq X22 (s T17)) (',' (shanoi X22 T18 T20 T19 X23) (',' (shanoi X22 T19 T18 T20 X24) (',' (append X23 (. (mv T18 T20) ([])) X25) (append X25 X24 T22)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [ "X22", "X23", "X24", "X25" ], "exprvars": [] } }, "367": { "goal": [{ "clause": 2, "scope": 3, "term": "(append T62 T51 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T62" ], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(shanoi (s T31) T18 T20 T19 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19", "T20", "T31" ], "free": ["X23"], "exprvars": [] } }, "368": { "goal": [{ "clause": 3, "scope": 3, "term": "(append T62 T51 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T62" ], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": 1, "scope": 1, "term": "(shanoi (s (0)) T9 T10 T11 T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": [], "exprvars": [] } }, "347": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (shanoi (s T31) T19 T18 T20 X24) (',' (append T38 (. (mv T18 T20) ([])) X25) (append X25 X24 T22)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19", "T20", "T31", "T38" ], "free": [ "X24", "X25" ], "exprvars": [] } }, "369": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 29, "label": "CASE" }, { "from": 29, "to": 240, "label": "EVAL with clause\nshanoi(s(0), X4, X5, X6, .(mv(X4, X6), [])).\nand substitutionT1 -> s(0),\nT2 -> T9,\nX4 -> T9,\nT3 -> T10,\nX5 -> T10,\nT4 -> T11,\nX6 -> T11,\nT5 -> .(mv(T9, T11), [])" }, { "from": 29, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 240, "to": 248, "label": "SUCCESS" }, { "from": 243, "to": 266, "label": "EVAL with clause\nshanoi(s(s(X17)), X18, X19, X20, X21) :- ','(eq(X22, s(X17)), ','(shanoi(X22, X18, X20, X19, X23), ','(shanoi(X22, X19, X18, X20, X24), ','(append(X23, .(mv(X18, X20), []), X25), append(X25, X24, X21))))).\nand substitutionX17 -> T17,\nT1 -> s(s(T17)),\nT2 -> T18,\nX18 -> T18,\nT3 -> T19,\nX19 -> T19,\nT4 -> T20,\nX20 -> T20,\nT5 -> T22,\nX21 -> T22,\nT21 -> T22" }, { "from": 243, "to": 267, "label": "EVAL-BACKTRACK" }, { "from": 248, "to": 254, "label": "BACKTRACK\nfor clause: 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)))))because of non-unification" }, { "from": 266, "to": 268, "label": "CASE" }, { "from": 268, "to": 271, "label": "ONLY EVAL with clause\neq(X36, X36).\nand substitutionX22 -> s(T31),\nX36 -> s(T31),\nT17 -> T31,\nX37 -> s(T31)" }, { "from": 271, "to": 346, "label": "SPLIT 1" }, { "from": 271, "to": 347, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT18 is ground\nT20 is ground\nT19 is ground\nT38 is ground\nreplacements:X23 -> T38" }, { "from": 346, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T31)\nT2 -> T18\nT3 -> T20\nT4 -> T19\nT5 -> X23" }, { "from": 347, "to": 352, "label": "SPLIT 1" }, { "from": 347, "to": 353, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT19 is ground\nT18 is ground\nT20 is ground\nT51 is ground\nreplacements:X24 -> T51" }, { "from": 352, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T31)\nT2 -> T19\nT3 -> T18\nT4 -> T20\nT5 -> X24" }, { "from": 353, "to": 361, "label": "SPLIT 1" }, { "from": 353, "to": 362, "label": "SPLIT 2\nnew knowledge:\nT38 is ground\nT18 is ground\nT20 is ground\nT62 is ground\nreplacements:X25 -> T62" }, { "from": 361, "to": 362, "label": "INSTANCE with matching:\nT62 -> T38\nT51 -> .(mv(T18, T20), [])\nT22 -> X25" }, { "from": 362, "to": 366, "label": "CASE" }, { "from": 366, "to": 367, "label": "PARALLEL" }, { "from": 366, "to": 368, "label": "PARALLEL" }, { "from": 367, "to": 369, "label": "EVAL with clause\nappend([], X72, X72).\nand substitutionT62 -> [],\nT51 -> T73,\nX72 -> T73,\nT22 -> T73" }, { "from": 367, "to": 370, "label": "EVAL-BACKTRACK" }, { "from": 368, "to": 378, "label": "EVAL with clause\nappend(.(X81, X82), X83, .(X81, X84)) :- append(X82, X83, X84).\nand substitutionX81 -> T82,\nX82 -> T83,\nT62 -> .(T82, T83),\nT51 -> T84,\nX83 -> T84,\nX84 -> T86,\nT22 -> .(T82, T86),\nT85 -> T86" }, { "from": 368, "to": 379, "label": "EVAL-BACKTRACK" }, { "from": 369, "to": 371, "label": "SUCCESS" }, { "from": 378, "to": 362, "label": "INSTANCE with matching:\nT62 -> T83\nT51 -> T84\nT22 -> T86" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4). shanoiA(s(s(X1)), X2, X3, X4, X5) :- shanoiA(s(X1), X2, X4, X3, X6). shanoiA(s(s(X1)), X2, X3, X4, X5) :- ','(shanoicA(s(X1), X2, X4, X3, X6), shanoiA(s(X1), X3, X2, X4, X7)). shanoiA(s(s(X1)), X2, X3, X4, X5) :- ','(shanoicA(s(X1), X2, X4, X3, X6), ','(shanoicA(s(X1), X3, X2, X4, X7), appendB(X6, .(mv(X2, X4), []), X8))). shanoiA(s(s(X1)), X2, X3, X4, X5) :- ','(shanoicA(s(X1), X2, X4, X3, X6), ','(shanoicA(s(X1), X3, X2, X4, X7), ','(appendcB(X6, .(mv(X2, X4), []), X8), appendB(X8, X7, X5)))). Clauses: shanoicA(s(0), X1, X2, X3, .(mv(X1, X3), [])). shanoicA(s(s(X1)), X2, X3, X4, X5) :- ','(shanoicA(s(X1), X2, X4, X3, X6), ','(shanoicA(s(X1), X3, X2, X4, X7), ','(appendcB(X6, .(mv(X2, X4), []), X8), appendcB(X8, X7, X5)))). appendcB([], X1, X1). appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4). Afs: shanoiA(x1, x2, x3, x4, x5) = shanoiA(x1, x2, x3, x4) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: shanoiA_in_5: (b,b,b,b,f) shanoicA_in_5: (b,b,b,b,f) appendcB_in_3: (b,b,f) appendB_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> U2_GGGGA(X1, X2, X3, X4, X5, shanoiA_in_gggga(s(X1), X2, X4, X3, X6)) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> SHANOIA_IN_GGGGA(s(X1), X2, X4, X3, X6) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U4_GGGGA(X1, X2, X3, X4, X5, shanoiA_in_gggga(s(X1), X3, X2, X4, X7)) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> SHANOIA_IN_GGGGA(s(X1), X3, X2, X4, X7) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U6_GGGGA(X1, X2, X3, X4, X5, appendB_in_gga(X6, .(mv(X2, X4), []), X8)) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> APPENDB_IN_GGA(X6, .(mv(X2, X4), []), X8) APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appendB_in_gga(X2, X3, X4)) APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_GGA(X2, X3, X4) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U8_GGGGA(X1, X2, X3, X4, X5, appendB_in_gga(X8, X7, X5)) U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> APPENDB_IN_GGA(X8, X7, X5) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4, X5) -> U10_gggga(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U10_gggga(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) appendcB_in_gga([], X1, X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U14_gga(X1, X2, X3, X4, appendcB_in_gga(X2, X3, X4)) U14_gga(X1, X2, X3, X4, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, X5, appendcB_in_gga(X8, X7, X5)) U13_gggga(X1, X2, X3, X4, X5, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The argument filtering Pi contains the following mapping: shanoiA_in_gggga(x1, x2, x3, x4, x5) = shanoiA_in_gggga(x1, x2, x3, x4) s(x1) = s(x1) shanoicA_in_gggga(x1, x2, x3, x4, x5) = shanoicA_in_gggga(x1, x2, x3, x4) 0 = 0 shanoicA_out_gggga(x1, x2, x3, x4, x5) = shanoicA_out_gggga(x1, x2, x3, x4, x5) U10_gggga(x1, x2, x3, x4, x5, x6) = U10_gggga(x1, x2, x3, x4, x6) U11_gggga(x1, x2, x3, x4, x5, x6, x7) = U11_gggga(x1, x2, x3, x4, x6, x7) U12_gggga(x1, x2, x3, x4, x5, x6, x7) = U12_gggga(x1, x2, x3, x4, x6, x7) appendcB_in_gga(x1, x2, x3) = appendcB_in_gga(x1, x2) [] = [] appendcB_out_gga(x1, x2, x3) = appendcB_out_gga(x1, x2, x3) .(x1, x2) = .(x1, x2) U14_gga(x1, x2, x3, x4, x5) = U14_gga(x1, x2, x3, x5) mv(x1, x2) = mv(x1, x2) U13_gggga(x1, x2, x3, x4, x5, x6) = U13_gggga(x1, x2, x3, x4, x6) appendB_in_gga(x1, x2, x3) = appendB_in_gga(x1, x2) SHANOIA_IN_GGGGA(x1, x2, x3, x4, x5) = SHANOIA_IN_GGGGA(x1, x2, x3, x4) U2_GGGGA(x1, x2, x3, x4, x5, x6) = U2_GGGGA(x1, x2, x3, x4, x6) U3_GGGGA(x1, x2, x3, x4, x5, x6) = U3_GGGGA(x1, x2, x3, x4, x6) U4_GGGGA(x1, x2, x3, x4, x5, x6) = U4_GGGGA(x1, x2, x3, x4, x6) U5_GGGGA(x1, x2, x3, x4, x5, x6, x7) = U5_GGGGA(x1, x2, x3, x4, x6, x7) U6_GGGGA(x1, x2, x3, x4, x5, x6) = U6_GGGGA(x1, x2, x3, x4, x6) APPENDB_IN_GGA(x1, x2, x3) = APPENDB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U7_GGGGA(x1, x2, x3, x4, x5, x6, x7) = U7_GGGGA(x1, x2, x3, x4, x6, x7) U8_GGGGA(x1, x2, x3, x4, x5, x6) = U8_GGGGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> U2_GGGGA(X1, X2, X3, X4, X5, shanoiA_in_gggga(s(X1), X2, X4, X3, X6)) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> SHANOIA_IN_GGGGA(s(X1), X2, X4, X3, X6) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U4_GGGGA(X1, X2, X3, X4, X5, shanoiA_in_gggga(s(X1), X3, X2, X4, X7)) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> SHANOIA_IN_GGGGA(s(X1), X3, X2, X4, X7) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U6_GGGGA(X1, X2, X3, X4, X5, appendB_in_gga(X6, .(mv(X2, X4), []), X8)) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> APPENDB_IN_GGA(X6, .(mv(X2, X4), []), X8) APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appendB_in_gga(X2, X3, X4)) APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_GGA(X2, X3, X4) U5_GGGGA(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U8_GGGGA(X1, X2, X3, X4, X5, appendB_in_gga(X8, X7, X5)) U7_GGGGA(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> APPENDB_IN_GGA(X8, X7, X5) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4, X5) -> U10_gggga(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U10_gggga(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) appendcB_in_gga([], X1, X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U14_gga(X1, X2, X3, X4, appendcB_in_gga(X2, X3, X4)) U14_gga(X1, X2, X3, X4, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, X5, appendcB_in_gga(X8, X7, X5)) U13_gggga(X1, X2, X3, X4, X5, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The argument filtering Pi contains the following mapping: shanoiA_in_gggga(x1, x2, x3, x4, x5) = shanoiA_in_gggga(x1, x2, x3, x4) s(x1) = s(x1) shanoicA_in_gggga(x1, x2, x3, x4, x5) = shanoicA_in_gggga(x1, x2, x3, x4) 0 = 0 shanoicA_out_gggga(x1, x2, x3, x4, x5) = shanoicA_out_gggga(x1, x2, x3, x4, x5) U10_gggga(x1, x2, x3, x4, x5, x6) = U10_gggga(x1, x2, x3, x4, x6) U11_gggga(x1, x2, x3, x4, x5, x6, x7) = U11_gggga(x1, x2, x3, x4, x6, x7) U12_gggga(x1, x2, x3, x4, x5, x6, x7) = U12_gggga(x1, x2, x3, x4, x6, x7) appendcB_in_gga(x1, x2, x3) = appendcB_in_gga(x1, x2) [] = [] appendcB_out_gga(x1, x2, x3) = appendcB_out_gga(x1, x2, x3) .(x1, x2) = .(x1, x2) U14_gga(x1, x2, x3, x4, x5) = U14_gga(x1, x2, x3, x5) mv(x1, x2) = mv(x1, x2) U13_gggga(x1, x2, x3, x4, x5, x6) = U13_gggga(x1, x2, x3, x4, x6) appendB_in_gga(x1, x2, x3) = appendB_in_gga(x1, x2) SHANOIA_IN_GGGGA(x1, x2, x3, x4, x5) = SHANOIA_IN_GGGGA(x1, x2, x3, x4) U2_GGGGA(x1, x2, x3, x4, x5, x6) = U2_GGGGA(x1, x2, x3, x4, x6) U3_GGGGA(x1, x2, x3, x4, x5, x6) = U3_GGGGA(x1, x2, x3, x4, x6) U4_GGGGA(x1, x2, x3, x4, x5, x6) = U4_GGGGA(x1, x2, x3, x4, x6) U5_GGGGA(x1, x2, x3, x4, x5, x6, x7) = U5_GGGGA(x1, x2, x3, x4, x6, x7) U6_GGGGA(x1, x2, x3, x4, x5, x6) = U6_GGGGA(x1, x2, x3, x4, x6) APPENDB_IN_GGA(x1, x2, x3) = APPENDB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U7_GGGGA(x1, x2, x3, x4, x5, x6, x7) = U7_GGGGA(x1, x2, x3, x4, x6, x7) U8_GGGGA(x1, x2, x3, x4, x5, x6) = U8_GGGGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 9 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_GGA(X2, X3, X4) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4, X5) -> U10_gggga(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U10_gggga(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) appendcB_in_gga([], X1, X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U14_gga(X1, X2, X3, X4, appendcB_in_gga(X2, X3, X4)) U14_gga(X1, X2, X3, X4, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, X5, appendcB_in_gga(X8, X7, X5)) U13_gggga(X1, X2, X3, X4, X5, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The argument filtering Pi contains the following mapping: s(x1) = s(x1) shanoicA_in_gggga(x1, x2, x3, x4, x5) = shanoicA_in_gggga(x1, x2, x3, x4) 0 = 0 shanoicA_out_gggga(x1, x2, x3, x4, x5) = shanoicA_out_gggga(x1, x2, x3, x4, x5) U10_gggga(x1, x2, x3, x4, x5, x6) = U10_gggga(x1, x2, x3, x4, x6) U11_gggga(x1, x2, x3, x4, x5, x6, x7) = U11_gggga(x1, x2, x3, x4, x6, x7) U12_gggga(x1, x2, x3, x4, x5, x6, x7) = U12_gggga(x1, x2, x3, x4, x6, x7) appendcB_in_gga(x1, x2, x3) = appendcB_in_gga(x1, x2) [] = [] appendcB_out_gga(x1, x2, x3) = appendcB_out_gga(x1, x2, x3) .(x1, x2) = .(x1, x2) U14_gga(x1, x2, x3, x4, x5) = U14_gga(x1, x2, x3, x5) mv(x1, x2) = mv(x1, x2) U13_gggga(x1, x2, x3, x4, x5, x6) = U13_gggga(x1, x2, x3, x4, x6) APPENDB_IN_GGA(x1, x2, x3) = APPENDB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDB_IN_GGA(x1, x2, x3) = APPENDB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APPENDB_IN_GGA(.(X1, X2), X3) -> APPENDB_IN_GGA(X2, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *APPENDB_IN_GGA(.(X1, X2), X3) -> APPENDB_IN_GGA(X2, X3) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U3_GGGGA(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> SHANOIA_IN_GGGGA(s(X1), X3, X2, X4, X7) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4, X5) -> SHANOIA_IN_GGGGA(s(X1), X2, X4, X3, X6) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4, X5) -> U10_gggga(X1, X2, X3, X4, X5, shanoicA_in_gggga(s(X1), X2, X4, X3, X6)) U10_gggga(X1, X2, X3, X4, X5, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_in_gggga(s(X1), X3, X2, X4, X7)) U11_gggga(X1, X2, X3, X4, X5, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_in_gga(X6, .(mv(X2, X4), []), X8)) appendcB_in_gga([], X1, X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U14_gga(X1, X2, X3, X4, appendcB_in_gga(X2, X3, X4)) U14_gga(X1, X2, X3, X4, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X5, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, X5, appendcB_in_gga(X8, X7, X5)) U13_gggga(X1, X2, X3, X4, X5, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The argument filtering Pi contains the following mapping: s(x1) = s(x1) shanoicA_in_gggga(x1, x2, x3, x4, x5) = shanoicA_in_gggga(x1, x2, x3, x4) 0 = 0 shanoicA_out_gggga(x1, x2, x3, x4, x5) = shanoicA_out_gggga(x1, x2, x3, x4, x5) U10_gggga(x1, x2, x3, x4, x5, x6) = U10_gggga(x1, x2, x3, x4, x6) U11_gggga(x1, x2, x3, x4, x5, x6, x7) = U11_gggga(x1, x2, x3, x4, x6, x7) U12_gggga(x1, x2, x3, x4, x5, x6, x7) = U12_gggga(x1, x2, x3, x4, x6, x7) appendcB_in_gga(x1, x2, x3) = appendcB_in_gga(x1, x2) [] = [] appendcB_out_gga(x1, x2, x3) = appendcB_out_gga(x1, x2, x3) .(x1, x2) = .(x1, x2) U14_gga(x1, x2, x3, x4, x5) = U14_gga(x1, x2, x3, x5) mv(x1, x2) = mv(x1, x2) U13_gggga(x1, x2, x3, x4, x5, x6) = U13_gggga(x1, x2, x3, x4, x6) SHANOIA_IN_GGGGA(x1, x2, x3, x4, x5) = SHANOIA_IN_GGGGA(x1, x2, x3, x4) U3_GGGGA(x1, x2, x3, x4, x5, x6) = U3_GGGGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4) -> U3_GGGGA(X1, X2, X3, X4, shanoicA_in_gggga(s(X1), X2, X4, X3)) U3_GGGGA(X1, X2, X3, X4, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> SHANOIA_IN_GGGGA(s(X1), X3, X2, X4) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4) -> SHANOIA_IN_GGGGA(s(X1), X2, X4, X3) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4) -> U10_gggga(X1, X2, X3, X4, shanoicA_in_gggga(s(X1), X2, X4, X3)) U10_gggga(X1, X2, X3, X4, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X6, shanoicA_in_gggga(s(X1), X3, X2, X4)) U11_gggga(X1, X2, X3, X4, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X7, appendcB_in_gga(X6, .(mv(X2, X4), []))) appendcB_in_gga([], X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3) -> U14_gga(X1, X2, X3, appendcB_in_gga(X2, X3)) U14_gga(X1, X2, X3, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, appendcB_in_gga(X8, X7)) U13_gggga(X1, X2, X3, X4, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The set Q consists of the following terms: shanoicA_in_gggga(x0, x1, x2, x3) U10_gggga(x0, x1, x2, x3, x4) U11_gggga(x0, x1, x2, x3, x4, x5) appendcB_in_gga(x0, x1) U14_gga(x0, x1, x2, x3) U12_gggga(x0, x1, x2, x3, x4, x5) U13_gggga(x0, x1, x2, x3, x4) We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4) -> U3_GGGGA(X1, X2, X3, X4, shanoicA_in_gggga(s(X1), X2, X4, X3)) SHANOIA_IN_GGGGA(s(s(X1)), X2, X3, X4) -> SHANOIA_IN_GGGGA(s(X1), X2, X4, X3) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U3_GGGGA_5(x_1, ..., x_5) ) = x_1 POL( shanoicA_in_gggga_4(x_1, ..., x_4) ) = max{0, x_2 + 2x_4 - 2} POL( s_1(x_1) ) = x_1 + 2 POL( 0 ) = 0 POL( shanoicA_out_gggga_5(x_1, ..., x_5) ) = max{0, 2x_2 + 2x_3 + 2x_5 - 2} POL( ._2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( mv_2(x_1, x_2) ) = 1 POL( [] ) = 2 POL( U10_gggga_5(x_1, ..., x_5) ) = x_5 POL( U11_gggga_6(x_1, ..., x_6) ) = max{0, x_5 - 2} POL( U12_gggga_6(x_1, ..., x_6) ) = 2x_1 + 2x_3 + x_5 + 2 POL( appendcB_in_gga_2(x_1, x_2) ) = max{0, -2} POL( U13_gggga_5(x_1, ..., x_5) ) = x_2 + x_4 + 2 POL( appendcB_out_gga_3(x_1, ..., x_3) ) = max{0, 2x_3 - 2} POL( U14_gga_4(x_1, ..., x_4) ) = max{0, 2x_1 + 2x_2 + x_4 - 2} POL( SHANOIA_IN_GGGGA_4(x_1, ..., x_4) ) = max{0, x_1 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GGGGA(X1, X2, X3, X4, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> SHANOIA_IN_GGGGA(s(X1), X3, X2, X4) The TRS R consists of the following rules: shanoicA_in_gggga(s(0), X1, X2, X3) -> shanoicA_out_gggga(s(0), X1, X2, X3, .(mv(X1, X3), [])) shanoicA_in_gggga(s(s(X1)), X2, X3, X4) -> U10_gggga(X1, X2, X3, X4, shanoicA_in_gggga(s(X1), X2, X4, X3)) U10_gggga(X1, X2, X3, X4, shanoicA_out_gggga(s(X1), X2, X4, X3, X6)) -> U11_gggga(X1, X2, X3, X4, X6, shanoicA_in_gggga(s(X1), X3, X2, X4)) U11_gggga(X1, X2, X3, X4, X6, shanoicA_out_gggga(s(X1), X3, X2, X4, X7)) -> U12_gggga(X1, X2, X3, X4, X7, appendcB_in_gga(X6, .(mv(X2, X4), []))) appendcB_in_gga([], X1) -> appendcB_out_gga([], X1, X1) appendcB_in_gga(.(X1, X2), X3) -> U14_gga(X1, X2, X3, appendcB_in_gga(X2, X3)) U14_gga(X1, X2, X3, appendcB_out_gga(X2, X3, X4)) -> appendcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_gggga(X1, X2, X3, X4, X7, appendcB_out_gga(X6, .(mv(X2, X4), []), X8)) -> U13_gggga(X1, X2, X3, X4, appendcB_in_gga(X8, X7)) U13_gggga(X1, X2, X3, X4, appendcB_out_gga(X8, X7, X5)) -> shanoicA_out_gggga(s(s(X1)), X2, X3, X4, X5) The set Q consists of the following terms: shanoicA_in_gggga(x0, x1, x2, x3) U10_gggga(x0, x1, x2, x3, x4) U11_gggga(x0, x1, x2, x3, x4, x5) appendcB_in_gga(x0, x1) U14_gga(x0, x1, x2, x3) U12_gggga(x0, x1, x2, x3, x4, x5) U13_gggga(x0, x1, x2, x3, x4) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (20) TRUE