5.16/2.24 YES 5.16/2.25 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.16/2.25 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.16/2.25 5.16/2.25 5.16/2.25 Left Termination of the query pattern 5.16/2.25 5.16/2.25 hbal_tree(g,a) 5.16/2.25 5.16/2.25 w.r.t. the given Prolog program could successfully be proven: 5.16/2.25 5.16/2.25 (0) Prolog 5.16/2.25 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 5.16/2.25 (2) TRIPLES 5.16/2.25 (3) TriplesToPiDPProof [SOUND, 0 ms] 5.16/2.25 (4) PiDP 5.16/2.25 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.16/2.25 (6) PiDP 5.16/2.25 (7) PiDPToQDPProof [SOUND, 4 ms] 5.16/2.25 (8) QDP 5.16/2.25 (9) MRRProof [EQUIVALENT, 60 ms] 5.16/2.25 (10) QDP 5.16/2.25 (11) PisEmptyProof [EQUIVALENT, 0 ms] 5.16/2.25 (12) YES 5.16/2.25 5.16/2.25 5.16/2.25 ---------------------------------------- 5.16/2.25 5.16/2.25 (0) 5.16/2.25 Obligation: 5.16/2.25 Clauses: 5.16/2.25 5.16/2.25 hbal_tree(zero, nil). 5.16/2.25 hbal_tree(s(zero), t(x, nil, nil)). 5.16/2.25 hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R))). 5.16/2.25 distr(D1, X1, D1, D1). 5.16/2.25 distr(D1, D2, D1, D2). 5.16/2.25 distr(D1, D2, D2, D1). 5.16/2.25 5.16/2.25 5.16/2.25 Query: hbal_tree(g,a) 5.16/2.25 ---------------------------------------- 5.16/2.25 5.16/2.25 (1) PrologToDTProblemTransformerProof (SOUND) 5.16/2.25 Built DT problem from termination graph DT10. 5.16/2.25 5.16/2.25 { 5.16/2.25 "root": 3, 5.16/2.25 "program": { 5.16/2.25 "directives": [], 5.16/2.25 "clauses": [ 5.16/2.25 [ 5.16/2.25 "(hbal_tree (zero) (nil))", 5.16/2.25 null 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(hbal_tree (s (zero)) (t (x) (nil) (nil)))", 5.16/2.25 null 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(hbal_tree (s (s X)) (t (x) L R))", 5.16/2.25 "(',' (distr (s X) X DL DR) (',' (hbal_tree DL L) (hbal_tree DR R)))" 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(distr D1 X1 D1 D1)", 5.16/2.25 null 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(distr D1 D2 D1 D2)", 5.16/2.25 null 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(distr D1 D2 D2 D1)", 5.16/2.25 null 5.16/2.25 ] 5.16/2.25 ] 5.16/2.25 }, 5.16/2.25 "graph": { 5.16/2.25 "nodes": { 5.16/2.25 "25": { 5.16/2.25 "goal": [ 5.16/2.25 { 5.16/2.25 "clause": 0, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree T1 T2)" 5.16/2.25 }, 5.16/2.25 { 5.16/2.25 "clause": 1, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree T1 T2)" 5.16/2.25 }, 5.16/2.25 { 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree T1 T2)" 5.16/2.25 } 5.16/2.25 ], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T1"], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "type": "Nodes", 5.16/2.25 "130": { 5.16/2.25 "goal": [ 5.16/2.25 { 5.16/2.25 "clause": 1, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree (zero) T2)" 5.16/2.25 }, 5.16/2.25 { 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree (zero) T2)" 5.16/2.25 } 5.16/2.25 ], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "131": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree (zero) T2)" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "132": { 5.16/2.25 "goal": [], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "133": { 5.16/2.25 "goal": [ 5.16/2.25 { 5.16/2.25 "clause": -1, 5.16/2.25 "scope": -1, 5.16/2.25 "term": "(true)" 5.16/2.25 }, 5.16/2.25 { 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree (s (zero)) T2)" 5.16/2.25 } 5.16/2.25 ], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "135": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree T1 T2)" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [ 5.16/2.25 [ 5.16/2.25 "(hbal_tree T1 T2)", 5.16/2.25 "(hbal_tree (zero) (nil))" 5.16/2.25 ], 5.16/2.25 [ 5.16/2.25 "(hbal_tree T1 T2)", 5.16/2.25 "(hbal_tree (s (zero)) (t (x) (nil) (nil)))" 5.16/2.25 ] 5.16/2.25 ], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T1"], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "256": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": 4, 5.16/2.25 "scope": 2, 5.16/2.25 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T6"], 5.16/2.25 "free": [ 5.16/2.25 "X14", 5.16/2.25 "X15" 5.16/2.25 ], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "136": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": 2, 5.16/2.25 "scope": 1, 5.16/2.25 "term": "(hbal_tree (s (zero)) T2)" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "257": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": 5, 5.16/2.25 "scope": 2, 5.16/2.25 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T6"], 5.16/2.25 "free": [ 5.16/2.25 "X14", 5.16/2.25 "X15" 5.16/2.25 ], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "137": { 5.16/2.25 "goal": [], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": [], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "258": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": -1, 5.16/2.25 "scope": -1, 5.16/2.25 "term": "(',' (hbal_tree (s T21) T9) (hbal_tree T21 T10))" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T21"], 5.16/2.25 "free": [], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "138": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": -1, 5.16/2.25 "scope": -1, 5.16/2.25 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.25 }], 5.16/2.25 "kb": { 5.16/2.25 "nonunifying": [], 5.16/2.25 "intvars": {}, 5.16/2.25 "arithmetic": { 5.16/2.25 "type": "PlainIntegerRelationState", 5.16/2.25 "relations": [] 5.16/2.25 }, 5.16/2.25 "ground": ["T6"], 5.16/2.25 "free": [ 5.16/2.25 "X14", 5.16/2.25 "X15" 5.16/2.25 ], 5.16/2.25 "exprvars": [] 5.16/2.25 } 5.16/2.25 }, 5.16/2.25 "259": { 5.16/2.25 "goal": [{ 5.16/2.25 "clause": -1, 5.16/2.25 "scope": -1, 5.16/2.26 "term": "(hbal_tree (s T21) T9)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T21"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "139": { 5.16/2.26 "goal": [], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": [], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "260": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree T21 T22)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T21"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "140": { 5.16/2.26 "goal": [ 5.16/2.26 { 5.16/2.26 "clause": 3, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 4, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 5, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 } 5.16/2.26 ], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T6"], 5.16/2.26 "free": [ 5.16/2.26 "X14", 5.16/2.26 "X15" 5.16/2.26 ], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "261": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(',' (hbal_tree T25 T9) (hbal_tree (s T25) T10))" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T25"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "262": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree T25 T9)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T25"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "142": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": 3, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T6"], 5.16/2.26 "free": [ 5.16/2.26 "X14", 5.16/2.26 "X15" 5.16/2.26 ], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "263": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree (s T25) T26)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T25"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "144": { 5.16/2.26 "goal": [ 5.16/2.26 { 5.16/2.26 "clause": 4, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 5, 5.16/2.26 "scope": 2, 5.16/2.26 "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" 5.16/2.26 } 5.16/2.26 ], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T6"], 5.16/2.26 "free": [ 5.16/2.26 "X14", 5.16/2.26 "X15" 5.16/2.26 ], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "145": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(',' (hbal_tree (s T15) T9) (hbal_tree (s T15) T10))" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T15"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "3": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree T1 T2)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T1"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "146": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree (s T15) T9)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T15"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "147": { 5.16/2.26 "goal": [{ 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(hbal_tree (s T15) T16)" 5.16/2.26 }], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T15"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "127": { 5.16/2.26 "goal": [ 5.16/2.26 { 5.16/2.26 "clause": -1, 5.16/2.26 "scope": -1, 5.16/2.26 "term": "(true)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 1, 5.16/2.26 "scope": 1, 5.16/2.26 "term": "(hbal_tree (zero) T2)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 2, 5.16/2.26 "scope": 1, 5.16/2.26 "term": "(hbal_tree (zero) T2)" 5.16/2.26 } 5.16/2.26 ], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": [], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "129": { 5.16/2.26 "goal": [ 5.16/2.26 { 5.16/2.26 "clause": 1, 5.16/2.26 "scope": 1, 5.16/2.26 "term": "(hbal_tree T1 T2)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "clause": 2, 5.16/2.26 "scope": 1, 5.16/2.26 "term": "(hbal_tree T1 T2)" 5.16/2.26 } 5.16/2.26 ], 5.16/2.26 "kb": { 5.16/2.26 "nonunifying": [[ 5.16/2.26 "(hbal_tree T1 T2)", 5.16/2.26 "(hbal_tree (zero) (nil))" 5.16/2.26 ]], 5.16/2.26 "intvars": {}, 5.16/2.26 "arithmetic": { 5.16/2.26 "type": "PlainIntegerRelationState", 5.16/2.26 "relations": [] 5.16/2.26 }, 5.16/2.26 "ground": ["T1"], 5.16/2.26 "free": [], 5.16/2.26 "exprvars": [] 5.16/2.26 } 5.16/2.26 } 5.16/2.26 }, 5.16/2.26 "edges": [ 5.16/2.26 { 5.16/2.26 "from": 3, 5.16/2.26 "to": 25, 5.16/2.26 "label": "CASE" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 25, 5.16/2.26 "to": 127, 5.16/2.26 "label": "EVAL with clause\nhbal_tree(zero, nil).\nand substitutionT1 -> zero,\nT2 -> nil" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 25, 5.16/2.26 "to": 129, 5.16/2.26 "label": "EVAL-BACKTRACK" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 127, 5.16/2.26 "to": 130, 5.16/2.26 "label": "SUCCESS" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 129, 5.16/2.26 "to": 133, 5.16/2.26 "label": "EVAL with clause\nhbal_tree(s(zero), t(x, nil, nil)).\nand substitutionT1 -> s(zero),\nT2 -> t(x, nil, nil)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 129, 5.16/2.26 "to": 135, 5.16/2.26 "label": "EVAL-BACKTRACK" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 130, 5.16/2.26 "to": 131, 5.16/2.26 "label": "BACKTRACK\nfor clause: hbal_tree(s(zero), t(x, nil, nil))because of non-unification" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 131, 5.16/2.26 "to": 132, 5.16/2.26 "label": "BACKTRACK\nfor clause: hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R)))because of non-unification" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 133, 5.16/2.26 "to": 136, 5.16/2.26 "label": "SUCCESS" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 135, 5.16/2.26 "to": 138, 5.16/2.26 "label": "EVAL with clause\nhbal_tree(s(s(X11)), t(x, X12, X13)) :- ','(distr(s(X11), X11, X14, X15), ','(hbal_tree(X14, X12), hbal_tree(X15, X13))).\nand substitutionX11 -> T6,\nT1 -> s(s(T6)),\nX12 -> T9,\nX13 -> T10,\nT2 -> t(x, T9, T10),\nT7 -> T9,\nT8 -> T10" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 135, 5.16/2.26 "to": 139, 5.16/2.26 "label": "EVAL-BACKTRACK" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 136, 5.16/2.26 "to": 137, 5.16/2.26 "label": "BACKTRACK\nfor clause: hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R)))because of non-unification" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 138, 5.16/2.26 "to": 140, 5.16/2.26 "label": "CASE" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 140, 5.16/2.26 "to": 142, 5.16/2.26 "label": "PARALLEL" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 140, 5.16/2.26 "to": 144, 5.16/2.26 "label": "PARALLEL" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 142, 5.16/2.26 "to": 145, 5.16/2.26 "label": "ONLY EVAL with clause\ndistr(X24, X25, X24, X24).\nand substitutionT6 -> T15,\nX24 -> s(T15),\nX25 -> T15,\nX14 -> s(T15),\nX15 -> s(T15)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 144, 5.16/2.26 "to": 256, 5.16/2.26 "label": "PARALLEL" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 144, 5.16/2.26 "to": 257, 5.16/2.26 "label": "PARALLEL" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 145, 5.16/2.26 "to": 146, 5.16/2.26 "label": "SPLIT 1" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 145, 5.16/2.26 "to": 147, 5.16/2.26 "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nT9 is ground\nreplacements:T10 -> T16" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 146, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> s(T15)\nT2 -> T9" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 147, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> s(T15)\nT2 -> T16" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 256, 5.16/2.26 "to": 258, 5.16/2.26 "label": "ONLY EVAL with clause\ndistr(X34, X35, X34, X35).\nand substitutionT6 -> T21,\nX34 -> s(T21),\nX35 -> T21,\nX14 -> s(T21),\nX15 -> T21" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 257, 5.16/2.26 "to": 261, 5.16/2.26 "label": "ONLY EVAL with clause\ndistr(X40, X41, X41, X40).\nand substitutionT6 -> T25,\nX40 -> s(T25),\nX41 -> T25,\nX14 -> T25,\nX15 -> s(T25)" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 258, 5.16/2.26 "to": 259, 5.16/2.26 "label": "SPLIT 1" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 258, 5.16/2.26 "to": 260, 5.16/2.26 "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT9 is ground\nreplacements:T10 -> T22" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 259, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> s(T21)\nT2 -> T9" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 260, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> T22" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 261, 5.16/2.26 "to": 262, 5.16/2.26 "label": "SPLIT 1" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 261, 5.16/2.26 "to": 263, 5.16/2.26 "label": "SPLIT 2\nnew knowledge:\nT25 is ground\nT9 is ground\nreplacements:T10 -> T26" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 262, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> T25\nT2 -> T9" 5.16/2.26 }, 5.16/2.26 { 5.16/2.26 "from": 263, 5.16/2.26 "to": 3, 5.16/2.26 "label": "INSTANCE with matching:\nT1 -> s(T25)\nT2 -> T26" 5.16/2.26 } 5.16/2.26 ], 5.16/2.26 "type": "Graph" 5.16/2.26 } 5.16/2.26 } 5.16/2.26 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (2) 5.16/2.26 Obligation: 5.16/2.26 Triples: 5.16/2.26 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(s(X1), X2). 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treeA(s(X1), X3)). 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(s(X1), X2). 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treeA(X1, X3)). 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(X1, X2). 5.16/2.26 hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(X1, X2), hbal_treeA(s(X1), X3)). 5.16/2.26 5.16/2.26 Clauses: 5.16/2.26 5.16/2.26 hbal_treecA(zero, nil). 5.16/2.26 hbal_treecA(s(zero), t(x, nil, nil)). 5.16/2.26 hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treecA(s(X1), X3)). 5.16/2.26 hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treecA(X1, X3)). 5.16/2.26 hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(X1, X2), hbal_treecA(s(X1), X3)). 5.16/2.26 5.16/2.26 Afs: 5.16/2.26 5.16/2.26 hbal_treeA(x1, x2) = hbal_treeA(x1) 5.16/2.26 5.16/2.26 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (3) TriplesToPiDPProof (SOUND) 5.16/2.26 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.16/2.26 5.16/2.26 hbal_treeA_in_2: (b,f) 5.16/2.26 5.16/2.26 hbal_treecA_in_2: (b,f) 5.16/2.26 5.16/2.26 Transforming TRIPLES into the following Term Rewriting System: 5.16/2.26 5.16/2.26 Pi DP problem: 5.16/2.26 The TRS P consists of the following rules: 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U1_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X2)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U3_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U5_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X2)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U7_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) 5.16/2.26 U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U4_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X3)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) 5.16/2.26 5.16/2.26 The TRS R consists of the following rules: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) 5.16/2.26 hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) 5.16/2.26 U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 5.16/2.26 The argument filtering Pi contains the following mapping: 5.16/2.26 hbal_treeA_in_ga(x1, x2) = hbal_treeA_in_ga(x1) 5.16/2.26 5.16/2.26 s(x1) = s(x1) 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) 5.16/2.26 5.16/2.26 zero = zero 5.16/2.26 5.16/2.26 hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) 5.16/2.26 5.16/2.26 U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) 5.16/2.26 5.16/2.26 U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) 5.16/2.26 5.16/2.26 U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 t(x1, x2, x3) = t(x1, x2, x3) 5.16/2.26 5.16/2.26 x = x 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) 5.16/2.26 5.16/2.26 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 5.16/2.26 5.16/2.26 U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) 5.16/2.26 5.16/2.26 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) 5.16/2.26 5.16/2.26 U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) 5.16/2.26 5.16/2.26 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) 5.16/2.26 5.16/2.26 U7_GA(x1, x2, x3, x4) = U7_GA(x1, x4) 5.16/2.26 5.16/2.26 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) 5.16/2.26 5.16/2.26 5.16/2.26 We have to consider all (P,R,Pi)-chains 5.16/2.26 5.16/2.26 5.16/2.26 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 5.16/2.26 5.16/2.26 5.16/2.26 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (4) 5.16/2.26 Obligation: 5.16/2.26 Pi DP problem: 5.16/2.26 The TRS P consists of the following rules: 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U1_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X2)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U3_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U5_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X2)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U7_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) 5.16/2.26 U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U4_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X3)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) 5.16/2.26 5.16/2.26 The TRS R consists of the following rules: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) 5.16/2.26 hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) 5.16/2.26 U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 5.16/2.26 The argument filtering Pi contains the following mapping: 5.16/2.26 hbal_treeA_in_ga(x1, x2) = hbal_treeA_in_ga(x1) 5.16/2.26 5.16/2.26 s(x1) = s(x1) 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) 5.16/2.26 5.16/2.26 zero = zero 5.16/2.26 5.16/2.26 hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) 5.16/2.26 5.16/2.26 U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) 5.16/2.26 5.16/2.26 U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) 5.16/2.26 5.16/2.26 U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 t(x1, x2, x3) = t(x1, x2, x3) 5.16/2.26 5.16/2.26 x = x 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) 5.16/2.26 5.16/2.26 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 5.16/2.26 5.16/2.26 U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) 5.16/2.26 5.16/2.26 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) 5.16/2.26 5.16/2.26 U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) 5.16/2.26 5.16/2.26 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) 5.16/2.26 5.16/2.26 U7_GA(x1, x2, x3, x4) = U7_GA(x1, x4) 5.16/2.26 5.16/2.26 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) 5.16/2.26 5.16/2.26 5.16/2.26 We have to consider all (P,R,Pi)-chains 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (5) DependencyGraphProof (EQUIVALENT) 5.16/2.26 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 5 less nodes. 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (6) 5.16/2.26 Obligation: 5.16/2.26 Pi DP problem: 5.16/2.26 The TRS P consists of the following rules: 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) 5.16/2.26 U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) 5.16/2.26 5.16/2.26 The TRS R consists of the following rules: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) 5.16/2.26 hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) 5.16/2.26 U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) 5.16/2.26 U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) 5.16/2.26 U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 5.16/2.26 The argument filtering Pi contains the following mapping: 5.16/2.26 s(x1) = s(x1) 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) 5.16/2.26 5.16/2.26 zero = zero 5.16/2.26 5.16/2.26 hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) 5.16/2.26 5.16/2.26 U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) 5.16/2.26 5.16/2.26 U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) 5.16/2.26 5.16/2.26 U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) 5.16/2.26 5.16/2.26 t(x1, x2, x3) = t(x1, x2, x3) 5.16/2.26 5.16/2.26 x = x 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) 5.16/2.26 5.16/2.26 U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) 5.16/2.26 5.16/2.26 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) 5.16/2.26 5.16/2.26 5.16/2.26 We have to consider all (P,R,Pi)-chains 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (7) PiDPToQDPProof (SOUND) 5.16/2.26 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (8) 5.16/2.26 Obligation: 5.16/2.26 Q DP problem: 5.16/2.26 The TRS P consists of the following rules: 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> U2_GA(X1, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(X1) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> U6_GA(X1, hbal_treecA_in_ga(X1)) 5.16/2.26 U6_GA(X1, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1) 5.16/2.26 5.16/2.26 The TRS R consists of the following rules: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(zero) -> hbal_treecA_out_ga(zero, nil) 5.16/2.26 hbal_treecA_in_ga(s(zero)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1))) -> U9_ga(X1, hbal_treecA_in_ga(s(X1))) 5.16/2.26 hbal_treecA_in_ga(s(s(X1))) -> U12_ga(X1, hbal_treecA_in_ga(X1)) 5.16/2.26 U12_ga(X1, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U13_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U10_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, hbal_treecA_in_ga(X1)) 5.16/2.26 U11_ga(X1, X2, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 5.16/2.26 The set Q consists of the following terms: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(x0) 5.16/2.26 U12_ga(x0, x1) 5.16/2.26 U13_ga(x0, x1, x2) 5.16/2.26 U9_ga(x0, x1) 5.16/2.26 U10_ga(x0, x1, x2) 5.16/2.26 U11_ga(x0, x1, x2) 5.16/2.26 5.16/2.26 We have to consider all (P,Q,R)-chains. 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (9) MRRProof (EQUIVALENT) 5.16/2.26 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.16/2.26 5.16/2.26 Strictly oriented dependency pairs: 5.16/2.26 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> U2_GA(X1, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(X1) 5.16/2.26 HBAL_TREEA_IN_GA(s(s(X1))) -> U6_GA(X1, hbal_treecA_in_ga(X1)) 5.16/2.26 U6_GA(X1, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1)) 5.16/2.26 U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1) 5.16/2.26 5.16/2.26 5.16/2.26 Used ordering: Polynomial interpretation [POLO]: 5.16/2.26 5.16/2.26 POL(HBAL_TREEA_IN_GA(x_1)) = 1 + x_1 5.16/2.26 POL(U10_ga(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 5.16/2.26 POL(U11_ga(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 5.16/2.26 POL(U12_ga(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 5.16/2.26 POL(U13_ga(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 5.16/2.26 POL(U2_GA(x_1, x_2)) = 2*x_1 + x_2 5.16/2.26 POL(U6_GA(x_1, x_2)) = 1 + 2*x_1 + x_2 5.16/2.26 POL(U9_ga(x_1, x_2)) = 2 + 2*x_1 + x_2 5.16/2.26 POL(hbal_treecA_in_ga(x_1)) = 2 + x_1 5.16/2.26 POL(hbal_treecA_out_ga(x_1, x_2)) = 2 + x_1 + 2*x_2 5.16/2.26 POL(nil) = 0 5.16/2.26 POL(s(x_1)) = 1 + 2*x_1 5.16/2.26 POL(t(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 5.16/2.26 POL(x) = 0 5.16/2.26 POL(zero) = 0 5.16/2.26 5.16/2.26 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (10) 5.16/2.26 Obligation: 5.16/2.26 Q DP problem: 5.16/2.26 P is empty. 5.16/2.26 The TRS R consists of the following rules: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(zero) -> hbal_treecA_out_ga(zero, nil) 5.16/2.26 hbal_treecA_in_ga(s(zero)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) 5.16/2.26 hbal_treecA_in_ga(s(s(X1))) -> U9_ga(X1, hbal_treecA_in_ga(s(X1))) 5.16/2.26 hbal_treecA_in_ga(s(s(X1))) -> U12_ga(X1, hbal_treecA_in_ga(X1)) 5.16/2.26 U12_ga(X1, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U13_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, hbal_treecA_in_ga(s(X1))) 5.16/2.26 U10_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, hbal_treecA_in_ga(X1)) 5.16/2.26 U11_ga(X1, X2, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) 5.16/2.26 5.16/2.26 The set Q consists of the following terms: 5.16/2.26 5.16/2.26 hbal_treecA_in_ga(x0) 5.16/2.26 U12_ga(x0, x1) 5.16/2.26 U13_ga(x0, x1, x2) 5.16/2.26 U9_ga(x0, x1) 5.16/2.26 U10_ga(x0, x1, x2) 5.16/2.26 U11_ga(x0, x1, x2) 5.16/2.26 5.16/2.26 We have to consider all (P,Q,R)-chains. 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (11) PisEmptyProof (EQUIVALENT) 5.16/2.26 The TRS P is empty. Hence, there is no (P,Q,R) chain. 5.16/2.26 ---------------------------------------- 5.16/2.26 5.16/2.26 (12) 5.16/2.26 YES 5.45/2.29 EOF