6.05/2.36 MAYBE 6.05/2.39 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 6.05/2.39 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.05/2.39 6.05/2.39 6.05/2.39 Left Termination of the query pattern 6.05/2.39 6.05/2.39 append(a,a,a) 6.05/2.39 6.05/2.39 w.r.t. the given Prolog program could not be shown: 6.05/2.39 6.05/2.39 (0) Prolog 6.05/2.39 (1) PrologToTRSTransformerProof [SOUND, 0 ms] 6.05/2.39 (2) QTRS 6.05/2.39 (3) QTRSRRRProof [EQUIVALENT, 27 ms] 6.05/2.39 (4) QTRS 6.05/2.39 (5) QTRSRRRProof [EQUIVALENT, 4 ms] 6.05/2.39 (6) QTRS 6.05/2.39 (7) Overlay + Local Confluence [EQUIVALENT, 0 ms] 6.05/2.39 (8) QTRS 6.05/2.39 (9) DependencyPairsProof [EQUIVALENT, 0 ms] 6.05/2.39 (10) QDP 6.05/2.39 (11) UsableRulesProof [EQUIVALENT, 0 ms] 6.05/2.39 (12) QDP 6.05/2.39 (13) QReductionProof [EQUIVALENT, 0 ms] 6.05/2.39 (14) QDP 6.05/2.39 (15) PrologToPiTRSProof [SOUND, 0 ms] 6.05/2.39 (16) PiTRS 6.05/2.39 (17) DependencyPairsProof [EQUIVALENT, 0 ms] 6.05/2.39 (18) PiDP 6.05/2.39 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 6.05/2.39 (20) PiDP 6.05/2.39 (21) UsableRulesProof [EQUIVALENT, 0 ms] 6.05/2.39 (22) PiDP 6.05/2.39 (23) PiDPToQDPProof [SOUND, 0 ms] 6.05/2.39 (24) QDP 6.05/2.39 (25) PrologToPiTRSProof [SOUND, 0 ms] 6.05/2.39 (26) PiTRS 6.05/2.39 (27) DependencyPairsProof [EQUIVALENT, 0 ms] 6.05/2.39 (28) PiDP 6.05/2.39 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 6.05/2.39 (30) PiDP 6.05/2.39 (31) UsableRulesProof [EQUIVALENT, 0 ms] 6.05/2.39 (32) PiDP 6.05/2.39 (33) PiDPToQDPProof [SOUND, 0 ms] 6.05/2.39 (34) QDP 6.05/2.39 (35) PrologToDTProblemTransformerProof [SOUND, 0 ms] 6.05/2.39 (36) TRIPLES 6.05/2.39 (37) TriplesToPiDPProof [SOUND, 0 ms] 6.05/2.39 (38) PiDP 6.05/2.39 (39) DependencyGraphProof [EQUIVALENT, 0 ms] 6.05/2.39 (40) PiDP 6.05/2.39 (41) PiDPToQDPProof [SOUND, 0 ms] 6.05/2.39 (42) QDP 6.05/2.39 (43) PrologToIRSwTTransformerProof [SOUND, 0 ms] 6.05/2.39 (44) IRSwT 6.05/2.39 (45) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 6.05/2.39 (46) IRSwT 6.05/2.39 (47) IntTRSCompressionProof [EQUIVALENT, 11 ms] 6.05/2.39 (48) IRSwT 6.05/2.39 (49) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 6.05/2.39 (50) IRSwT 6.05/2.39 (51) IRSwTTerminationDigraphProof [EQUIVALENT, 4 ms] 6.05/2.39 (52) IRSwT 6.05/2.39 (53) FilterProof [EQUIVALENT, 0 ms] 6.05/2.39 (54) IntTRS 6.05/2.39 (55) IntTRSNonPeriodicNontermProof [COMPLETE, 7 ms] 6.05/2.39 (56) NO 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (0) 6.05/2.39 Obligation: 6.05/2.39 Clauses: 6.05/2.39 6.05/2.39 append([], L, L). 6.05/2.39 append(.(H, L1), L2, .(H, L3)) :- append(L1, L2, L3). 6.05/2.39 append1([], L, L). 6.05/2.39 append1(.(H, L1), L2, .(H, L3)) :- append1(L1, L2, L3). 6.05/2.39 6.05/2.39 6.05/2.39 Query: append(a,a,a) 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (1) PrologToTRSTransformerProof (SOUND) 6.05/2.39 Transformed Prolog program to TRS. 6.05/2.39 6.05/2.39 { 6.05/2.39 "root": 7, 6.05/2.39 "program": { 6.05/2.39 "directives": [], 6.05/2.39 "clauses": [ 6.05/2.39 [ 6.05/2.39 "(append ([]) L L)", 6.05/2.39 null 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append (. H L1) L2 (. H L3))", 6.05/2.39 "(append L1 L2 L3)" 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append1 ([]) L L)", 6.05/2.39 null 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append1 (. H L1) L2 (. H L3))", 6.05/2.39 "(append1 L1 L2 L3)" 6.05/2.39 ] 6.05/2.39 ] 6.05/2.39 }, 6.05/2.39 "graph": { 6.05/2.39 "nodes": { 6.05/2.39 "13": { 6.05/2.39 "goal": [ 6.05/2.39 { 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "79": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "14": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "69": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(true)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "15": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "7": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "80": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T21 T22 T23)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "81": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "71": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "type": "Nodes" 6.05/2.39 }, 6.05/2.39 "edges": [ 6.05/2.39 { 6.05/2.39 "from": 7, 6.05/2.39 "to": 13, 6.05/2.39 "label": "CASE" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 13, 6.05/2.39 "to": 14, 6.05/2.39 "label": "PARALLEL" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 13, 6.05/2.39 "to": 15, 6.05/2.39 "label": "PARALLEL" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 14, 6.05/2.39 "to": 69, 6.05/2.39 "label": "EVAL with clause\nappend([], X5, X5).\nand substitutionT1 -> [],\nT2 -> T8,\nX5 -> T8,\nT3 -> T8" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 14, 6.05/2.39 "to": 71, 6.05/2.39 "label": "EVAL-BACKTRACK" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 15, 6.05/2.39 "to": 80, 6.05/2.39 "label": "EVAL with clause\nappend(.(X14, X15), X16, .(X14, X17)) :- append(X15, X16, X17).\nand substitutionX14 -> T17,\nX15 -> T21,\nT1 -> .(T17, T21),\nT2 -> T22,\nX16 -> T22,\nX17 -> T23,\nT3 -> .(T17, T23),\nT18 -> T21,\nT19 -> T22,\nT20 -> T23" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 15, 6.05/2.39 "to": 81, 6.05/2.39 "label": "EVAL-BACKTRACK" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 69, 6.05/2.39 "to": 79, 6.05/2.39 "label": "SUCCESS" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 80, 6.05/2.39 "to": 7, 6.05/2.39 "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> T22\nT3 -> T23" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "type": "Graph" 6.05/2.39 } 6.05/2.39 } 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (2) 6.05/2.39 Obligation: 6.05/2.39 Q restricted rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 f7_in -> f7_out1 6.05/2.39 f7_in -> U1(f7_in) 6.05/2.39 U1(f7_out1) -> f7_out1 6.05/2.39 6.05/2.39 Q is empty. 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (3) QTRSRRRProof (EQUIVALENT) 6.05/2.39 Used ordering: 6.05/2.39 Polynomial interpretation [POLO]: 6.05/2.39 6.05/2.39 POL(U1(x_1)) = x_1 6.05/2.39 POL(f7_in) = 2 6.05/2.39 POL(f7_out1) = 0 6.05/2.39 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.05/2.39 6.05/2.39 f7_in -> f7_out1 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (4) 6.05/2.39 Obligation: 6.05/2.39 Q restricted rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 f7_in -> U1(f7_in) 6.05/2.39 U1(f7_out1) -> f7_out1 6.05/2.39 6.05/2.39 Q is empty. 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (5) QTRSRRRProof (EQUIVALENT) 6.05/2.39 Used ordering: 6.05/2.39 Polynomial interpretation [POLO]: 6.05/2.39 6.05/2.39 POL(U1(x_1)) = 2*x_1 6.05/2.39 POL(f7_in) = 0 6.05/2.39 POL(f7_out1) = 1 6.05/2.39 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.05/2.39 6.05/2.39 U1(f7_out1) -> f7_out1 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (6) 6.05/2.39 Obligation: 6.05/2.39 Q restricted rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 f7_in -> U1(f7_in) 6.05/2.39 6.05/2.39 Q is empty. 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (7) Overlay + Local Confluence (EQUIVALENT) 6.05/2.39 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (8) 6.05/2.39 Obligation: 6.05/2.39 Q restricted rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 f7_in -> U1(f7_in) 6.05/2.39 6.05/2.39 The set Q consists of the following terms: 6.05/2.39 6.05/2.39 f7_in 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (9) DependencyPairsProof (EQUIVALENT) 6.05/2.39 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (10) 6.05/2.39 Obligation: 6.05/2.39 Q DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 F7_IN -> F7_IN 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 f7_in -> U1(f7_in) 6.05/2.39 6.05/2.39 The set Q consists of the following terms: 6.05/2.39 6.05/2.39 f7_in 6.05/2.39 6.05/2.39 We have to consider all minimal (P,Q,R)-chains. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (11) UsableRulesProof (EQUIVALENT) 6.05/2.39 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (12) 6.05/2.39 Obligation: 6.05/2.39 Q DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 F7_IN -> F7_IN 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 The set Q consists of the following terms: 6.05/2.39 6.05/2.39 f7_in 6.05/2.39 6.05/2.39 We have to consider all minimal (P,Q,R)-chains. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (13) QReductionProof (EQUIVALENT) 6.05/2.39 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.05/2.39 6.05/2.39 f7_in 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (14) 6.05/2.39 Obligation: 6.05/2.39 Q DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 F7_IN -> F7_IN 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 Q is empty. 6.05/2.39 We have to consider all minimal (P,Q,R)-chains. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (15) PrologToPiTRSProof (SOUND) 6.05/2.39 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 6.05/2.39 6.05/2.39 append_in_3: (f,f,f) 6.05/2.39 6.05/2.39 Transforming Prolog into the following Term Rewriting System: 6.05/2.39 6.05/2.39 Pi-finite rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (16) 6.05/2.39 Obligation: 6.05/2.39 Pi-finite rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (17) DependencyPairsProof (EQUIVALENT) 6.05/2.39 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (18) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (19) DependencyGraphProof (EQUIVALENT) 6.05/2.39 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (20) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (21) UsableRulesProof (EQUIVALENT) 6.05/2.39 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (22) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (23) PiDPToQDPProof (SOUND) 6.05/2.39 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (24) 6.05/2.39 Obligation: 6.05/2.39 Q DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA -> APPEND_IN_AAA 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 Q is empty. 6.05/2.39 We have to consider all (P,Q,R)-chains. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (25) PrologToPiTRSProof (SOUND) 6.05/2.39 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 6.05/2.39 6.05/2.39 append_in_3: (f,f,f) 6.05/2.39 6.05/2.39 Transforming Prolog into the following Term Rewriting System: 6.05/2.39 6.05/2.39 Pi-finite rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (26) 6.05/2.39 Obligation: 6.05/2.39 Pi-finite rewrite system: 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 6.05/2.39 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (27) DependencyPairsProof (EQUIVALENT) 6.05/2.39 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (28) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> U1_AAA(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 U1_AAA(x1, x2, x3, x4, x5) = U1_AAA(x5) 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (29) DependencyGraphProof (EQUIVALENT) 6.05/2.39 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (30) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 The TRS R consists of the following rules: 6.05/2.39 6.05/2.39 append_in_aaa([], L, L) -> append_out_aaa([], L, L) 6.05/2.39 append_in_aaa(.(H, L1), L2, .(H, L3)) -> U1_aaa(H, L1, L2, L3, append_in_aaa(L1, L2, L3)) 6.05/2.39 U1_aaa(H, L1, L2, L3, append_out_aaa(L1, L2, L3)) -> append_out_aaa(.(H, L1), L2, .(H, L3)) 6.05/2.39 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 append_in_aaa(x1, x2, x3) = append_in_aaa 6.05/2.39 6.05/2.39 append_out_aaa(x1, x2, x3) = append_out_aaa(x1) 6.05/2.39 6.05/2.39 U1_aaa(x1, x2, x3, x4, x5) = U1_aaa(x5) 6.05/2.39 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (31) UsableRulesProof (EQUIVALENT) 6.05/2.39 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (32) 6.05/2.39 Obligation: 6.05/2.39 Pi DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_AAA(L1, L2, L3) 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 The argument filtering Pi contains the following mapping: 6.05/2.39 .(x1, x2) = .(x2) 6.05/2.39 6.05/2.39 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 6.05/2.39 6.05/2.39 6.05/2.39 We have to consider all (P,R,Pi)-chains 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (33) PiDPToQDPProof (SOUND) 6.05/2.39 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (34) 6.05/2.39 Obligation: 6.05/2.39 Q DP problem: 6.05/2.39 The TRS P consists of the following rules: 6.05/2.39 6.05/2.39 APPEND_IN_AAA -> APPEND_IN_AAA 6.05/2.39 6.05/2.39 R is empty. 6.05/2.39 Q is empty. 6.05/2.39 We have to consider all (P,Q,R)-chains. 6.05/2.39 ---------------------------------------- 6.05/2.39 6.05/2.39 (35) PrologToDTProblemTransformerProof (SOUND) 6.05/2.39 Built DT problem from termination graph DT10. 6.05/2.39 6.05/2.39 { 6.05/2.39 "root": 4, 6.05/2.39 "program": { 6.05/2.39 "directives": [], 6.05/2.39 "clauses": [ 6.05/2.39 [ 6.05/2.39 "(append ([]) L L)", 6.05/2.39 null 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append (. H L1) L2 (. H L3))", 6.05/2.39 "(append L1 L2 L3)" 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append1 ([]) L L)", 6.05/2.39 null 6.05/2.39 ], 6.05/2.39 [ 6.05/2.39 "(append1 (. H L1) L2 (. H L3))", 6.05/2.39 "(append1 L1 L2 L3)" 6.05/2.39 ] 6.05/2.39 ] 6.05/2.39 }, 6.05/2.39 "graph": { 6.05/2.39 "nodes": { 6.05/2.39 "89": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T14 T15 T16)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "type": "Nodes", 6.05/2.39 "158": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T67 T68 T69)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "159": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "90": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "91": { 6.05/2.39 "goal": [ 6.05/2.39 { 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 2, 6.05/2.39 "term": "(append T14 T15 T16)" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 2, 6.05/2.39 "term": "(append T14 T15 T16)" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "70": { 6.05/2.39 "goal": [ 6.05/2.39 { 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(true)" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "92": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 2, 6.05/2.39 "term": "(append T14 T15 T16)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "93": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 2, 6.05/2.39 "term": "(append T14 T15 T16)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "94": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(true)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "73": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [[ 6.05/2.39 "(append T1 T2 T3)", 6.05/2.39 "(append ([]) X2 X2)" 6.05/2.39 ]], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": ["X2"], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "95": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "96": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "97": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T34 T35 T36)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "100": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "101": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T47 T48 T49)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "102": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "4": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "103": { 6.05/2.39 "goal": [ 6.05/2.39 { 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 3, 6.05/2.39 "term": "(append T47 T48 T49)" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 3, 6.05/2.39 "term": "(append T47 T48 T49)" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "104": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 3, 6.05/2.39 "term": "(append T47 T48 T49)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "6": { 6.05/2.39 "goal": [ 6.05/2.39 { 6.05/2.39 "clause": 0, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 } 6.05/2.39 ], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "105": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 3, 6.05/2.39 "term": "(append T47 T48 T49)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "106": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": -1, 6.05/2.39 "scope": -1, 6.05/2.39 "term": "(true)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "107": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "108": { 6.05/2.39 "goal": [], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "87": { 6.05/2.39 "goal": [{ 6.05/2.39 "clause": 1, 6.05/2.39 "scope": 1, 6.05/2.39 "term": "(append T1 T2 T3)" 6.05/2.39 }], 6.05/2.39 "kb": { 6.05/2.39 "nonunifying": [], 6.05/2.39 "intvars": {}, 6.05/2.39 "arithmetic": { 6.05/2.39 "type": "PlainIntegerRelationState", 6.05/2.39 "relations": [] 6.05/2.39 }, 6.05/2.39 "ground": [], 6.05/2.39 "free": [], 6.05/2.39 "exprvars": [] 6.05/2.39 } 6.05/2.39 } 6.05/2.39 }, 6.05/2.39 "edges": [ 6.05/2.39 { 6.05/2.39 "from": 4, 6.05/2.39 "to": 6, 6.05/2.39 "label": "CASE" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 6, 6.05/2.39 "to": 70, 6.05/2.39 "label": "EVAL with clause\nappend([], X2, X2).\nand substitutionT1 -> [],\nT2 -> T5,\nX2 -> T5,\nT3 -> T5" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 6, 6.05/2.39 "to": 73, 6.05/2.39 "label": "EVAL-BACKTRACK" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 70, 6.05/2.39 "to": 87, 6.05/2.39 "label": "SUCCESS" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 73, 6.05/2.39 "to": 101, 6.05/2.39 "label": "EVAL with clause\nappend(.(X34, X35), X36, .(X34, X37)) :- append(X35, X36, X37).\nand substitutionX34 -> T43,\nX35 -> T47,\nT1 -> .(T43, T47),\nT2 -> T48,\nX36 -> T48,\nX37 -> T49,\nT3 -> .(T43, T49),\nT44 -> T47,\nT45 -> T48,\nT46 -> T49" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 73, 6.05/2.39 "to": 102, 6.05/2.39 "label": "EVAL-BACKTRACK" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 87, 6.05/2.39 "to": 89, 6.05/2.39 "label": "EVAL with clause\nappend(.(X7, X8), X9, .(X7, X10)) :- append(X8, X9, X10).\nand substitutionX7 -> T10,\nX8 -> T14,\nT1 -> .(T10, T14),\nT2 -> T15,\nX9 -> T15,\nX10 -> T16,\nT3 -> .(T10, T16),\nT11 -> T14,\nT12 -> T15,\nT13 -> T16" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 87, 6.05/2.39 "to": 90, 6.05/2.39 "label": "EVAL-BACKTRACK" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 89, 6.05/2.39 "to": 91, 6.05/2.39 "label": "CASE" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 91, 6.05/2.39 "to": 92, 6.05/2.39 "label": "PARALLEL" 6.05/2.39 }, 6.05/2.39 { 6.05/2.39 "from": 91, 6.05/2.39 "to": 93, 6.05/2.39 "label": "PARALLEL" 6.05/2.39 }, 6.05/2.39 { 6.05/2.40 "from": 92, 6.05/2.40 "to": 94, 6.05/2.40 "label": "EVAL with clause\nappend([], X15, X15).\nand substitutionT14 -> [],\nT15 -> T21,\nX15 -> T21,\nT16 -> T21" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 92, 6.05/2.40 "to": 95, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 93, 6.05/2.40 "to": 97, 6.05/2.40 "label": "EVAL with clause\nappend(.(X24, X25), X26, .(X24, X27)) :- append(X25, X26, X27).\nand substitutionX24 -> T30,\nX25 -> T34,\nT14 -> .(T30, T34),\nT15 -> T35,\nX26 -> T35,\nX27 -> T36,\nT16 -> .(T30, T36),\nT31 -> T34,\nT32 -> T35,\nT33 -> T36" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 93, 6.05/2.40 "to": 100, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 94, 6.05/2.40 "to": 96, 6.05/2.40 "label": "SUCCESS" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 97, 6.05/2.40 "to": 4, 6.05/2.40 "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T35\nT3 -> T36" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 101, 6.05/2.40 "to": 103, 6.05/2.40 "label": "CASE" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 103, 6.05/2.40 "to": 104, 6.05/2.40 "label": "PARALLEL" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 103, 6.05/2.40 "to": 105, 6.05/2.40 "label": "PARALLEL" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 104, 6.05/2.40 "to": 106, 6.05/2.40 "label": "EVAL with clause\nappend([], X42, X42).\nand substitutionT47 -> [],\nT48 -> T54,\nX42 -> T54,\nT49 -> T54" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 104, 6.05/2.40 "to": 107, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 105, 6.05/2.40 "to": 158, 6.05/2.40 "label": "EVAL with clause\nappend(.(X51, X52), X53, .(X51, X54)) :- append(X52, X53, X54).\nand substitutionX51 -> T63,\nX52 -> T67,\nT47 -> .(T63, T67),\nT48 -> T68,\nX53 -> T68,\nX54 -> T69,\nT49 -> .(T63, T69),\nT64 -> T67,\nT65 -> T68,\nT66 -> T69" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 105, 6.05/2.40 "to": 159, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 106, 6.05/2.40 "to": 108, 6.05/2.40 "label": "SUCCESS" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 158, 6.05/2.40 "to": 4, 6.05/2.40 "label": "INSTANCE with matching:\nT1 -> T67\nT2 -> T68\nT3 -> T69" 6.05/2.40 } 6.05/2.40 ], 6.05/2.40 "type": "Graph" 6.05/2.40 } 6.05/2.40 } 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (36) 6.05/2.40 Obligation: 6.05/2.40 Triples: 6.05/2.40 6.05/2.40 appendA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appendA(X3, X4, X5). 6.05/2.40 appendA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appendA(X3, X4, X5). 6.05/2.40 6.05/2.40 Clauses: 6.05/2.40 6.05/2.40 appendcA([], X1, X1). 6.05/2.40 appendcA(.(X1, []), X2, .(X1, X2)). 6.05/2.40 appendcA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appendcA(X3, X4, X5). 6.05/2.40 appendcA(.(X1, []), X2, .(X1, X2)). 6.05/2.40 appendcA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appendcA(X3, X4, X5). 6.05/2.40 6.05/2.40 Afs: 6.05/2.40 6.05/2.40 appendA(x1, x2, x3) = appendA 6.05/2.40 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (37) TriplesToPiDPProof (SOUND) 6.05/2.40 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 6.05/2.40 6.05/2.40 appendA_in_3: (f,f,f) 6.05/2.40 6.05/2.40 Transforming TRIPLES into the following Term Rewriting System: 6.05/2.40 6.05/2.40 Pi DP problem: 6.05/2.40 The TRS P consists of the following rules: 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> U1_AAA(X1, X2, X3, X4, X5, appendA_in_aaa(X3, X4, X5)) 6.05/2.40 APPENDA_IN_AAA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPENDA_IN_AAA(X3, X4, X5) 6.05/2.40 6.05/2.40 R is empty. 6.05/2.40 The argument filtering Pi contains the following mapping: 6.05/2.40 appendA_in_aaa(x1, x2, x3) = appendA_in_aaa 6.05/2.40 6.05/2.40 .(x1, x2) = .(x2) 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(x1, x2, x3) = APPENDA_IN_AAA 6.05/2.40 6.05/2.40 U1_AAA(x1, x2, x3, x4, x5, x6) = U1_AAA(x6) 6.05/2.40 6.05/2.40 6.05/2.40 We have to consider all (P,R,Pi)-chains 6.05/2.40 6.05/2.40 6.05/2.40 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 6.05/2.40 6.05/2.40 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (38) 6.05/2.40 Obligation: 6.05/2.40 Pi DP problem: 6.05/2.40 The TRS P consists of the following rules: 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> U1_AAA(X1, X2, X3, X4, X5, appendA_in_aaa(X3, X4, X5)) 6.05/2.40 APPENDA_IN_AAA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPENDA_IN_AAA(X3, X4, X5) 6.05/2.40 6.05/2.40 R is empty. 6.05/2.40 The argument filtering Pi contains the following mapping: 6.05/2.40 appendA_in_aaa(x1, x2, x3) = appendA_in_aaa 6.05/2.40 6.05/2.40 .(x1, x2) = .(x2) 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(x1, x2, x3) = APPENDA_IN_AAA 6.05/2.40 6.05/2.40 U1_AAA(x1, x2, x3, x4, x5, x6) = U1_AAA(x6) 6.05/2.40 6.05/2.40 6.05/2.40 We have to consider all (P,R,Pi)-chains 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (39) DependencyGraphProof (EQUIVALENT) 6.05/2.40 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (40) 6.05/2.40 Obligation: 6.05/2.40 Pi DP problem: 6.05/2.40 The TRS P consists of the following rules: 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPENDA_IN_AAA(X3, X4, X5) 6.05/2.40 6.05/2.40 R is empty. 6.05/2.40 The argument filtering Pi contains the following mapping: 6.05/2.40 .(x1, x2) = .(x2) 6.05/2.40 6.05/2.40 APPENDA_IN_AAA(x1, x2, x3) = APPENDA_IN_AAA 6.05/2.40 6.05/2.40 6.05/2.40 We have to consider all (P,R,Pi)-chains 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (41) PiDPToQDPProof (SOUND) 6.05/2.40 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (42) 6.05/2.40 Obligation: 6.05/2.40 Q DP problem: 6.05/2.40 The TRS P consists of the following rules: 6.05/2.40 6.05/2.40 APPENDA_IN_AAA -> APPENDA_IN_AAA 6.05/2.40 6.05/2.40 R is empty. 6.05/2.40 Q is empty. 6.05/2.40 We have to consider all (P,Q,R)-chains. 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (43) PrologToIRSwTTransformerProof (SOUND) 6.05/2.40 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 6.05/2.40 6.05/2.40 { 6.05/2.40 "root": 3, 6.05/2.40 "program": { 6.05/2.40 "directives": [], 6.05/2.40 "clauses": [ 6.05/2.40 [ 6.05/2.40 "(append ([]) L L)", 6.05/2.40 null 6.05/2.40 ], 6.05/2.40 [ 6.05/2.40 "(append (. H L1) L2 (. H L3))", 6.05/2.40 "(append L1 L2 L3)" 6.05/2.40 ], 6.05/2.40 [ 6.05/2.40 "(append1 ([]) L L)", 6.05/2.40 null 6.05/2.40 ], 6.05/2.40 [ 6.05/2.40 "(append1 (. H L1) L2 (. H L3))", 6.05/2.40 "(append1 L1 L2 L3)" 6.05/2.40 ] 6.05/2.40 ] 6.05/2.40 }, 6.05/2.40 "graph": { 6.05/2.40 "nodes": { 6.05/2.40 "88": { 6.05/2.40 "goal": [], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "68": { 6.05/2.40 "goal": [{ 6.05/2.40 "clause": -1, 6.05/2.40 "scope": -1, 6.05/2.40 "term": "(true)" 6.05/2.40 }], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "3": { 6.05/2.40 "goal": [{ 6.05/2.40 "clause": -1, 6.05/2.40 "scope": -1, 6.05/2.40 "term": "(append T1 T2 T3)" 6.05/2.40 }], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "25": { 6.05/2.40 "goal": [{ 6.05/2.40 "clause": 0, 6.05/2.40 "scope": 1, 6.05/2.40 "term": "(append T1 T2 T3)" 6.05/2.40 }], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "5": { 6.05/2.40 "goal": [ 6.05/2.40 { 6.05/2.40 "clause": 0, 6.05/2.40 "scope": 1, 6.05/2.40 "term": "(append T1 T2 T3)" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "clause": 1, 6.05/2.40 "scope": 1, 6.05/2.40 "term": "(append T1 T2 T3)" 6.05/2.40 } 6.05/2.40 ], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "28": { 6.05/2.40 "goal": [{ 6.05/2.40 "clause": 1, 6.05/2.40 "scope": 1, 6.05/2.40 "term": "(append T1 T2 T3)" 6.05/2.40 }], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "72": { 6.05/2.40 "goal": [], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "type": "Nodes", 6.05/2.40 "85": { 6.05/2.40 "goal": [], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "86": { 6.05/2.40 "goal": [{ 6.05/2.40 "clause": -1, 6.05/2.40 "scope": -1, 6.05/2.40 "term": "(append T21 T22 T23)" 6.05/2.40 }], 6.05/2.40 "kb": { 6.05/2.40 "nonunifying": [], 6.05/2.40 "intvars": {}, 6.05/2.40 "arithmetic": { 6.05/2.40 "type": "PlainIntegerRelationState", 6.05/2.40 "relations": [] 6.05/2.40 }, 6.05/2.40 "ground": [], 6.05/2.40 "free": [], 6.05/2.40 "exprvars": [] 6.05/2.40 } 6.05/2.40 } 6.05/2.40 }, 6.05/2.40 "edges": [ 6.05/2.40 { 6.05/2.40 "from": 3, 6.05/2.40 "to": 5, 6.05/2.40 "label": "CASE" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 5, 6.05/2.40 "to": 25, 6.05/2.40 "label": "PARALLEL" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 5, 6.05/2.40 "to": 28, 6.05/2.40 "label": "PARALLEL" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 25, 6.05/2.40 "to": 68, 6.05/2.40 "label": "EVAL with clause\nappend([], X5, X5).\nand substitutionT1 -> [],\nT2 -> T8,\nX5 -> T8,\nT3 -> T8" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 25, 6.05/2.40 "to": 72, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 28, 6.05/2.40 "to": 86, 6.05/2.40 "label": "EVAL with clause\nappend(.(X14, X15), X16, .(X14, X17)) :- append(X15, X16, X17).\nand substitutionX14 -> T17,\nX15 -> T21,\nT1 -> .(T17, T21),\nT2 -> T22,\nX16 -> T22,\nX17 -> T23,\nT3 -> .(T17, T23),\nT18 -> T21,\nT19 -> T22,\nT20 -> T23" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 28, 6.05/2.40 "to": 88, 6.05/2.40 "label": "EVAL-BACKTRACK" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 68, 6.05/2.40 "to": 85, 6.05/2.40 "label": "SUCCESS" 6.05/2.40 }, 6.05/2.40 { 6.05/2.40 "from": 86, 6.05/2.40 "to": 3, 6.05/2.40 "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> T22\nT3 -> T23" 6.05/2.40 } 6.05/2.40 ], 6.05/2.40 "type": "Graph" 6.05/2.40 } 6.05/2.40 } 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (44) 6.05/2.40 Obligation: 6.05/2.40 Rules: 6.05/2.40 f5_in -> f28_in :|: TRUE 6.05/2.40 f28_out -> f5_out :|: TRUE 6.05/2.40 f5_in -> f25_in :|: TRUE 6.05/2.40 f25_out -> f5_out :|: TRUE 6.05/2.40 f3_out -> f86_out :|: TRUE 6.05/2.40 f86_in -> f3_in :|: TRUE 6.05/2.40 f28_in -> f86_in :|: TRUE 6.05/2.40 f28_in -> f88_in :|: TRUE 6.05/2.40 f88_out -> f28_out :|: TRUE 6.05/2.40 f86_out -> f28_out :|: TRUE 6.05/2.40 f3_in -> f5_in :|: TRUE 6.05/2.40 f5_out -> f3_out :|: TRUE 6.05/2.40 Start term: f3_in 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (45) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 6.05/2.40 Constructed simple dependency graph. 6.05/2.40 6.05/2.40 Simplified to the following IRSwTs: 6.05/2.40 6.05/2.40 intTRSProblem: 6.05/2.40 f5_in -> f28_in :|: TRUE 6.05/2.40 f86_in -> f3_in :|: TRUE 6.05/2.40 f28_in -> f86_in :|: TRUE 6.05/2.40 f3_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (46) 6.05/2.40 Obligation: 6.05/2.40 Rules: 6.05/2.40 f5_in -> f28_in :|: TRUE 6.05/2.40 f86_in -> f3_in :|: TRUE 6.05/2.40 f28_in -> f86_in :|: TRUE 6.05/2.40 f3_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (47) IntTRSCompressionProof (EQUIVALENT) 6.05/2.40 Compressed rules. 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (48) 6.05/2.40 Obligation: 6.05/2.40 Rules: 6.05/2.40 f5_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (49) IRSFormatTransformerProof (EQUIVALENT) 6.05/2.40 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (50) 6.05/2.40 Obligation: 6.05/2.40 Rules: 6.05/2.40 f5_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (51) IRSwTTerminationDigraphProof (EQUIVALENT) 6.05/2.40 Constructed termination digraph! 6.05/2.40 Nodes: 6.05/2.40 (1) f5_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 Arcs: 6.05/2.40 (1) -> (1) 6.05/2.40 6.05/2.40 This digraph is fully evaluated! 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (52) 6.05/2.40 Obligation: 6.05/2.40 6.05/2.40 Termination digraph: 6.05/2.40 Nodes: 6.05/2.40 (1) f5_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 Arcs: 6.05/2.40 (1) -> (1) 6.05/2.40 6.05/2.40 This digraph is fully evaluated! 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (53) FilterProof (EQUIVALENT) 6.05/2.40 Used the following sort dictionary for filtering: 6.05/2.40 f5_in() 6.05/2.40 Replaced non-predefined constructor symbols by 0. 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (54) 6.05/2.40 Obligation: 6.05/2.40 Rules: 6.05/2.40 f5_in -> f5_in :|: TRUE 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (55) IntTRSNonPeriodicNontermProof (COMPLETE) 6.05/2.40 Normalized system to the following form: 6.05/2.40 f(pc) -> f(1) :|: pc = 1 && TRUE 6.05/2.40 Proved unsatisfiability of the following formula, indicating that the system is never left after entering: 6.05/2.40 ((run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) 6.05/2.40 Proved satisfiability of the following formula, indicating that the system is entered at least once: 6.05/2.40 (run2_0 = ((1 * 1)) and (((run1_0 * 1)) = ((1 * 1)) and T)) 6.05/2.40 6.05/2.40 ---------------------------------------- 6.05/2.40 6.05/2.40 (56) 6.05/2.40 NO 6.05/2.44 EOF