3.64/1.63 YES 3.64/1.64 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.64/1.64 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.64/1.64 3.64/1.64 3.64/1.64 Left Termination of the query pattern 3.64/1.64 3.64/1.64 len(g,a) 3.64/1.64 3.64/1.64 w.r.t. the given Prolog program could successfully be proven: 3.64/1.64 3.64/1.64 (0) Prolog 3.64/1.64 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.64/1.64 (2) TRIPLES 3.64/1.64 (3) TriplesToPiDPProof [SOUND, 0 ms] 3.64/1.64 (4) PiDP 3.64/1.64 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.64/1.64 (6) PiDP 3.64/1.64 (7) PiDPToQDPProof [SOUND, 0 ms] 3.64/1.64 (8) QDP 3.64/1.64 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.64/1.64 (10) YES 3.64/1.64 3.64/1.64 3.64/1.64 ---------------------------------------- 3.64/1.64 3.64/1.64 (0) 3.64/1.64 Obligation: 3.64/1.64 Clauses: 3.64/1.64 3.64/1.64 len([], 0). 3.64/1.64 len(.(X1, Ts), s(N)) :- len(Ts, N). 3.64/1.64 3.64/1.64 3.64/1.64 Query: len(g,a) 3.64/1.64 ---------------------------------------- 3.64/1.64 3.64/1.64 (1) PrologToDTProblemTransformerProof (SOUND) 3.64/1.64 Built DT problem from termination graph DT10. 3.64/1.64 3.64/1.64 { 3.64/1.64 "root": 5, 3.64/1.64 "program": { 3.64/1.64 "directives": [], 3.64/1.64 "clauses": [ 3.64/1.64 [ 3.64/1.64 "(len ([]) (0))", 3.64/1.64 null 3.64/1.64 ], 3.64/1.64 [ 3.64/1.64 "(len (. X1 Ts) (s N))", 3.64/1.64 "(len Ts N)" 3.64/1.64 ] 3.64/1.64 ] 3.64/1.64 }, 3.64/1.64 "graph": { 3.64/1.64 "nodes": { 3.64/1.64 "59": { 3.64/1.64 "goal": [{ 3.64/1.64 "clause": -1, 3.64/1.64 "scope": -1, 3.64/1.64 "term": "(len T7 T9)" 3.64/1.64 }], 3.64/1.64 "kb": { 3.64/1.64 "nonunifying": [], 3.64/1.64 "intvars": {}, 3.64/1.64 "arithmetic": { 3.64/1.64 "type": "PlainIntegerRelationState", 3.64/1.64 "relations": [] 3.64/1.64 }, 3.64/1.64 "ground": ["T7"], 3.64/1.64 "free": [], 3.64/1.64 "exprvars": [] 3.64/1.64 } 3.64/1.64 }, 3.64/1.64 "type": "Nodes", 3.64/1.64 "5": { 3.64/1.64 "goal": [{ 3.64/1.64 "clause": -1, 3.64/1.64 "scope": -1, 3.64/1.64 "term": "(len T1 T2)" 3.64/1.64 }], 3.64/1.64 "kb": { 3.64/1.64 "nonunifying": [], 3.64/1.64 "intvars": {}, 3.64/1.64 "arithmetic": { 3.64/1.64 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T1"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "6": { 3.64/1.65 "goal": [ 3.64/1.65 { 3.64/1.65 "clause": 0, 3.64/1.65 "scope": 1, 3.64/1.65 "term": "(len T1 T2)" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 1, 3.64/1.65 "term": "(len T1 T2)" 3.64/1.65 } 3.64/1.65 ], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T1"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "90": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": -1, 3.64/1.65 "scope": -1, 3.64/1.65 "term": "(true)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "91": { 3.64/1.65 "goal": [], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "92": { 3.64/1.65 "goal": [], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "60": { 3.64/1.65 "goal": [], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "93": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": -1, 3.64/1.65 "scope": -1, 3.64/1.65 "term": "(len T17 T19)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T17"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "94": { 3.64/1.65 "goal": [], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "73": { 3.64/1.65 "goal": [ 3.64/1.65 { 3.64/1.65 "clause": 0, 3.64/1.65 "scope": 2, 3.64/1.65 "term": "(len T7 T9)" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 2, 3.64/1.65 "term": "(len T7 T9)" 3.64/1.65 } 3.64/1.65 ], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T7"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "52": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 1, 3.64/1.65 "term": "(len T1 T2)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [[ 3.64/1.65 "(len T1 T2)", 3.64/1.65 "(len ([]) (0))" 3.64/1.65 ]], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T1"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "85": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": 0, 3.64/1.65 "scope": 2, 3.64/1.65 "term": "(len T7 T9)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T7"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "31": { 3.64/1.65 "goal": [ 3.64/1.65 { 3.64/1.65 "clause": -1, 3.64/1.65 "scope": -1, 3.64/1.65 "term": "(true)" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 1, 3.64/1.65 "term": "(len ([]) T2)" 3.64/1.65 } 3.64/1.65 ], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "53": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 1, 3.64/1.65 "term": "(len ([]) T2)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "86": { 3.64/1.65 "goal": [{ 3.64/1.65 "clause": 1, 3.64/1.65 "scope": 2, 3.64/1.65 "term": "(len T7 T9)" 3.64/1.65 }], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": ["T7"], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "54": { 3.64/1.65 "goal": [], 3.64/1.65 "kb": { 3.64/1.65 "nonunifying": [], 3.64/1.65 "intvars": {}, 3.64/1.65 "arithmetic": { 3.64/1.65 "type": "PlainIntegerRelationState", 3.64/1.65 "relations": [] 3.64/1.65 }, 3.64/1.65 "ground": [], 3.64/1.65 "free": [], 3.64/1.65 "exprvars": [] 3.64/1.65 } 3.64/1.65 } 3.64/1.65 }, 3.64/1.65 "edges": [ 3.64/1.65 { 3.64/1.65 "from": 5, 3.64/1.65 "to": 6, 3.64/1.65 "label": "CASE" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 6, 3.64/1.65 "to": 31, 3.64/1.65 "label": "EVAL with clause\nlen([], 0).\nand substitutionT1 -> [],\nT2 -> 0" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 6, 3.64/1.65 "to": 52, 3.64/1.65 "label": "EVAL-BACKTRACK" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 31, 3.64/1.65 "to": 53, 3.64/1.65 "label": "SUCCESS" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 52, 3.64/1.65 "to": 59, 3.64/1.65 "label": "EVAL with clause\nlen(.(X8, X9), s(X10)) :- len(X9, X10).\nand substitutionX8 -> T6,\nX9 -> T7,\nT1 -> .(T6, T7),\nX10 -> T9,\nT2 -> s(T9),\nT8 -> T9" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 52, 3.64/1.65 "to": 60, 3.64/1.65 "label": "EVAL-BACKTRACK" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 53, 3.64/1.65 "to": 54, 3.64/1.65 "label": "BACKTRACK\nfor clause: len(.(X1, Ts), s(N)) :- len(Ts, N)because of non-unification" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 59, 3.64/1.65 "to": 73, 3.64/1.65 "label": "CASE" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 73, 3.64/1.65 "to": 85, 3.64/1.65 "label": "PARALLEL" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 73, 3.64/1.65 "to": 86, 3.64/1.65 "label": "PARALLEL" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 85, 3.64/1.65 "to": 90, 3.64/1.65 "label": "EVAL with clause\nlen([], 0).\nand substitutionT7 -> [],\nT9 -> 0" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 85, 3.64/1.65 "to": 91, 3.64/1.65 "label": "EVAL-BACKTRACK" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 86, 3.64/1.65 "to": 93, 3.64/1.65 "label": "EVAL with clause\nlen(.(X17, X18), s(X19)) :- len(X18, X19).\nand substitutionX17 -> T16,\nX18 -> T17,\nT7 -> .(T16, T17),\nX19 -> T19,\nT9 -> s(T19),\nT18 -> T19" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 86, 3.64/1.65 "to": 94, 3.64/1.65 "label": "EVAL-BACKTRACK" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 90, 3.64/1.65 "to": 92, 3.64/1.65 "label": "SUCCESS" 3.64/1.65 }, 3.64/1.65 { 3.64/1.65 "from": 93, 3.64/1.65 "to": 5, 3.64/1.65 "label": "INSTANCE with matching:\nT1 -> T17\nT2 -> T19" 3.64/1.65 } 3.64/1.65 ], 3.64/1.65 "type": "Graph" 3.64/1.65 } 3.64/1.65 } 3.64/1.65 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (2) 3.64/1.65 Obligation: 3.64/1.65 Triples: 3.64/1.65 3.64/1.65 lenA(.(X1, .(X2, X3)), s(s(X4))) :- lenA(X3, X4). 3.64/1.65 3.64/1.65 Clauses: 3.64/1.65 3.64/1.65 lencA([], 0). 3.64/1.65 lencA(.(X1, []), s(0)). 3.64/1.65 lencA(.(X1, .(X2, X3)), s(s(X4))) :- lencA(X3, X4). 3.64/1.65 3.64/1.65 Afs: 3.64/1.65 3.64/1.65 lenA(x1, x2) = lenA(x1) 3.64/1.65 3.64/1.65 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (3) TriplesToPiDPProof (SOUND) 3.64/1.65 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.64/1.65 3.64/1.65 lenA_in_2: (b,f) 3.64/1.65 3.64/1.65 Transforming TRIPLES into the following Term Rewriting System: 3.64/1.65 3.64/1.65 Pi DP problem: 3.64/1.65 The TRS P consists of the following rules: 3.64/1.65 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3)), s(s(X4))) -> U1_GA(X1, X2, X3, X4, lenA_in_ga(X3, X4)) 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3)), s(s(X4))) -> LENA_IN_GA(X3, X4) 3.64/1.65 3.64/1.65 R is empty. 3.64/1.65 The argument filtering Pi contains the following mapping: 3.64/1.65 lenA_in_ga(x1, x2) = lenA_in_ga(x1) 3.64/1.65 3.64/1.65 .(x1, x2) = .(x1, x2) 3.64/1.65 3.64/1.65 s(x1) = s(x1) 3.64/1.65 3.64/1.65 LENA_IN_GA(x1, x2) = LENA_IN_GA(x1) 3.64/1.65 3.64/1.65 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x3, x5) 3.64/1.65 3.64/1.65 3.64/1.65 We have to consider all (P,R,Pi)-chains 3.64/1.65 3.64/1.65 3.64/1.65 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 3.64/1.65 3.64/1.65 3.64/1.65 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (4) 3.64/1.65 Obligation: 3.64/1.65 Pi DP problem: 3.64/1.65 The TRS P consists of the following rules: 3.64/1.65 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3)), s(s(X4))) -> U1_GA(X1, X2, X3, X4, lenA_in_ga(X3, X4)) 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3)), s(s(X4))) -> LENA_IN_GA(X3, X4) 3.64/1.65 3.64/1.65 R is empty. 3.64/1.65 The argument filtering Pi contains the following mapping: 3.64/1.65 lenA_in_ga(x1, x2) = lenA_in_ga(x1) 3.64/1.65 3.64/1.65 .(x1, x2) = .(x1, x2) 3.64/1.65 3.64/1.65 s(x1) = s(x1) 3.64/1.65 3.64/1.65 LENA_IN_GA(x1, x2) = LENA_IN_GA(x1) 3.64/1.65 3.64/1.65 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x3, x5) 3.64/1.65 3.64/1.65 3.64/1.65 We have to consider all (P,R,Pi)-chains 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (5) DependencyGraphProof (EQUIVALENT) 3.64/1.65 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (6) 3.64/1.65 Obligation: 3.64/1.65 Pi DP problem: 3.64/1.65 The TRS P consists of the following rules: 3.64/1.65 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3)), s(s(X4))) -> LENA_IN_GA(X3, X4) 3.64/1.65 3.64/1.65 R is empty. 3.64/1.65 The argument filtering Pi contains the following mapping: 3.64/1.65 .(x1, x2) = .(x1, x2) 3.64/1.65 3.64/1.65 s(x1) = s(x1) 3.64/1.65 3.64/1.65 LENA_IN_GA(x1, x2) = LENA_IN_GA(x1) 3.64/1.65 3.64/1.65 3.64/1.65 We have to consider all (P,R,Pi)-chains 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (7) PiDPToQDPProof (SOUND) 3.64/1.65 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (8) 3.64/1.65 Obligation: 3.64/1.65 Q DP problem: 3.64/1.65 The TRS P consists of the following rules: 3.64/1.65 3.64/1.65 LENA_IN_GA(.(X1, .(X2, X3))) -> LENA_IN_GA(X3) 3.64/1.65 3.64/1.65 R is empty. 3.64/1.65 Q is empty. 3.64/1.65 We have to consider all (P,Q,R)-chains. 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (9) QDPSizeChangeProof (EQUIVALENT) 3.64/1.65 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. 3.64/1.65 3.64/1.65 From the DPs we obtained the following set of size-change graphs: 3.64/1.65 *LENA_IN_GA(.(X1, .(X2, X3))) -> LENA_IN_GA(X3) 3.64/1.65 The graph contains the following edges 1 > 1 3.64/1.65 3.64/1.65 3.64/1.65 ---------------------------------------- 3.64/1.65 3.64/1.65 (10) 3.64/1.65 YES 3.77/1.70 EOF