/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 star(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) BuiltinConflictTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToDTProblemTransformerProof [SOUND, 0 ms] (4) TRIPLES (5) TriplesToPiDPProof [SOUND, 0 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [SOUND, 3 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 1 ms] (15) YES (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPOrderProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) TRUE ---------------------------------------- (0) Obligation: Clauses: star(U, []) :- !. star([], W) :- ','(!, =(W, [])). star(U, W) :- ','(app(U, V, W), star(U, V)). app([], L, L). app(.(X, L), M, .(X, N)) :- app(L, M, N). =(X, X). Query: star(g,g) ---------------------------------------- (1) BuiltinConflictTransformerProof (EQUIVALENT) Renamed defined predicates conflicting with built-in predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: star(U, []) :- !. star([], W) :- ','(!, user_defined_=(W, [])). star(U, W) :- ','(app(U, V, W), star(U, V)). app([], L, L). app(.(X, L), M, .(X, N)) :- app(L, M, N). user_defined_=(X, X). Query: star(g,g) ---------------------------------------- (3) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(star U ([]))", "(!)" ], [ "(star ([]) W)", "(',' (!) (user_defined_= W ([])))" ], [ "(star U W)", "(',' (app U V W) (star U V))" ], [ "(app ([]) L L)", null ], [ "(app (. X L) M (. X N))", "(app L M N)" ], [ "(user_defined_= X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "195": { "goal": [ { "clause": 1, "scope": 1, "term": "(star T1 T2)" }, { "clause": 2, "scope": 1, "term": "(star T1 T2)" } ], "kb": { "nonunifying": [[ "(star T1 T2)", "(star X2 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": ["X2"], "exprvars": [] } }, "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "197": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(star (. T19 T20) T24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T24" ], "free": [], "exprvars": [] } }, "231": { "goal": [ { "clause": 3, "scope": 4, "term": "(app T20 X27 T21)" }, { "clause": 4, "scope": 4, "term": "(app T20 X27 T21)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X27"], "exprvars": [] } }, "232": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T20 X27 T21)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X27"], "exprvars": [] } }, "233": { "goal": [{ "clause": 4, "scope": 4, "term": "(app T20 X27 T21)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X27"], "exprvars": [] } }, "236": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "219": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (user_defined_= T6 ([])))" }, { "clause": 2, "scope": 1, "term": "(star ([]) T6)" } ], "kb": { "nonunifying": [[ "(star ([]) T6)", "(star X2 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X2"], "exprvars": [] } }, "14": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(star T4 ([]))" }, { "clause": 2, "scope": 1, "term": "(star T4 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": 2, "scope": 1, "term": "(star T1 T2)" }], "kb": { "nonunifying": [ [ "(star T1 T2)", "(star X2 ([]))" ], [ "(star T1 T2)", "(star ([]) X4)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [ "X2", "X4" ], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T39 X60 T40)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T39", "T40" ], "free": ["X60"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(star T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "221": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T6 ([]))" }], "kb": { "nonunifying": [[ "(star ([]) T6)", "(star X2 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X2"], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [ { "clause": 0, "scope": 1, "term": "(star T1 T2)" }, { "clause": 1, "scope": 1, "term": "(star T1 T2)" }, { "clause": 2, "scope": 1, "term": "(star T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": 5, "scope": 2, "term": "(user_defined_= T6 ([]))" }], "kb": { "nonunifying": [[ "(star ([]) T6)", "(star X2 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X2"], "exprvars": [] } }, "223": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T10 X10 T11) (star T10 X10))" }], "kb": { "nonunifying": [ [ "(star T10 T11)", "(star X2 ([]))" ], [ "(star T10 T11)", "(star ([]) X4)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X2", "X4", "X10" ], "exprvars": [] } }, "225": { "goal": [ { "clause": 3, "scope": 3, "term": "(',' (app T10 X10 T11) (star T10 X10))" }, { "clause": 4, "scope": 3, "term": "(',' (app T10 X10 T11) (star T10 X10))" } ], "kb": { "nonunifying": [ [ "(star T10 T11)", "(star X2 ([]))" ], [ "(star T10 T11)", "(star ([]) X4)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X2", "X4", "X10" ], "exprvars": [] } }, "226": { "goal": [{ "clause": 4, "scope": 3, "term": "(',' (app T10 X10 T11) (star T10 X10))" }], "kb": { "nonunifying": [ [ "(star T10 T11)", "(star X2 ([]))" ], [ "(star T10 T11)", "(star ([]) X4)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X2", "X4", "X10" ], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T20 X27 T21) (star (. T19 T20) X27))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T21" ], "free": ["X27"], "exprvars": [] } }, "228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T20 X27 T21)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X27"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 14, "label": "EVAL with clause\nstar(X2, []) :- !_1.\nand substitutionT1 -> T4,\nX2 -> T4,\nT2 -> []" }, { "from": 2, "to": 195, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 196, "label": "CUT" }, { "from": 195, "to": 219, "label": "EVAL with clause\nstar([], X4) :- ','(!_1, user_defined_=(X4, [])).\nand substitutionT1 -> [],\nT2 -> T6,\nX4 -> T6" }, { "from": 195, "to": 220, "label": "EVAL-BACKTRACK" }, { "from": 196, "to": 197, "label": "SUCCESS" }, { "from": 219, "to": 221, "label": "CUT" }, { "from": 220, "to": 224, "label": "ONLY EVAL with clause\nstar(X8, X9) :- ','(app(X8, X10, X9), star(X8, X10)).\nand substitutionT1 -> T10,\nX8 -> T10,\nT2 -> T11,\nX9 -> T11" }, { "from": 221, "to": 222, "label": "CASE" }, { "from": 222, "to": 223, "label": "BACKTRACK\nfor clause: user_defined_=(X, X)\nwith clash: (star([], T6), star(X2, []))" }, { "from": 224, "to": 225, "label": "CASE" }, { "from": 225, "to": 226, "label": "BACKTRACK\nfor clause: app([], L, L)\nwith clash: (star(T10, T11), star([], X4))" }, { "from": 226, "to": 227, "label": "EVAL with clause\napp(.(X23, X24), X25, .(X23, X26)) :- app(X24, X25, X26).\nand substitutionX23 -> T19,\nX24 -> T20,\nT10 -> .(T19, T20),\nX10 -> X27,\nX25 -> X27,\nX26 -> T21,\nT11 -> .(T19, T21)" }, { "from": 226, "to": 228, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 229, "label": "SPLIT 1" }, { "from": 227, "to": 230, "label": "SPLIT 2\nnew knowledge:\nT20 is ground\nT24 is ground\nT21 is ground\nreplacements:X27 -> T24" }, { "from": 229, "to": 231, "label": "CASE" }, { "from": 230, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T19, T20)\nT2 -> T24" }, { "from": 231, "to": 232, "label": "PARALLEL" }, { "from": 231, "to": 233, "label": "PARALLEL" }, { "from": 232, "to": 236, "label": "EVAL with clause\napp([], X44, X44).\nand substitutionT20 -> [],\nX27 -> T31,\nX44 -> T31,\nT21 -> T31,\nX45 -> T31" }, { "from": 232, "to": 237, "label": "EVAL-BACKTRACK" }, { "from": 233, "to": 242, "label": "EVAL with clause\napp(.(X56, X57), X58, .(X56, X59)) :- app(X57, X58, X59).\nand substitutionX56 -> T38,\nX57 -> T39,\nT20 -> .(T38, T39),\nX27 -> X60,\nX58 -> X60,\nX59 -> T40,\nT21 -> .(T38, T40)" }, { "from": 233, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 238, "label": "SUCCESS" }, { "from": 242, "to": 229, "label": "INSTANCE with matching:\nT20 -> T39\nX27 -> X60\nT21 -> T40" } ], "type": "Graph" } } ---------------------------------------- (4) Obligation: Triples: appB(.(X1, X2), X3, .(X1, X4)) :- appB(X2, X3, X4). starA(.(X1, X2), .(X1, X3)) :- appB(X2, X4, X3). starA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4, X3), starA(.(X1, X2), X4)). Clauses: starcA(X1, []). starcA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4, X3), starcA(.(X1, X2), X4)). appcB([], X1, X1). appcB(.(X1, X2), X3, .(X1, X4)) :- appcB(X2, X3, X4). Afs: starA(x1, x2) = starA(x1, x2) ---------------------------------------- (5) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: starA_in_2: (b,b) appB_in_3: (b,f,b) appcB_in_3: (b,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U2_GG(X1, X2, X3, appB_in_gag(X2, X4, X3)) STARA_IN_GG(.(X1, X2), .(X1, X3)) -> APPB_IN_GAG(X2, X4, X3) APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> U1_GAG(X1, X2, X3, X4, appB_in_gag(X2, X3, X4)) APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAG(X2, X3, X4) STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U3_GG(X1, X2, X3, appcB_in_gag(X2, X4, X3)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> U4_GG(X1, X2, X3, starA_in_gg(.(X1, X2), X4)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> STARA_IN_GG(.(X1, X2), X4) The TRS R consists of the following rules: appcB_in_gag([], X1, X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), X3, .(X1, X4)) -> U8_gag(X1, X2, X3, X4, appcB_in_gag(X2, X3, X4)) U8_gag(X1, X2, X3, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: starA_in_gg(x1, x2) = starA_in_gg(x1, x2) .(x1, x2) = .(x1, x2) appB_in_gag(x1, x2, x3) = appB_in_gag(x1, x3) appcB_in_gag(x1, x2, x3) = appcB_in_gag(x1, x3) [] = [] appcB_out_gag(x1, x2, x3) = appcB_out_gag(x1, x2, x3) U8_gag(x1, x2, x3, x4, x5) = U8_gag(x1, x2, x4, x5) STARA_IN_GG(x1, x2) = STARA_IN_GG(x1, x2) U2_GG(x1, x2, x3, x4) = U2_GG(x1, x2, x3, x4) APPB_IN_GAG(x1, x2, x3) = APPB_IN_GAG(x1, x3) U1_GAG(x1, x2, x3, x4, x5) = U1_GAG(x1, x2, x4, x5) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U2_GG(X1, X2, X3, appB_in_gag(X2, X4, X3)) STARA_IN_GG(.(X1, X2), .(X1, X3)) -> APPB_IN_GAG(X2, X4, X3) APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> U1_GAG(X1, X2, X3, X4, appB_in_gag(X2, X3, X4)) APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAG(X2, X3, X4) STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U3_GG(X1, X2, X3, appcB_in_gag(X2, X4, X3)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> U4_GG(X1, X2, X3, starA_in_gg(.(X1, X2), X4)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> STARA_IN_GG(.(X1, X2), X4) The TRS R consists of the following rules: appcB_in_gag([], X1, X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), X3, .(X1, X4)) -> U8_gag(X1, X2, X3, X4, appcB_in_gag(X2, X3, X4)) U8_gag(X1, X2, X3, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: starA_in_gg(x1, x2) = starA_in_gg(x1, x2) .(x1, x2) = .(x1, x2) appB_in_gag(x1, x2, x3) = appB_in_gag(x1, x3) appcB_in_gag(x1, x2, x3) = appcB_in_gag(x1, x3) [] = [] appcB_out_gag(x1, x2, x3) = appcB_out_gag(x1, x2, x3) U8_gag(x1, x2, x3, x4, x5) = U8_gag(x1, x2, x4, x5) STARA_IN_GG(x1, x2) = STARA_IN_GG(x1, x2) U2_GG(x1, x2, x3, x4) = U2_GG(x1, x2, x3, x4) APPB_IN_GAG(x1, x2, x3) = APPB_IN_GAG(x1, x3) U1_GAG(x1, x2, x3, x4, x5) = U1_GAG(x1, x2, x4, x5) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAG(X2, X3, X4) The TRS R consists of the following rules: appcB_in_gag([], X1, X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), X3, .(X1, X4)) -> U8_gag(X1, X2, X3, X4, appcB_in_gag(X2, X3, X4)) U8_gag(X1, X2, X3, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcB_in_gag(x1, x2, x3) = appcB_in_gag(x1, x3) [] = [] appcB_out_gag(x1, x2, x3) = appcB_out_gag(x1, x2, x3) U8_gag(x1, x2, x3, x4, x5) = U8_gag(x1, x2, x4, x5) APPB_IN_GAG(x1, x2, x3) = APPB_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (11) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAG(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPB_IN_GAG(x1, x2, x3) = APPB_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: APPB_IN_GAG(.(X1, X2), .(X1, X4)) -> APPB_IN_GAG(X2, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) 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: *APPB_IN_GAG(.(X1, X2), .(X1, X4)) -> APPB_IN_GAG(X2, X4) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U3_GG(X1, X2, X3, appcB_in_gag(X2, X4, X3)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> STARA_IN_GG(.(X1, X2), X4) The TRS R consists of the following rules: appcB_in_gag([], X1, X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), X3, .(X1, X4)) -> U8_gag(X1, X2, X3, X4, appcB_in_gag(X2, X3, X4)) U8_gag(X1, X2, X3, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcB_in_gag(x1, x2, x3) = appcB_in_gag(x1, x3) [] = [] appcB_out_gag(x1, x2, x3) = appcB_out_gag(x1, x2, x3) U8_gag(x1, x2, x3, x4, x5) = U8_gag(x1, x2, x4, x5) STARA_IN_GG(x1, x2) = STARA_IN_GG(x1, x2) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U3_GG(X1, X2, X3, appcB_in_gag(X2, X3)) U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> STARA_IN_GG(.(X1, X2), X4) The TRS R consists of the following rules: appcB_in_gag([], X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), .(X1, X4)) -> U8_gag(X1, X2, X4, appcB_in_gag(X2, X4)) U8_gag(X1, X2, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The set Q consists of the following terms: appcB_in_gag(x0, x1) U8_gag(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U3_GG(X1, X2, X3, appcB_out_gag(X2, X4, X3)) -> STARA_IN_GG(.(X1, X2), X4) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U3_GG_4(x_1, ..., x_4) ) = 2x_1 + 2x_4 + 2 POL( appcB_in_gag_2(x_1, x_2) ) = 2x_2 POL( [] ) = 0 POL( appcB_out_gag_3(x_1, ..., x_3) ) = 2x_2 POL( ._2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( U8_gag_4(x_1, ..., x_4) ) = 2x_1 + 2x_4 POL( STARA_IN_GG_2(x_1, x_2) ) = max{0, 2x_2 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: appcB_in_gag([], X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), .(X1, X4)) -> U8_gag(X1, X2, X4, appcB_in_gag(X2, X4)) U8_gag(X1, X2, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: STARA_IN_GG(.(X1, X2), .(X1, X3)) -> U3_GG(X1, X2, X3, appcB_in_gag(X2, X3)) The TRS R consists of the following rules: appcB_in_gag([], X1) -> appcB_out_gag([], X1, X1) appcB_in_gag(.(X1, X2), .(X1, X4)) -> U8_gag(X1, X2, X4, appcB_in_gag(X2, X4)) U8_gag(X1, X2, X4, appcB_out_gag(X2, X3, X4)) -> appcB_out_gag(.(X1, X2), X3, .(X1, X4)) The set Q consists of the following terms: appcB_in_gag(x0, x1) U8_gag(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (22) TRUE