/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 ss(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 40 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 13 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PiDPToQDPProof [SOUND, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) PiDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) PiDP (38) PiDPToQDPProof [SOUND, 0 ms] (39) QDP (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] (41) YES ---------------------------------------- (0) Obligation: Clauses: ss(Xs, Ys) :- ','(perm(Xs, Ys), ordered(Ys)). perm([], []). perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys))). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). ordered([]). ordered(.(X1, [])). ordered(.(X, .(Y, Xs))) :- ','(less(X, s(Y)), ordered(.(Y, Xs))). less(0, s(X2)). less(s(X), s(Y)) :- less(X, Y). Query: ss(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(ss Xs Ys)", "(',' (perm Xs Ys) (ordered Ys))" ], [ "(perm ([]) ([]))", null ], [ "(perm Xs (. X Ys))", "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ], [ "(ordered ([]))", null ], [ "(ordered (. X1 ([])))", null ], [ "(ordered (. X (. Y Xs)))", "(',' (less X (s Y)) (ordered (. Y Xs)))" ], [ "(less (0) (s X2))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "type": "Nodes", "154": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "158": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "357": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X63 (. T42 X64) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T44" ], "free": [ "X63", "X64" ], "exprvars": [] } }, "555": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T105 (s T106))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T105", "T106" ], "free": [], "exprvars": [] } }, "479": { "goal": [ { "clause": 5, "scope": 7, "term": "(ordered (. T14 T15))" }, { "clause": 6, "scope": 7, "term": "(ordered (. T14 T15))" }, { "clause": 7, "scope": 7, "term": "(ordered (. T14 T15))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": [] } }, "556": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T106 T107))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T106", "T107" ], "free": [], "exprvars": [] } }, "557": { "goal": [ { "clause": 8, "scope": 8, "term": "(less T105 (s T106))" }, { "clause": 9, "scope": 8, "term": "(less T105 (s T106))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T105", "T106" ], "free": [], "exprvars": [] } }, "558": { "goal": [{ "clause": 8, "scope": 8, "term": "(less T105 (s T106))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T105", "T106" ], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "438": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T20 T21 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X25"], "exprvars": [] } }, "559": { "goal": [{ "clause": 9, "scope": 8, "term": "(less T105 (s T106))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T105", "T106" ], "free": [], "exprvars": [] } }, "439": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T51 T15) (ordered (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15", "T51" ], "free": [], "exprvars": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "480": { "goal": [ { "clause": 6, "scope": 7, "term": "(ordered (. T14 T15))" }, { "clause": 7, "scope": 7, "term": "(ordered (. T14 T15))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": [] } }, "360": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "163": { "goal": [{ "clause": 7, "scope": 3, "term": "(ordered ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "482": { "goal": [{ "clause": 6, "scope": 7, "term": "(ordered (. T14 T15))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": [] } }, "483": { "goal": [{ "clause": 7, "scope": 7, "term": "(ordered (. T14 T15))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": [] } }, "560": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "440": { "goal": [ { "clause": 3, "scope": 5, "term": "(app T20 T21 X25)" }, { "clause": 4, "scope": 5, "term": "(app T20 T21 X25)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X25"], "exprvars": [] } }, "561": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "441": { "goal": [{ "clause": 3, "scope": 5, "term": "(app T20 T21 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X25"], "exprvars": [] } }, "562": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "442": { "goal": [{ "clause": 4, "scope": 5, "term": "(app T20 T21 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X25"], "exprvars": [] } }, "486": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "563": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T121 T122)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T121", "T122" ], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(ss T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X23 (. T14 X24) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "443": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "487": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "564": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "323": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (app T20 T21 X25) (perm X25 T15)) (ordered (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15", "T20", "T21" ], "free": ["X25"], "exprvars": [] } }, "444": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "488": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "565": { "goal": [ { "clause": 8, "scope": 9, "term": "(less T121 T122)" }, { "clause": 9, "scope": 9, "term": "(less T121 T122)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T121", "T122" ], "free": [], "exprvars": [] } }, "445": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "489": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T105 (s T106)) (ordered (. T106 T107)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T105", "T106", "T107" ], "free": [], "exprvars": [] } }, "566": { "goal": [{ "clause": 8, "scope": 9, "term": "(less T121 T122)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T121", "T122" ], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(ss T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "446": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T66 T67 X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T67" ], "free": ["X92"], "exprvars": [] } }, "567": { "goal": [{ "clause": 9, "scope": 9, "term": "(less T121 T122)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T121", "T122" ], "free": [], "exprvars": [] } }, "128": { "goal": [ { "clause": 5, "scope": 3, "term": "(ordered ([]))" }, { "clause": 6, "scope": 3, "term": "(ordered ([]))" }, { "clause": 7, "scope": 3, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "447": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "568": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "327": { "goal": [ { "clause": 3, "scope": 4, "term": "(app X23 (. T14 X24) T13)" }, { "clause": 4, "scope": 4, "term": "(app X23 (. T14 X24) T13)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "448": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T51 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T51" ], "free": [], "exprvars": [] } }, "569": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [{ "clause": 3, "scope": 4, "term": "(app X23 (. T14 X24) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "449": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T14 T15))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": [] } }, "329": { "goal": [{ "clause": 4, "scope": 4, "term": "(app X23 (. T14 X24) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "67": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T5 T6) (ordered T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "490": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "570": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "450": { "goal": [ { "clause": 1, "scope": 6, "term": "(perm T51 T15)" }, { "clause": 2, "scope": 6, "term": "(perm T51 T15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T51" ], "free": [], "exprvars": [] } }, "571": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T134 T135)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T134", "T135" ], "free": [], "exprvars": [] } }, "297": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (app X23 (. T14 X24) T13) (',' (app X23 X24 X25) (perm X25 T15))) (ordered (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14", "T15" ], "free": [ "X23", "X24", "X25" ], "exprvars": [] } }, "451": { "goal": [{ "clause": 1, "scope": 6, "term": "(perm T51 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T51" ], "free": [], "exprvars": [] } }, "572": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "452": { "goal": [{ "clause": 2, "scope": 6, "term": "(perm T51 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T51" ], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "453": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "454": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "334": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "455": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "456": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X107 (. T77 X108) T76) (',' (app X107 X108 X109) (perm X109 T78)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T76", "T77", "T78" ], "free": [ "X107", "X108", "X109" ], "exprvars": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "457": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "458": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X107 (. T77 X108) T76)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T76", "T77" ], "free": [ "X107", "X108" ], "exprvars": [] } }, "459": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T83 T84 X109) (perm X109 T78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T83", "T84" ], "free": ["X109"], "exprvars": [] } }, "70": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (perm T5 T6) (ordered T6))" }, { "clause": 2, "scope": 2, "term": "(',' (perm T5 T6) (ordered T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (perm T5 T6) (ordered T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "76": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (perm T5 T6) (ordered T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "460": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T83 T84 X109)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84" ], "free": ["X109"], "exprvars": [] } }, "461": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T91 T78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T91" ], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": 5, "scope": 3, "term": "(ordered ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [ { "clause": 6, "scope": 3, "term": "(ordered ([]))" }, { "clause": 7, "scope": 3, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "304": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 67, "label": "ONLY EVAL with clause\nss(X5, X6) :- ','(perm(X5, X6), ordered(X6)).\nand substitutionT1 -> T5,\nX5 -> T5,\nT2 -> T6,\nX6 -> T6" }, { "from": 67, "to": 70, "label": "CASE" }, { "from": 70, "to": 75, "label": "PARALLEL" }, { "from": 70, "to": 76, "label": "PARALLEL" }, { "from": 75, "to": 92, "label": "EVAL with clause\nperm([], []).\nand substitutionT5 -> [],\nT6 -> []" }, { "from": 75, "to": 99, "label": "EVAL-BACKTRACK" }, { "from": 76, "to": 297, "label": "EVAL with clause\nperm(X20, .(X21, X22)) :- ','(app(X23, .(X21, X24), X20), ','(app(X23, X24, X25), perm(X25, X22))).\nand substitutionT5 -> T13,\nX20 -> T13,\nX21 -> T14,\nX22 -> T15,\nT6 -> .(T14, T15)" }, { "from": 76, "to": 304, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 128, "label": "CASE" }, { "from": 128, "to": 143, "label": "PARALLEL" }, { "from": 128, "to": 145, "label": "PARALLEL" }, { "from": 143, "to": 154, "label": "ONLY EVAL with clause\nordered([]).\nand substitution" }, { "from": 145, "to": 163, "label": "BACKTRACK\nfor clause: ordered(.(X1, []))because of non-unification" }, { "from": 154, "to": 158, "label": "SUCCESS" }, { "from": 163, "to": 214, "label": "BACKTRACK\nfor clause: ordered(.(X, .(Y, Xs))) :- ','(less(X, s(Y)), ordered(.(Y, Xs)))because of non-unification" }, { "from": 297, "to": 322, "label": "SPLIT 1" }, { "from": 297, "to": 323, "label": "SPLIT 2\nnew knowledge:\nT20 is ground\nT14 is ground\nT21 is ground\nT13 is ground\nreplacements:X23 -> T20,\nX24 -> T21" }, { "from": 322, "to": 327, "label": "CASE" }, { "from": 323, "to": 438, "label": "SPLIT 1" }, { "from": 323, "to": 439, "label": "SPLIT 2\nnew knowledge:\nT20 is ground\nT21 is ground\nT51 is ground\nreplacements:X25 -> T51" }, { "from": 327, "to": 328, "label": "PARALLEL" }, { "from": 327, "to": 329, "label": "PARALLEL" }, { "from": 328, "to": 332, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionX23 -> [],\nT14 -> T34,\nX24 -> T35,\nX42 -> .(T34, T35),\nX43 -> T35,\nT13 -> .(T34, T35)" }, { "from": 328, "to": 334, "label": "EVAL-BACKTRACK" }, { "from": 329, "to": 357, "label": "EVAL with clause\napp(.(X58, X59), X60, .(X58, X61)) :- app(X59, X60, X61).\nand substitutionX58 -> T43,\nX59 -> X63,\nX23 -> .(T43, X63),\nT14 -> T42,\nX24 -> X64,\nX60 -> .(T42, X64),\nX62 -> T43,\nX61 -> T44,\nT13 -> .(T43, T44)" }, { "from": 329, "to": 360, "label": "EVAL-BACKTRACK" }, { "from": 332, "to": 336, "label": "SUCCESS" }, { "from": 357, "to": 322, "label": "INSTANCE with matching:\nX23 -> X63\nT14 -> T42\nX24 -> X64\nT13 -> T44" }, { "from": 438, "to": 440, "label": "CASE" }, { "from": 439, "to": 448, "label": "SPLIT 1" }, { "from": 439, "to": 449, "label": "SPLIT 2\nnew knowledge:\nT51 is ground\nT15 is ground" }, { "from": 440, "to": 441, "label": "PARALLEL" }, { "from": 440, "to": 442, "label": "PARALLEL" }, { "from": 441, "to": 443, "label": "EVAL with clause\napp([], X77, X77).\nand substitutionT20 -> [],\nT21 -> T58,\nX77 -> T58,\nX25 -> T58" }, { "from": 441, "to": 444, "label": "EVAL-BACKTRACK" }, { "from": 442, "to": 446, "label": "EVAL with clause\napp(.(X88, X89), X90, .(X88, X91)) :- app(X89, X90, X91).\nand substitutionX88 -> T65,\nX89 -> T66,\nT20 -> .(T65, T66),\nT21 -> T67,\nX90 -> T67,\nX91 -> X92,\nX25 -> .(T65, X92)" }, { "from": 442, "to": 447, "label": "EVAL-BACKTRACK" }, { "from": 443, "to": 445, "label": "SUCCESS" }, { "from": 446, "to": 438, "label": "INSTANCE with matching:\nT20 -> T66\nT21 -> T67\nX25 -> X92" }, { "from": 448, "to": 450, "label": "CASE" }, { "from": 449, "to": 479, "label": "CASE" }, { "from": 450, "to": 451, "label": "PARALLEL" }, { "from": 450, "to": 452, "label": "PARALLEL" }, { "from": 451, "to": 453, "label": "EVAL with clause\nperm([], []).\nand substitutionT51 -> [],\nT15 -> []" }, { "from": 451, "to": 454, "label": "EVAL-BACKTRACK" }, { "from": 452, "to": 456, "label": "EVAL with clause\nperm(X104, .(X105, X106)) :- ','(app(X107, .(X105, X108), X104), ','(app(X107, X108, X109), perm(X109, X106))).\nand substitutionT51 -> T76,\nX104 -> T76,\nX105 -> T77,\nX106 -> T78,\nT15 -> .(T77, T78)" }, { "from": 452, "to": 457, "label": "EVAL-BACKTRACK" }, { "from": 453, "to": 455, "label": "SUCCESS" }, { "from": 456, "to": 458, "label": "SPLIT 1" }, { "from": 456, "to": 459, "label": "SPLIT 2\nnew knowledge:\nT83 is ground\nT77 is ground\nT84 is ground\nT76 is ground\nreplacements:X107 -> T83,\nX108 -> T84" }, { "from": 458, "to": 322, "label": "INSTANCE with matching:\nX23 -> X107\nT14 -> T77\nX24 -> X108\nT13 -> T76" }, { "from": 459, "to": 460, "label": "SPLIT 1" }, { "from": 459, "to": 461, "label": "SPLIT 2\nnew knowledge:\nT83 is ground\nT84 is ground\nT91 is ground\nreplacements:X109 -> T91" }, { "from": 460, "to": 438, "label": "INSTANCE with matching:\nT20 -> T83\nT21 -> T84\nX25 -> X109" }, { "from": 461, "to": 448, "label": "INSTANCE with matching:\nT51 -> T91\nT15 -> T78" }, { "from": 479, "to": 480, "label": "BACKTRACK\nfor clause: ordered([])because of non-unification" }, { "from": 480, "to": 482, "label": "PARALLEL" }, { "from": 480, "to": 483, "label": "PARALLEL" }, { "from": 482, "to": 486, "label": "EVAL with clause\nordered(.(X126, [])).\nand substitutionT14 -> T98,\nX126 -> T98,\nT15 -> []" }, { "from": 482, "to": 487, "label": "EVAL-BACKTRACK" }, { "from": 483, "to": 489, "label": "EVAL with clause\nordered(.(X133, .(X134, X135))) :- ','(less(X133, s(X134)), ordered(.(X134, X135))).\nand substitutionT14 -> T105,\nX133 -> T105,\nX134 -> T106,\nX135 -> T107,\nT15 -> .(T106, T107)" }, { "from": 483, "to": 490, "label": "EVAL-BACKTRACK" }, { "from": 486, "to": 488, "label": "SUCCESS" }, { "from": 489, "to": 555, "label": "SPLIT 1" }, { "from": 489, "to": 556, "label": "SPLIT 2\nnew knowledge:\nT105 is ground\nT106 is ground" }, { "from": 555, "to": 557, "label": "CASE" }, { "from": 556, "to": 449, "label": "INSTANCE with matching:\nT14 -> T106\nT15 -> T107" }, { "from": 557, "to": 558, "label": "PARALLEL" }, { "from": 557, "to": 559, "label": "PARALLEL" }, { "from": 558, "to": 560, "label": "EVAL with clause\nless(0, s(X144)).\nand substitutionT105 -> 0,\nT106 -> T116,\nX144 -> T116" }, { "from": 558, "to": 561, "label": "EVAL-BACKTRACK" }, { "from": 559, "to": 563, "label": "EVAL with clause\nless(s(X149), s(X150)) :- less(X149, X150).\nand substitutionX149 -> T121,\nT105 -> s(T121),\nT106 -> T122,\nX150 -> T122" }, { "from": 559, "to": 564, "label": "EVAL-BACKTRACK" }, { "from": 560, "to": 562, "label": "SUCCESS" }, { "from": 563, "to": 565, "label": "CASE" }, { "from": 565, "to": 566, "label": "PARALLEL" }, { "from": 565, "to": 567, "label": "PARALLEL" }, { "from": 566, "to": 568, "label": "EVAL with clause\nless(0, s(X157)).\nand substitutionT121 -> 0,\nX157 -> T129,\nT122 -> s(T129)" }, { "from": 566, "to": 569, "label": "EVAL-BACKTRACK" }, { "from": 567, "to": 571, "label": "EVAL with clause\nless(s(X162), s(X163)) :- less(X162, X163).\nand substitutionX162 -> T134,\nT121 -> s(T134),\nX163 -> T135,\nT122 -> s(T135)" }, { "from": 567, "to": 572, "label": "EVAL-BACKTRACK" }, { "from": 568, "to": 570, "label": "SUCCESS" }, { "from": 571, "to": 563, "label": "INSTANCE with matching:\nT121 -> T134\nT122 -> T135" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appA(.(X1, X2), X3, X4, .(X1, X5)) :- appA(X2, X3, X4, X5). appB(.(X1, X2), X3, .(X1, X4)) :- appB(X2, X3, X4). permC(X1, .(X2, X3)) :- appA(X4, X2, X5, X1). permC(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), appB(X4, X5, X6)). permC(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), ','(appcB(X4, X5, X6), permC(X6, X3))). orderedD(s(X1), .(X2, X3)) :- lessF(X1, X2). orderedD(X1, .(X2, X3)) :- ','(lesscE(X1, X2), orderedD(X2, X3)). lessF(s(X1), s(X2)) :- lessF(X1, X2). ssG(X1, .(X2, X3)) :- appA(X4, X2, X5, X1). ssG(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), appB(X4, X5, X6)). ssG(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), ','(appcB(X4, X5, X6), permC(X6, X3))). ssG(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), ','(appcB(X4, X5, X6), ','(permcC(X6, X3), orderedD(X2, X3)))). Clauses: appcA([], X1, X2, .(X1, X2)). appcA(.(X1, X2), X3, X4, .(X1, X5)) :- appcA(X2, X3, X4, X5). appcB([], X1, X1). appcB(.(X1, X2), X3, .(X1, X4)) :- appcB(X2, X3, X4). permcC([], []). permcC(X1, .(X2, X3)) :- ','(appcA(X4, X2, X5, X1), ','(appcB(X4, X5, X6), permcC(X6, X3))). orderedcD(X1, []). orderedcD(X1, .(X2, X3)) :- ','(lesscE(X1, X2), orderedcD(X2, X3)). lesscF(0, s(X1)). lesscF(s(X1), s(X2)) :- lesscF(X1, X2). lesscE(0, X1). lesscE(s(X1), X2) :- lesscF(X1, X2). Afs: ssG(x1, x2) = ssG(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: ssG_in_2: (b,b) appA_in_4: (f,b,f,b) appcA_in_4: (f,b,f,b) appB_in_3: (b,b,f) appcB_in_3: (b,b,f) permC_in_2: (b,b) permcC_in_2: (b,b) orderedD_in_2: (b,b) lessF_in_2: (b,b) lesscE_in_2: (b,b) lesscF_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SSG_IN_GG(X1, .(X2, X3)) -> U12_GG(X1, X2, X3, appA_in_agag(X4, X2, X5, X1)) SSG_IN_GG(X1, .(X2, X3)) -> APPA_IN_AGAG(X4, X2, X5, X1) APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AGAG(X1, X2, X3, X4, X5, appA_in_agag(X2, X3, X4, X5)) APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> APPA_IN_AGAG(X2, X3, X4, X5) SSG_IN_GG(X1, .(X2, X3)) -> U13_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U14_GG(X1, X2, X3, appB_in_gga(X4, X5, X6)) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> APPB_IN_GGA(X4, X5, X6) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U2_GGA(X1, X2, X3, X4, appB_in_gga(X2, X3, X4)) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U15_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U16_GG(X1, X2, X3, permC_in_gg(X6, X3)) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) PERMC_IN_GG(X1, .(X2, X3)) -> U3_GG(X1, X2, X3, appA_in_agag(X4, X2, X5, X1)) PERMC_IN_GG(X1, .(X2, X3)) -> APPA_IN_AGAG(X4, X2, X5, X1) PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U5_GG(X1, X2, X3, appB_in_gga(X4, X5, X6)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> APPB_IN_GGA(X4, X5, X6) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U7_GG(X1, X2, X3, permC_in_gg(X6, X3)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U17_GG(X1, X2, X3, permcC_in_gg(X6, X3)) U17_GG(X1, X2, X3, permcC_out_gg(X6, X3)) -> U18_GG(X1, X2, X3, orderedD_in_gg(X2, X3)) U17_GG(X1, X2, X3, permcC_out_gg(X6, X3)) -> ORDEREDD_IN_GG(X2, X3) ORDEREDD_IN_GG(s(X1), .(X2, X3)) -> U8_GG(X1, X2, X3, lessF_in_gg(X1, X2)) ORDEREDD_IN_GG(s(X1), .(X2, X3)) -> LESSF_IN_GG(X1, X2) LESSF_IN_GG(s(X1), s(X2)) -> U11_GG(X1, X2, lessF_in_gg(X1, X2)) LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> U10_GG(X1, X2, X3, orderedD_in_gg(X2, X3)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appA_in_agag(x1, x2, x3, x4) = appA_in_agag(x2, x4) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appB_in_gga(x1, x2, x3) = appB_in_gga(x1, x2) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permC_in_gg(x1, x2) = permC_in_gg(x1, x2) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) orderedD_in_gg(x1, x2) = orderedD_in_gg(x1, x2) s(x1) = s(x1) lessF_in_gg(x1, x2) = lessF_in_gg(x1, x2) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) SSG_IN_GG(x1, x2) = SSG_IN_GG(x1, x2) U12_GG(x1, x2, x3, x4) = U12_GG(x1, x2, x3, x4) APPA_IN_AGAG(x1, x2, x3, x4) = APPA_IN_AGAG(x2, x4) U1_AGAG(x1, x2, x3, x4, x5, x6) = U1_AGAG(x1, x3, x5, x6) U13_GG(x1, x2, x3, x4) = U13_GG(x1, x2, x3, x4) U14_GG(x1, x2, x3, x4) = U14_GG(x1, x2, x3, x4) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) U15_GG(x1, x2, x3, x4) = U15_GG(x1, x2, x3, x4) U16_GG(x1, x2, x3, x4) = U16_GG(x1, x2, x3, x4) PERMC_IN_GG(x1, x2) = PERMC_IN_GG(x1, x2) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U5_GG(x1, x2, x3, x4) = U5_GG(x1, x2, x3, x4) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) U17_GG(x1, x2, x3, x4) = U17_GG(x1, x2, x3, x4) U18_GG(x1, x2, x3, x4) = U18_GG(x1, x2, x3, x4) ORDEREDD_IN_GG(x1, x2) = ORDEREDD_IN_GG(x1, x2) U8_GG(x1, x2, x3, x4) = U8_GG(x1, x2, x3, x4) LESSF_IN_GG(x1, x2) = LESSF_IN_GG(x1, x2) U11_GG(x1, x2, x3) = U11_GG(x1, x2, x3) U9_GG(x1, x2, x3, x4) = U9_GG(x1, x2, x3, x4) U10_GG(x1, x2, x3, x4) = U10_GG(x1, x2, x3, x4) 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: SSG_IN_GG(X1, .(X2, X3)) -> U12_GG(X1, X2, X3, appA_in_agag(X4, X2, X5, X1)) SSG_IN_GG(X1, .(X2, X3)) -> APPA_IN_AGAG(X4, X2, X5, X1) APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AGAG(X1, X2, X3, X4, X5, appA_in_agag(X2, X3, X4, X5)) APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> APPA_IN_AGAG(X2, X3, X4, X5) SSG_IN_GG(X1, .(X2, X3)) -> U13_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U14_GG(X1, X2, X3, appB_in_gga(X4, X5, X6)) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> APPB_IN_GGA(X4, X5, X6) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U2_GGA(X1, X2, X3, X4, appB_in_gga(X2, X3, X4)) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) U13_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U15_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U16_GG(X1, X2, X3, permC_in_gg(X6, X3)) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) PERMC_IN_GG(X1, .(X2, X3)) -> U3_GG(X1, X2, X3, appA_in_agag(X4, X2, X5, X1)) PERMC_IN_GG(X1, .(X2, X3)) -> APPA_IN_AGAG(X4, X2, X5, X1) PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U5_GG(X1, X2, X3, appB_in_gga(X4, X5, X6)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> APPB_IN_GGA(X4, X5, X6) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U7_GG(X1, X2, X3, permC_in_gg(X6, X3)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) U15_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U17_GG(X1, X2, X3, permcC_in_gg(X6, X3)) U17_GG(X1, X2, X3, permcC_out_gg(X6, X3)) -> U18_GG(X1, X2, X3, orderedD_in_gg(X2, X3)) U17_GG(X1, X2, X3, permcC_out_gg(X6, X3)) -> ORDEREDD_IN_GG(X2, X3) ORDEREDD_IN_GG(s(X1), .(X2, X3)) -> U8_GG(X1, X2, X3, lessF_in_gg(X1, X2)) ORDEREDD_IN_GG(s(X1), .(X2, X3)) -> LESSF_IN_GG(X1, X2) LESSF_IN_GG(s(X1), s(X2)) -> U11_GG(X1, X2, lessF_in_gg(X1, X2)) LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> U10_GG(X1, X2, X3, orderedD_in_gg(X2, X3)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appA_in_agag(x1, x2, x3, x4) = appA_in_agag(x2, x4) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appB_in_gga(x1, x2, x3) = appB_in_gga(x1, x2) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permC_in_gg(x1, x2) = permC_in_gg(x1, x2) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) orderedD_in_gg(x1, x2) = orderedD_in_gg(x1, x2) s(x1) = s(x1) lessF_in_gg(x1, x2) = lessF_in_gg(x1, x2) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) SSG_IN_GG(x1, x2) = SSG_IN_GG(x1, x2) U12_GG(x1, x2, x3, x4) = U12_GG(x1, x2, x3, x4) APPA_IN_AGAG(x1, x2, x3, x4) = APPA_IN_AGAG(x2, x4) U1_AGAG(x1, x2, x3, x4, x5, x6) = U1_AGAG(x1, x3, x5, x6) U13_GG(x1, x2, x3, x4) = U13_GG(x1, x2, x3, x4) U14_GG(x1, x2, x3, x4) = U14_GG(x1, x2, x3, x4) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) U15_GG(x1, x2, x3, x4) = U15_GG(x1, x2, x3, x4) U16_GG(x1, x2, x3, x4) = U16_GG(x1, x2, x3, x4) PERMC_IN_GG(x1, x2) = PERMC_IN_GG(x1, x2) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U5_GG(x1, x2, x3, x4) = U5_GG(x1, x2, x3, x4) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) U17_GG(x1, x2, x3, x4) = U17_GG(x1, x2, x3, x4) U18_GG(x1, x2, x3, x4) = U18_GG(x1, x2, x3, x4) ORDEREDD_IN_GG(x1, x2) = ORDEREDD_IN_GG(x1, x2) U8_GG(x1, x2, x3, x4) = U8_GG(x1, x2, x3, x4) LESSF_IN_GG(x1, x2) = LESSF_IN_GG(x1, x2) U11_GG(x1, x2, x3) = U11_GG(x1, x2, x3) U9_GG(x1, x2, x3, x4) = U9_GG(x1, x2, x3, x4) U10_GG(x1, x2, x3, x4) = U10_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 22 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) s(x1) = s(x1) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) LESSF_IN_GG(x1, x2) = LESSF_IN_GG(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: LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) 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: LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) 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: *LESSF_IN_GG(s(X1), s(X2)) -> LESSF_IN_GG(X1, X2) 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: ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) s(x1) = s(x1) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) ORDEREDD_IN_GG(x1, x2) = ORDEREDD_IN_GG(x1, x2) U9_GG(x1, x2, x3, x4) = U9_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The TRS R consists of the following rules: lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) 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: ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The TRS R consists of the following rules: lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lesscE_in_gg(x0, x1) U28_gg(x0, x1, x2) lesscF_in_gg(x0, x1) U27_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *U9_GG(X1, X2, X3, lesscE_out_gg(X1, X2)) -> ORDEREDD_IN_GG(X2, X3) The graph contains the following edges 2 >= 1, 4 > 1, 3 >= 2 *ORDEREDD_IN_GG(X1, .(X2, X3)) -> U9_GG(X1, X2, X3, lesscE_in_gg(X1, X2)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) s(x1) = s(x1) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: APPB_IN_GGA(.(X1, X2), X3) -> APPB_IN_GGA(X2, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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_GGA(.(X1, X2), X3) -> APPB_IN_GGA(X2, X3) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> APPA_IN_AGAG(X2, X3, X4, X5) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) s(x1) = s(x1) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) APPA_IN_AGAG(x1, x2, x3, x4) = APPA_IN_AGAG(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_AGAG(.(X1, X2), X3, X4, .(X1, X5)) -> APPA_IN_AGAG(X2, X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPA_IN_AGAG(x1, x2, x3, x4) = APPA_IN_AGAG(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: APPA_IN_AGAG(X3, .(X1, X5)) -> APPA_IN_AGAG(X3, X5) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) 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: *APPA_IN_AGAG(X3, .(X1, X5)) -> APPA_IN_AGAG(X3, X5) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) permcC_in_gg([], []) -> permcC_out_gg([], []) permcC_in_gg(X1, .(X2, X3)) -> U22_gg(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U22_gg(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U23_gg(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U23_gg(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> U24_gg(X1, X2, X3, permcC_in_gg(X6, X3)) U24_gg(X1, X2, X3, permcC_out_gg(X6, X3)) -> permcC_out_gg(X1, .(X2, X3)) lesscE_in_gg(0, X1) -> lesscE_out_gg(0, X1) lesscE_in_gg(s(X1), X2) -> U28_gg(X1, X2, lesscF_in_gg(X1, X2)) lesscF_in_gg(0, s(X1)) -> lesscF_out_gg(0, s(X1)) lesscF_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lesscF_in_gg(X1, X2)) U27_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscF_out_gg(s(X1), s(X2)) U28_gg(X1, X2, lesscF_out_gg(X1, X2)) -> lesscE_out_gg(s(X1), X2) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) permcC_in_gg(x1, x2) = permcC_in_gg(x1, x2) permcC_out_gg(x1, x2) = permcC_out_gg(x1, x2) U22_gg(x1, x2, x3, x4) = U22_gg(x1, x2, x3, x4) U23_gg(x1, x2, x3, x4) = U23_gg(x1, x2, x3, x4) U24_gg(x1, x2, x3, x4) = U24_gg(x1, x2, x3, x4) s(x1) = s(x1) lesscE_in_gg(x1, x2) = lesscE_in_gg(x1, x2) 0 = 0 lesscE_out_gg(x1, x2) = lesscE_out_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) lesscF_in_gg(x1, x2) = lesscF_in_gg(x1, x2) lesscF_out_gg(x1, x2) = lesscF_out_gg(x1, x2) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) PERMC_IN_GG(x1, x2) = PERMC_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (37) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X4, X2, X5, X1)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5, X6)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) The TRS R consists of the following rules: appcA_in_agag([], X1, X2, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(.(X1, X2), X3, X4, .(X1, X5)) -> U20_agag(X1, X2, X3, X4, X5, appcA_in_agag(X2, X3, X4, X5)) appcB_in_gga([], X1, X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U21_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) U20_agag(X1, X2, X3, X4, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) U21_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appcA_in_agag(x1, x2, x3, x4) = appcA_in_agag(x2, x4) appcA_out_agag(x1, x2, x3, x4) = appcA_out_agag(x1, x2, x3, x4) U20_agag(x1, x2, x3, x4, x5, x6) = U20_agag(x1, x3, x5, x6) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) [] = [] appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) U21_gga(x1, x2, x3, x4, x5) = U21_gga(x1, x2, x3, x5) PERMC_IN_GG(x1, x2) = PERMC_IN_GG(x1, x2) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (38) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X2, X1)) U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5)) U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) The TRS R consists of the following rules: appcA_in_agag(X1, .(X1, X2)) -> appcA_out_agag([], X1, X2, .(X1, X2)) appcA_in_agag(X3, .(X1, X5)) -> U20_agag(X1, X3, X5, appcA_in_agag(X3, X5)) appcB_in_gga([], X1) -> appcB_out_gga([], X1, X1) appcB_in_gga(.(X1, X2), X3) -> U21_gga(X1, X2, X3, appcB_in_gga(X2, X3)) U20_agag(X1, X3, X5, appcA_out_agag(X2, X3, X4, X5)) -> appcA_out_agag(.(X1, X2), X3, X4, .(X1, X5)) U21_gga(X1, X2, X3, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) The set Q consists of the following terms: appcA_in_agag(x0, x1) appcB_in_gga(x0, x1) U20_agag(x0, x1, x2, x3) U21_gga(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) 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: *U4_GG(X1, X2, X3, appcA_out_agag(X4, X2, X5, X1)) -> U6_GG(X1, X2, X3, appcB_in_gga(X4, X5)) The graph contains the following edges 1 >= 1, 4 > 1, 2 >= 2, 4 > 2, 3 >= 3 *U6_GG(X1, X2, X3, appcB_out_gga(X4, X5, X6)) -> PERMC_IN_GG(X6, X3) The graph contains the following edges 4 > 1, 3 >= 2 *PERMC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appcA_in_agag(X2, X1)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 ---------------------------------------- (41) YES