4.33/2.03 YES 4.33/2.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.33/2.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.33/2.05 4.33/2.05 4.33/2.05 Left Termination of the query pattern 4.33/2.05 4.33/2.05 h(g) 4.33/2.05 4.33/2.05 w.r.t. the given Prolog program could successfully be proven: 4.33/2.05 4.33/2.05 (0) Prolog 4.33/2.05 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 4.33/2.05 (2) TRIPLES 4.33/2.05 (3) TriplesToPiDPProof [SOUND, 14 ms] 4.33/2.05 (4) PiDP 4.33/2.05 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.33/2.05 (6) AND 4.33/2.05 (7) PiDP 4.33/2.05 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.33/2.05 (9) PiDP 4.33/2.05 (10) PiDPToQDPProof [EQUIVALENT, 0 ms] 4.33/2.05 (11) QDP 4.33/2.05 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.33/2.05 (13) YES 4.33/2.05 (14) PiDP 4.33/2.05 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.33/2.05 (16) PiDP 4.33/2.05 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 4.33/2.05 (18) QDP 4.33/2.05 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.33/2.05 (20) YES 4.33/2.05 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (0) 4.33/2.05 Obligation: 4.33/2.05 Clauses: 4.33/2.05 4.33/2.05 f(c(s(X), Y)) :- f(c(X, s(Y))). 4.33/2.05 g(c(X, s(Y))) :- g(c(s(X), Y)). 4.33/2.05 h(X) :- ','(f(X), g(X)). 4.33/2.05 4.33/2.05 4.33/2.05 Query: h(g) 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (1) PrologToDTProblemTransformerProof (SOUND) 4.33/2.05 Built DT problem from termination graph DT10. 4.33/2.05 4.33/2.05 { 4.33/2.05 "root": 9, 4.33/2.05 "program": { 4.33/2.05 "directives": [], 4.33/2.05 "clauses": [ 4.33/2.05 [ 4.33/2.05 "(f (c (s X) Y))", 4.33/2.05 "(f (c X (s Y)))" 4.33/2.05 ], 4.33/2.05 [ 4.33/2.05 "(g (c X (s Y)))", 4.33/2.05 "(g (c (s X) Y))" 4.33/2.05 ], 4.33/2.05 [ 4.33/2.05 "(h X)", 4.33/2.05 "(',' (f X) (g X))" 4.33/2.05 ] 4.33/2.05 ] 4.33/2.05 }, 4.33/2.05 "graph": { 4.33/2.05 "nodes": { 4.33/2.05 "99": { 4.33/2.05 "goal": [], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "type": "Nodes", 4.33/2.05 "140": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(g (c (s (s T28)) T29))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T28", 4.33/2.05 "T29" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "130": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(f (c T18 (s (s T19))))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T18", 4.33/2.05 "T19" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "141": { 4.33/2.05 "goal": [], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "132": { 4.33/2.05 "goal": [], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "101": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(f (c T8 (s T9)))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T8", 4.33/2.05 "T9" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "103": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(g (c (s T8) T9))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T8", 4.33/2.05 "T9" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "139": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": 1, 4.33/2.05 "scope": 4, 4.33/2.05 "term": "(g (c (s T8) T9))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T8", 4.33/2.05 "T9" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "129": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": 0, 4.33/2.05 "scope": 3, 4.33/2.05 "term": "(f (c T8 (s T9)))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T8", 4.33/2.05 "T9" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "9": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(h T1)" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": ["T1"], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "95": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(',' (f T3) (g T3))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": ["T3"], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "97": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": 0, 4.33/2.05 "scope": 2, 4.33/2.05 "term": "(',' (f T3) (g T3))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": ["T3"], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "10": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": 2, 4.33/2.05 "scope": 1, 4.33/2.05 "term": "(h T1)" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": ["T1"], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "98": { 4.33/2.05 "goal": [{ 4.33/2.05 "clause": -1, 4.33/2.05 "scope": -1, 4.33/2.05 "term": "(',' (f (c T8 (s T9))) (g (c (s T8) T9)))" 4.33/2.05 }], 4.33/2.05 "kb": { 4.33/2.05 "nonunifying": [], 4.33/2.05 "intvars": {}, 4.33/2.05 "arithmetic": { 4.33/2.05 "type": "PlainIntegerRelationState", 4.33/2.05 "relations": [] 4.33/2.05 }, 4.33/2.05 "ground": [ 4.33/2.05 "T8", 4.33/2.05 "T9" 4.33/2.05 ], 4.33/2.05 "free": [], 4.33/2.05 "exprvars": [] 4.33/2.05 } 4.33/2.05 } 4.33/2.05 }, 4.33/2.05 "edges": [ 4.33/2.05 { 4.33/2.05 "from": 9, 4.33/2.05 "to": 10, 4.33/2.05 "label": "CASE" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 10, 4.33/2.05 "to": 95, 4.33/2.05 "label": "ONLY EVAL with clause\nh(X2) :- ','(f(X2), g(X2)).\nand substitutionT1 -> T3,\nX2 -> T3" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 95, 4.33/2.05 "to": 97, 4.33/2.05 "label": "CASE" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 97, 4.33/2.05 "to": 98, 4.33/2.05 "label": "EVAL with clause\nf(c(s(X7), X8)) :- f(c(X7, s(X8))).\nand substitutionX7 -> T8,\nX8 -> T9,\nT3 -> c(s(T8), T9)" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 97, 4.33/2.05 "to": 99, 4.33/2.05 "label": "EVAL-BACKTRACK" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 98, 4.33/2.05 "to": 101, 4.33/2.05 "label": "SPLIT 1" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 98, 4.33/2.05 "to": 103, 4.33/2.05 "label": "SPLIT 2\nnew knowledge:\nT8 is ground\nT9 is ground" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 101, 4.33/2.05 "to": 129, 4.33/2.05 "label": "CASE" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 103, 4.33/2.05 "to": 139, 4.33/2.05 "label": "CASE" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 129, 4.33/2.05 "to": 130, 4.33/2.05 "label": "EVAL with clause\nf(c(s(X17), X18)) :- f(c(X17, s(X18))).\nand substitutionX17 -> T18,\nT8 -> s(T18),\nT9 -> T19,\nX18 -> s(T19)" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 129, 4.33/2.05 "to": 132, 4.33/2.05 "label": "EVAL-BACKTRACK" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 130, 4.33/2.05 "to": 101, 4.33/2.05 "label": "INSTANCE with matching:\nT8 -> T18\nT9 -> s(T19)" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 139, 4.33/2.05 "to": 140, 4.33/2.05 "label": "EVAL with clause\ng(c(X27, s(X28))) :- g(c(s(X27), X28)).\nand substitutionT8 -> T28,\nX27 -> s(T28),\nX28 -> T29,\nT9 -> s(T29)" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 139, 4.33/2.05 "to": 141, 4.33/2.05 "label": "EVAL-BACKTRACK" 4.33/2.05 }, 4.33/2.05 { 4.33/2.05 "from": 140, 4.33/2.05 "to": 103, 4.33/2.05 "label": "INSTANCE with matching:\nT8 -> s(T28)\nT9 -> T29" 4.33/2.05 } 4.33/2.05 ], 4.33/2.05 "type": "Graph" 4.33/2.05 } 4.33/2.05 } 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (2) 4.33/2.05 Obligation: 4.33/2.05 Triples: 4.33/2.05 4.33/2.05 fA(s(X1), X2) :- fA(X1, s(X2)). 4.33/2.05 gB(X1, s(X2)) :- gB(s(X1), X2). 4.33/2.05 hC(c(s(X1), X2)) :- fA(X1, X2). 4.33/2.05 hC(c(s(X1), X2)) :- ','(fcA(X1, X2), gB(X1, X2)). 4.33/2.05 4.33/2.05 Clauses: 4.33/2.05 4.33/2.05 fcA(s(X1), X2) :- fcA(X1, s(X2)). 4.33/2.05 gcB(X1, s(X2)) :- gcB(s(X1), X2). 4.33/2.05 4.33/2.05 Afs: 4.33/2.05 4.33/2.05 hC(x1) = hC(x1) 4.33/2.05 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (3) TriplesToPiDPProof (SOUND) 4.33/2.05 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.33/2.05 4.33/2.05 hC_in_1: (b) 4.33/2.05 4.33/2.05 fA_in_2: (b,b) 4.33/2.05 4.33/2.05 fcA_in_2: (b,b) 4.33/2.05 4.33/2.05 gB_in_2: (b,b) 4.33/2.05 4.33/2.05 Transforming TRIPLES into the following Term Rewriting System: 4.33/2.05 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> U3_G(X1, X2, fA_in_gg(X1, X2)) 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> FA_IN_GG(X1, X2) 4.33/2.05 FA_IN_GG(s(X1), X2) -> U1_GG(X1, X2, fA_in_gg(X1, s(X2))) 4.33/2.05 FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> U4_G(X1, X2, fcA_in_gg(X1, X2)) 4.33/2.05 U4_G(X1, X2, fcA_out_gg(X1, X2)) -> U5_G(X1, X2, gB_in_gg(X1, X2)) 4.33/2.05 U4_G(X1, X2, fcA_out_gg(X1, X2)) -> GB_IN_GG(X1, X2) 4.33/2.05 GB_IN_GG(X1, s(X2)) -> U2_GG(X1, X2, gB_in_gg(s(X1), X2)) 4.33/2.05 GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 4.33/2.05 The TRS R consists of the following rules: 4.33/2.05 4.33/2.05 fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) 4.33/2.05 U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) 4.33/2.05 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 4.33/2.05 4.33/2.05 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 4.33/2.05 4.33/2.05 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (4) 4.33/2.05 Obligation: 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> U3_G(X1, X2, fA_in_gg(X1, X2)) 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> FA_IN_GG(X1, X2) 4.33/2.05 FA_IN_GG(s(X1), X2) -> U1_GG(X1, X2, fA_in_gg(X1, s(X2))) 4.33/2.05 FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 HC_IN_G(c(s(X1), X2)) -> U4_G(X1, X2, fcA_in_gg(X1, X2)) 4.33/2.05 U4_G(X1, X2, fcA_out_gg(X1, X2)) -> U5_G(X1, X2, gB_in_gg(X1, X2)) 4.33/2.05 U4_G(X1, X2, fcA_out_gg(X1, X2)) -> GB_IN_GG(X1, X2) 4.33/2.05 GB_IN_GG(X1, s(X2)) -> U2_GG(X1, X2, gB_in_gg(s(X1), X2)) 4.33/2.05 GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 4.33/2.05 The TRS R consists of the following rules: 4.33/2.05 4.33/2.05 fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) 4.33/2.05 U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) 4.33/2.05 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (5) DependencyGraphProof (EQUIVALENT) 4.33/2.05 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 7 less nodes. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (6) 4.33/2.05 Complex Obligation (AND) 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (7) 4.33/2.05 Obligation: 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 4.33/2.05 The TRS R consists of the following rules: 4.33/2.05 4.33/2.05 fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) 4.33/2.05 U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) 4.33/2.05 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (8) UsableRulesProof (EQUIVALENT) 4.33/2.05 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (9) 4.33/2.05 Obligation: 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 4.33/2.05 R is empty. 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (10) PiDPToQDPProof (EQUIVALENT) 4.33/2.05 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (11) 4.33/2.05 Obligation: 4.33/2.05 Q DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 4.33/2.05 R is empty. 4.33/2.05 Q is empty. 4.33/2.05 We have to consider all (P,Q,R)-chains. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (12) QDPSizeChangeProof (EQUIVALENT) 4.33/2.05 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. 4.33/2.05 4.33/2.05 From the DPs we obtained the following set of size-change graphs: 4.33/2.05 *GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) 4.33/2.05 The graph contains the following edges 2 > 2 4.33/2.05 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (13) 4.33/2.05 YES 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (14) 4.33/2.05 Obligation: 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 4.33/2.05 The TRS R consists of the following rules: 4.33/2.05 4.33/2.05 fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) 4.33/2.05 U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) 4.33/2.05 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (15) UsableRulesProof (EQUIVALENT) 4.33/2.05 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (16) 4.33/2.05 Obligation: 4.33/2.05 Pi DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 4.33/2.05 R is empty. 4.33/2.05 Pi is empty. 4.33/2.05 We have to consider all (P,R,Pi)-chains 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (17) PiDPToQDPProof (EQUIVALENT) 4.33/2.05 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (18) 4.33/2.05 Obligation: 4.33/2.05 Q DP problem: 4.33/2.05 The TRS P consists of the following rules: 4.33/2.05 4.33/2.05 FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 4.33/2.05 R is empty. 4.33/2.05 Q is empty. 4.33/2.05 We have to consider all (P,Q,R)-chains. 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (19) QDPSizeChangeProof (EQUIVALENT) 4.33/2.05 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. 4.33/2.05 4.33/2.05 From the DPs we obtained the following set of size-change graphs: 4.33/2.05 *FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) 4.33/2.05 The graph contains the following edges 1 > 1 4.33/2.05 4.33/2.05 4.33/2.05 ---------------------------------------- 4.33/2.05 4.33/2.05 (20) 4.33/2.05 YES 4.33/2.08 EOF