8.34/3.06 MAYBE 8.34/3.08 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 8.34/3.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.34/3.08 8.34/3.08 8.34/3.08 Left Termination of the query pattern 8.34/3.08 8.34/3.08 p(g) 8.34/3.08 8.34/3.08 w.r.t. the given Prolog program could not be shown: 8.34/3.08 8.34/3.08 (0) Prolog 8.34/3.08 (1) PrologToPiTRSProof [SOUND, 0 ms] 8.34/3.08 (2) PiTRS 8.34/3.08 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.34/3.08 (4) PiDP 8.34/3.08 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.34/3.08 (6) PiDP 8.34/3.08 (7) UsableRulesProof [EQUIVALENT, 0 ms] 8.34/3.08 (8) PiDP 8.34/3.08 (9) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.34/3.08 (10) QDP 8.34/3.08 (11) TransformationProof [EQUIVALENT, 0 ms] 8.34/3.08 (12) QDP 8.34/3.08 (13) NonTerminationLoopProof [COMPLETE, 3 ms] 8.34/3.08 (14) NO 8.34/3.08 (15) PrologToTRSTransformerProof [SOUND, 0 ms] 8.34/3.08 (16) QTRS 8.34/3.08 (17) QTRSRRRProof [EQUIVALENT, 42 ms] 8.34/3.08 (18) QTRS 8.34/3.08 (19) QTRSRRRProof [EQUIVALENT, 4 ms] 8.34/3.08 (20) QTRS 8.34/3.08 (21) Overlay + Local Confluence [EQUIVALENT, 0 ms] 8.34/3.08 (22) QTRS 8.34/3.08 (23) DependencyPairsProof [EQUIVALENT, 0 ms] 8.34/3.08 (24) QDP 8.34/3.08 (25) UsableRulesProof [EQUIVALENT, 0 ms] 8.34/3.08 (26) QDP 8.34/3.08 (27) QReductionProof [EQUIVALENT, 0 ms] 8.34/3.08 (28) QDP 8.34/3.08 (29) TransformationProof [EQUIVALENT, 0 ms] 8.34/3.08 (30) QDP 8.34/3.08 (31) NonTerminationLoopProof [COMPLETE, 0 ms] 8.34/3.08 (32) NO 8.34/3.08 (33) PrologToIRSwTTransformerProof [SOUND, 0 ms] 8.34/3.08 (34) IRSwT 8.34/3.08 (35) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 8.34/3.08 (36) IRSwT 8.34/3.08 (37) IntTRSCompressionProof [EQUIVALENT, 55 ms] 8.34/3.08 (38) IRSwT 8.34/3.08 (39) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.34/3.08 (40) IRSwT 8.34/3.08 (41) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] 8.34/3.08 (42) IRSwT 8.34/3.08 (43) IRSwTToIntTRSProof [SOUND, 0 ms] 8.34/3.08 (44) IRSwT 8.34/3.08 (45) PrologToPiTRSProof [SOUND, 0 ms] 8.34/3.08 (46) PiTRS 8.34/3.08 (47) DependencyPairsProof [EQUIVALENT, 0 ms] 8.34/3.08 (48) PiDP 8.34/3.08 (49) DependencyGraphProof [EQUIVALENT, 0 ms] 8.34/3.08 (50) PiDP 8.34/3.08 (51) UsableRulesProof [EQUIVALENT, 0 ms] 8.34/3.08 (52) PiDP 8.34/3.08 (53) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.34/3.08 (54) QDP 8.34/3.08 (55) TransformationProof [EQUIVALENT, 0 ms] 8.34/3.08 (56) QDP 8.34/3.08 (57) NonTerminationLoopProof [COMPLETE, 0 ms] 8.34/3.08 (58) NO 8.34/3.08 (59) PrologToDTProblemTransformerProof [SOUND, 0 ms] 8.34/3.08 (60) TRIPLES 8.34/3.08 (61) TriplesToPiDPProof [SOUND, 0 ms] 8.34/3.08 (62) PiDP 8.34/3.08 (63) DependencyGraphProof [EQUIVALENT, 0 ms] 8.34/3.08 (64) PiDP 8.34/3.08 (65) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.34/3.08 (66) QDP 8.34/3.08 (67) TransformationProof [EQUIVALENT, 0 ms] 8.34/3.08 (68) QDP 8.34/3.08 (69) NonTerminationLoopProof [COMPLETE, 0 ms] 8.34/3.08 (70) NO 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (0) 8.34/3.08 Obligation: 8.34/3.08 Clauses: 8.34/3.08 8.34/3.08 p(a). 8.34/3.08 p(X) :- p(a). 8.34/3.08 q(b). 8.34/3.08 8.34/3.08 8.34/3.08 Query: p(g) 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (1) PrologToPiTRSProof (SOUND) 8.34/3.08 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.34/3.08 8.34/3.08 p_in_1: (b) 8.34/3.08 8.34/3.08 Transforming Prolog into the following Term Rewriting System: 8.34/3.08 8.34/3.08 Pi-finite rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 The argument filtering Pi contains the following mapping: 8.34/3.08 p_in_g(x1) = p_in_g(x1) 8.34/3.08 8.34/3.08 a = a 8.34/3.08 8.34/3.08 p_out_g(x1) = p_out_g 8.34/3.08 8.34/3.08 U1_g(x1, x2) = U1_g(x2) 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (2) 8.34/3.08 Obligation: 8.34/3.08 Pi-finite rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 The argument filtering Pi contains the following mapping: 8.34/3.08 p_in_g(x1) = p_in_g(x1) 8.34/3.08 8.34/3.08 a = a 8.34/3.08 8.34/3.08 p_out_g(x1) = p_out_g 8.34/3.08 8.34/3.08 U1_g(x1, x2) = U1_g(x2) 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (3) DependencyPairsProof (EQUIVALENT) 8.34/3.08 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> U1_G(X, p_in_g(a)) 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 The argument filtering Pi contains the following mapping: 8.34/3.08 p_in_g(x1) = p_in_g(x1) 8.34/3.08 8.34/3.08 a = a 8.34/3.08 8.34/3.08 p_out_g(x1) = p_out_g 8.34/3.08 8.34/3.08 U1_g(x1, x2) = U1_g(x2) 8.34/3.08 8.34/3.08 P_IN_G(x1) = P_IN_G(x1) 8.34/3.08 8.34/3.08 U1_G(x1, x2) = U1_G(x2) 8.34/3.08 8.34/3.08 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (4) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> U1_G(X, p_in_g(a)) 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 The argument filtering Pi contains the following mapping: 8.34/3.08 p_in_g(x1) = p_in_g(x1) 8.34/3.08 8.34/3.08 a = a 8.34/3.08 8.34/3.08 p_out_g(x1) = p_out_g 8.34/3.08 8.34/3.08 U1_g(x1, x2) = U1_g(x2) 8.34/3.08 8.34/3.08 P_IN_G(x1) = P_IN_G(x1) 8.34/3.08 8.34/3.08 U1_G(x1, x2) = U1_G(x2) 8.34/3.08 8.34/3.08 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (5) DependencyGraphProof (EQUIVALENT) 8.34/3.08 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (6) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 The argument filtering Pi contains the following mapping: 8.34/3.08 p_in_g(x1) = p_in_g(x1) 8.34/3.08 8.34/3.08 a = a 8.34/3.08 8.34/3.08 p_out_g(x1) = p_out_g 8.34/3.08 8.34/3.08 U1_g(x1, x2) = U1_g(x2) 8.34/3.08 8.34/3.08 P_IN_G(x1) = P_IN_G(x1) 8.34/3.08 8.34/3.08 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (7) UsableRulesProof (EQUIVALENT) 8.34/3.08 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (8) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Pi is empty. 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (9) PiDPToQDPProof (EQUIVALENT) 8.34/3.08 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (10) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (11) TransformationProof (EQUIVALENT) 8.34/3.08 By instantiating [LPAR04] the rule P_IN_G(X) -> P_IN_G(a) we obtained the following new rules [LPAR04]: 8.34/3.08 8.34/3.08 (P_IN_G(a) -> P_IN_G(a),P_IN_G(a) -> P_IN_G(a)) 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (12) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(a) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (13) NonTerminationLoopProof (COMPLETE) 8.34/3.08 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 8.34/3.08 Found a loop by semiunifying a rule from P directly. 8.34/3.08 8.34/3.08 s = P_IN_G(a) evaluates to t =P_IN_G(a) 8.34/3.08 8.34/3.08 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 8.34/3.08 * Matcher: [ ] 8.34/3.08 * Semiunifier: [ ] 8.34/3.08 8.34/3.08 -------------------------------------------------------------------------------- 8.34/3.08 Rewriting sequence 8.34/3.08 8.34/3.08 The DP semiunifies directly so there is only one rewrite step from P_IN_G(a) to P_IN_G(a). 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (14) 8.34/3.08 NO 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (15) PrologToTRSTransformerProof (SOUND) 8.34/3.08 Transformed Prolog program to TRS. 8.34/3.08 8.34/3.08 { 8.34/3.08 "root": 2, 8.34/3.08 "program": { 8.34/3.08 "directives": [], 8.34/3.08 "clauses": [ 8.34/3.08 [ 8.34/3.08 "(p (a))", 8.34/3.08 null 8.34/3.08 ], 8.34/3.08 [ 8.34/3.08 "(p X)", 8.34/3.08 "(p (a))" 8.34/3.08 ], 8.34/3.08 [ 8.34/3.08 "(q (b))", 8.34/3.08 null 8.34/3.08 ] 8.34/3.08 ] 8.34/3.08 }, 8.34/3.08 "graph": { 8.34/3.08 "nodes": { 8.34/3.08 "12": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": 0, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "2": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "13": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": 1, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "3": { 8.34/3.08 "goal": [ 8.34/3.08 { 8.34/3.08 "clause": 0, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "clause": 1, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 } 8.34/3.08 ], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "17": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(true)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "28": { 8.34/3.08 "goal": [], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "18": { 8.34/3.08 "goal": [], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "29": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(p (a))" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "type": "Nodes" 8.34/3.08 }, 8.34/3.08 "edges": [ 8.34/3.08 { 8.34/3.08 "from": 2, 8.34/3.08 "to": 3, 8.34/3.08 "label": "CASE" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 3, 8.34/3.08 "to": 12, 8.34/3.08 "label": "PARALLEL" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 3, 8.34/3.08 "to": 13, 8.34/3.08 "label": "PARALLEL" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 12, 8.34/3.08 "to": 17, 8.34/3.08 "label": "EVAL with clause\np(a).\nand substitutionT1 -> a" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 12, 8.34/3.08 "to": 18, 8.34/3.08 "label": "EVAL-BACKTRACK" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 13, 8.34/3.08 "to": 29, 8.34/3.08 "label": "ONLY EVAL with clause\np(X3) :- p(a).\nand substitutionT1 -> T4,\nX3 -> T4" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 17, 8.34/3.08 "to": 28, 8.34/3.08 "label": "SUCCESS" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 29, 8.34/3.08 "to": 2, 8.34/3.08 "label": "INSTANCE with matching:\nT1 -> a" 8.34/3.08 } 8.34/3.08 ], 8.34/3.08 "type": "Graph" 8.34/3.08 } 8.34/3.08 } 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (16) 8.34/3.08 Obligation: 8.34/3.08 Q restricted rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 f2_in(a) -> f2_out1 8.34/3.08 f2_in(T4) -> U1(f2_in(a), T4) 8.34/3.08 U1(f2_out1, T4) -> f2_out1 8.34/3.08 8.34/3.08 Q is empty. 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (17) QTRSRRRProof (EQUIVALENT) 8.34/3.08 Used ordering: 8.34/3.08 Polynomial interpretation [POLO]: 8.34/3.08 8.34/3.08 POL(U1(x_1, x_2)) = x_1 + 2*x_2 8.34/3.08 POL(a) = 0 8.34/3.08 POL(f2_in(x_1)) = 1 + 2*x_1 8.34/3.08 POL(f2_out1) = 0 8.34/3.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.34/3.08 8.34/3.08 f2_in(a) -> f2_out1 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (18) 8.34/3.08 Obligation: 8.34/3.08 Q restricted rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 f2_in(T4) -> U1(f2_in(a), T4) 8.34/3.08 U1(f2_out1, T4) -> f2_out1 8.34/3.08 8.34/3.08 Q is empty. 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (19) QTRSRRRProof (EQUIVALENT) 8.34/3.08 Used ordering: 8.34/3.08 Polynomial interpretation [POLO]: 8.34/3.08 8.34/3.08 POL(U1(x_1, x_2)) = 2*x_1 + 2*x_2 8.34/3.08 POL(a) = 0 8.34/3.08 POL(f2_in(x_1)) = 2*x_1 8.34/3.08 POL(f2_out1) = 1 8.34/3.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.34/3.08 8.34/3.08 U1(f2_out1, T4) -> f2_out1 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (20) 8.34/3.08 Obligation: 8.34/3.08 Q restricted rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 f2_in(T4) -> U1(f2_in(a), T4) 8.34/3.08 8.34/3.08 Q is empty. 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (21) Overlay + Local Confluence (EQUIVALENT) 8.34/3.08 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (22) 8.34/3.08 Obligation: 8.34/3.08 Q restricted rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 f2_in(T4) -> U1(f2_in(a), T4) 8.34/3.08 8.34/3.08 The set Q consists of the following terms: 8.34/3.08 8.34/3.08 f2_in(x0) 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (23) DependencyPairsProof (EQUIVALENT) 8.34/3.08 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (24) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 F2_IN(T4) -> F2_IN(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 f2_in(T4) -> U1(f2_in(a), T4) 8.34/3.08 8.34/3.08 The set Q consists of the following terms: 8.34/3.08 8.34/3.08 f2_in(x0) 8.34/3.08 8.34/3.08 We have to consider all minimal (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (25) UsableRulesProof (EQUIVALENT) 8.34/3.08 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. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (26) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 F2_IN(T4) -> F2_IN(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 The set Q consists of the following terms: 8.34/3.08 8.34/3.08 f2_in(x0) 8.34/3.08 8.34/3.08 We have to consider all minimal (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (27) QReductionProof (EQUIVALENT) 8.34/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.34/3.08 8.34/3.08 f2_in(x0) 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (28) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 F2_IN(T4) -> F2_IN(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all minimal (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (29) TransformationProof (EQUIVALENT) 8.34/3.08 By instantiating [LPAR04] the rule F2_IN(T4) -> F2_IN(a) we obtained the following new rules [LPAR04]: 8.34/3.08 8.34/3.08 (F2_IN(a) -> F2_IN(a),F2_IN(a) -> F2_IN(a)) 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (30) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 F2_IN(a) -> F2_IN(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all minimal (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (31) NonTerminationLoopProof (COMPLETE) 8.34/3.08 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 8.34/3.08 Found a loop by semiunifying a rule from P directly. 8.34/3.08 8.34/3.08 s = F2_IN(a) evaluates to t =F2_IN(a) 8.34/3.08 8.34/3.08 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 8.34/3.08 * Matcher: [ ] 8.34/3.08 * Semiunifier: [ ] 8.34/3.08 8.34/3.08 -------------------------------------------------------------------------------- 8.34/3.08 Rewriting sequence 8.34/3.08 8.34/3.08 The DP semiunifies directly so there is only one rewrite step from F2_IN(a) to F2_IN(a). 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (32) 8.34/3.08 NO 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (33) PrologToIRSwTTransformerProof (SOUND) 8.34/3.08 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 8.34/3.08 8.34/3.08 { 8.34/3.08 "root": 1, 8.34/3.08 "program": { 8.34/3.08 "directives": [], 8.34/3.08 "clauses": [ 8.34/3.08 [ 8.34/3.08 "(p (a))", 8.34/3.08 null 8.34/3.08 ], 8.34/3.08 [ 8.34/3.08 "(p X)", 8.34/3.08 "(p (a))" 8.34/3.08 ], 8.34/3.08 [ 8.34/3.08 "(q (b))", 8.34/3.08 null 8.34/3.08 ] 8.34/3.08 ] 8.34/3.08 }, 8.34/3.08 "graph": { 8.34/3.08 "nodes": { 8.34/3.08 "1": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "36": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": 0, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "4": { 8.34/3.08 "goal": [ 8.34/3.08 { 8.34/3.08 "clause": 0, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "clause": 1, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 } 8.34/3.08 ], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "37": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": 1, 8.34/3.08 "scope": 1, 8.34/3.08 "term": "(p T1)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": ["T1"], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "59": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(p (a))" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "49": { 8.34/3.08 "goal": [{ 8.34/3.08 "clause": -1, 8.34/3.08 "scope": -1, 8.34/3.08 "term": "(true)" 8.34/3.08 }], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "type": "Nodes", 8.34/3.08 "52": { 8.34/3.08 "goal": [], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "54": { 8.34/3.08 "goal": [], 8.34/3.08 "kb": { 8.34/3.08 "nonunifying": [], 8.34/3.08 "intvars": {}, 8.34/3.08 "arithmetic": { 8.34/3.08 "type": "PlainIntegerRelationState", 8.34/3.08 "relations": [] 8.34/3.08 }, 8.34/3.08 "ground": [], 8.34/3.08 "free": [], 8.34/3.08 "exprvars": [] 8.34/3.08 } 8.34/3.08 } 8.34/3.08 }, 8.34/3.08 "edges": [ 8.34/3.08 { 8.34/3.08 "from": 1, 8.34/3.08 "to": 4, 8.34/3.08 "label": "CASE" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 4, 8.34/3.08 "to": 36, 8.34/3.08 "label": "PARALLEL" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 4, 8.34/3.08 "to": 37, 8.34/3.08 "label": "PARALLEL" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 36, 8.34/3.08 "to": 49, 8.34/3.08 "label": "EVAL with clause\np(a).\nand substitutionT1 -> a" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 36, 8.34/3.08 "to": 52, 8.34/3.08 "label": "EVAL-BACKTRACK" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 37, 8.34/3.08 "to": 59, 8.34/3.08 "label": "ONLY EVAL with clause\np(X3) :- p(a).\nand substitutionT1 -> T4,\nX3 -> T4" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 49, 8.34/3.08 "to": 54, 8.34/3.08 "label": "SUCCESS" 8.34/3.08 }, 8.34/3.08 { 8.34/3.08 "from": 59, 8.34/3.08 "to": 1, 8.34/3.08 "label": "INSTANCE with matching:\nT1 -> a" 8.34/3.08 } 8.34/3.08 ], 8.34/3.08 "type": "Graph" 8.34/3.08 } 8.34/3.08 } 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (34) 8.34/3.08 Obligation: 8.34/3.08 Rules: 8.34/3.08 f59_out -> f37_out(T4) :|: TRUE 8.34/3.08 f37_in(x) -> f59_in :|: TRUE 8.34/3.08 f1_out(a) -> f59_out :|: TRUE 8.34/3.08 f59_in -> f1_in(a) :|: TRUE 8.34/3.08 f4_in(T1) -> f37_in(T1) :|: TRUE 8.34/3.08 f4_in(x1) -> f36_in(x1) :|: TRUE 8.34/3.08 f37_out(x2) -> f4_out(x2) :|: TRUE 8.34/3.08 f36_out(x3) -> f4_out(x3) :|: TRUE 8.34/3.08 f4_out(x4) -> f1_out(x4) :|: TRUE 8.34/3.08 f1_in(x5) -> f4_in(x5) :|: TRUE 8.34/3.08 Start term: f1_in(T1) 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (35) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 8.34/3.08 Constructed simple dependency graph. 8.34/3.08 8.34/3.08 Simplified to the following IRSwTs: 8.34/3.08 8.34/3.08 intTRSProblem: 8.34/3.08 f37_in(x) -> f59_in :|: TRUE 8.34/3.08 f59_in -> f1_in(a) :|: TRUE 8.34/3.08 f4_in(T1) -> f37_in(T1) :|: TRUE 8.34/3.08 f1_in(x5) -> f4_in(x5) :|: TRUE 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (36) 8.34/3.08 Obligation: 8.34/3.08 Rules: 8.34/3.08 f37_in(x) -> f59_in :|: TRUE 8.34/3.08 f59_in -> f1_in(a) :|: TRUE 8.34/3.08 f4_in(T1) -> f37_in(T1) :|: TRUE 8.34/3.08 f1_in(x5) -> f4_in(x5) :|: TRUE 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (37) IntTRSCompressionProof (EQUIVALENT) 8.34/3.08 Compressed rules. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (38) 8.34/3.08 Obligation: 8.34/3.08 Rules: 8.34/3.08 f4_in(T1:0) -> f4_in(a) :|: TRUE 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (39) IRSFormatTransformerProof (EQUIVALENT) 8.34/3.08 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (40) 8.34/3.08 Obligation: 8.34/3.08 Rules: 8.34/3.08 f4_in(T1:0) -> f4_in(a) :|: TRUE 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (41) IRSwTTerminationDigraphProof (EQUIVALENT) 8.34/3.08 Constructed termination digraph! 8.34/3.08 Nodes: 8.34/3.08 (1) f4_in(T1:0) -> f4_in(a) :|: TRUE 8.34/3.08 8.34/3.08 Arcs: 8.34/3.08 (1) -> (1) 8.34/3.08 8.34/3.08 This digraph is fully evaluated! 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (42) 8.34/3.08 Obligation: 8.34/3.08 8.34/3.08 Termination digraph: 8.34/3.08 Nodes: 8.34/3.08 (1) f4_in(T1:0) -> f4_in(a) :|: TRUE 8.34/3.08 8.34/3.08 Arcs: 8.34/3.08 (1) -> (1) 8.34/3.08 8.34/3.08 This digraph is fully evaluated! 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (43) IRSwTToIntTRSProof (SOUND) 8.34/3.08 Applied path-length measure to transform intTRS with terms to intTRS. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (44) 8.34/3.08 Obligation: 8.34/3.08 Rules: 8.34/3.08 f4_in(x) -> f4_in(a) :|: TRUE 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (45) PrologToPiTRSProof (SOUND) 8.34/3.08 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.34/3.08 8.34/3.08 p_in_1: (b) 8.34/3.08 8.34/3.08 Transforming Prolog into the following Term Rewriting System: 8.34/3.08 8.34/3.08 Pi-finite rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 Pi is empty. 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.34/3.08 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (46) 8.34/3.08 Obligation: 8.34/3.08 Pi-finite rewrite system: 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 Pi is empty. 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (47) DependencyPairsProof (EQUIVALENT) 8.34/3.08 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> U1_G(X, p_in_g(a)) 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 Pi is empty. 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (48) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> U1_G(X, p_in_g(a)) 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 Pi is empty. 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (49) DependencyGraphProof (EQUIVALENT) 8.34/3.08 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (50) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 The TRS R consists of the following rules: 8.34/3.08 8.34/3.08 p_in_g(a) -> p_out_g(a) 8.34/3.08 p_in_g(X) -> U1_g(X, p_in_g(a)) 8.34/3.08 U1_g(X, p_out_g(a)) -> p_out_g(X) 8.34/3.08 8.34/3.08 Pi is empty. 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (51) UsableRulesProof (EQUIVALENT) 8.34/3.08 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (52) 8.34/3.08 Obligation: 8.34/3.08 Pi DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Pi is empty. 8.34/3.08 We have to consider all (P,R,Pi)-chains 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (53) PiDPToQDPProof (EQUIVALENT) 8.34/3.08 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (54) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(X) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (55) TransformationProof (EQUIVALENT) 8.34/3.08 By instantiating [LPAR04] the rule P_IN_G(X) -> P_IN_G(a) we obtained the following new rules [LPAR04]: 8.34/3.08 8.34/3.08 (P_IN_G(a) -> P_IN_G(a),P_IN_G(a) -> P_IN_G(a)) 8.34/3.08 8.34/3.08 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (56) 8.34/3.08 Obligation: 8.34/3.08 Q DP problem: 8.34/3.08 The TRS P consists of the following rules: 8.34/3.08 8.34/3.08 P_IN_G(a) -> P_IN_G(a) 8.34/3.08 8.34/3.08 R is empty. 8.34/3.08 Q is empty. 8.34/3.08 We have to consider all (P,Q,R)-chains. 8.34/3.08 ---------------------------------------- 8.34/3.08 8.34/3.08 (57) NonTerminationLoopProof (COMPLETE) 8.34/3.08 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 8.34/3.08 Found a loop by semiunifying a rule from P directly. 8.34/3.08 8.34/3.08 s = P_IN_G(a) evaluates to t =P_IN_G(a) 8.34/3.08 8.34/3.08 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 8.34/3.09 * Matcher: [ ] 8.34/3.09 * Semiunifier: [ ] 8.34/3.09 8.34/3.09 -------------------------------------------------------------------------------- 8.34/3.09 Rewriting sequence 8.34/3.09 8.34/3.09 The DP semiunifies directly so there is only one rewrite step from P_IN_G(a) to P_IN_G(a). 8.34/3.09 8.34/3.09 8.34/3.09 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (58) 8.34/3.09 NO 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (59) PrologToDTProblemTransformerProof (SOUND) 8.34/3.09 Built DT problem from termination graph DT10. 8.34/3.09 8.34/3.09 { 8.34/3.09 "root": 60, 8.34/3.09 "program": { 8.34/3.09 "directives": [], 8.34/3.09 "clauses": [ 8.34/3.09 [ 8.34/3.09 "(p (a))", 8.34/3.09 null 8.34/3.09 ], 8.34/3.09 [ 8.34/3.09 "(p X)", 8.34/3.09 "(p (a))" 8.34/3.09 ], 8.34/3.09 [ 8.34/3.09 "(q (b))", 8.34/3.09 null 8.34/3.09 ] 8.34/3.09 ] 8.34/3.09 }, 8.34/3.09 "graph": { 8.34/3.09 "nodes": { 8.34/3.09 "66": { 8.34/3.09 "goal": [ 8.34/3.09 { 8.34/3.09 "clause": 0, 8.34/3.09 "scope": 2, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 2, 8.34/3.09 "term": "(p (a))" 8.34/3.09 } 8.34/3.09 ], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "77": { 8.34/3.09 "goal": [], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "67": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 0, 8.34/3.09 "scope": 2, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "78": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "68": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 2, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "69": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(true)" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "type": "Nodes", 8.34/3.09 "70": { 8.34/3.09 "goal": [], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "60": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(p T1)" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": ["T1"], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "71": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "61": { 8.34/3.09 "goal": [ 8.34/3.09 { 8.34/3.09 "clause": 0, 8.34/3.09 "scope": 1, 8.34/3.09 "term": "(p T1)" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 1, 8.34/3.09 "term": "(p T1)" 8.34/3.09 } 8.34/3.09 ], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": ["T1"], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "72": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "62": { 8.34/3.09 "goal": [ 8.34/3.09 { 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(true)" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 } 8.34/3.09 ], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "73": { 8.34/3.09 "goal": [ 8.34/3.09 { 8.34/3.09 "clause": 0, 8.34/3.09 "scope": 3, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 3, 8.34/3.09 "term": "(p (a))" 8.34/3.09 } 8.34/3.09 ], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "63": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 1, 8.34/3.09 "term": "(p T1)" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [[ 8.34/3.09 "(p T1)", 8.34/3.09 "(p (a))" 8.34/3.09 ]], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": ["T1"], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "74": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 0, 8.34/3.09 "scope": 3, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "64": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "75": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": 1, 8.34/3.09 "scope": 3, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "65": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(p (a))" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "76": { 8.34/3.09 "goal": [{ 8.34/3.09 "clause": -1, 8.34/3.09 "scope": -1, 8.34/3.09 "term": "(true)" 8.34/3.09 }], 8.34/3.09 "kb": { 8.34/3.09 "nonunifying": [], 8.34/3.09 "intvars": {}, 8.34/3.09 "arithmetic": { 8.34/3.09 "type": "PlainIntegerRelationState", 8.34/3.09 "relations": [] 8.34/3.09 }, 8.34/3.09 "ground": [], 8.34/3.09 "free": [], 8.34/3.09 "exprvars": [] 8.34/3.09 } 8.34/3.09 } 8.34/3.09 }, 8.34/3.09 "edges": [ 8.34/3.09 { 8.34/3.09 "from": 60, 8.34/3.09 "to": 61, 8.34/3.09 "label": "CASE" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 61, 8.34/3.09 "to": 62, 8.34/3.09 "label": "EVAL with clause\np(a).\nand substitutionT1 -> a" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 61, 8.34/3.09 "to": 63, 8.34/3.09 "label": "EVAL-BACKTRACK" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 62, 8.34/3.09 "to": 64, 8.34/3.09 "label": "SUCCESS" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 63, 8.34/3.09 "to": 72, 8.34/3.09 "label": "ONLY EVAL with clause\np(X7) :- p(a).\nand substitutionT1 -> T3,\nX7 -> T3" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 64, 8.34/3.09 "to": 65, 8.34/3.09 "label": "ONLY EVAL with clause\np(X2) :- p(a).\nand substitutionX2 -> a" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 65, 8.34/3.09 "to": 66, 8.34/3.09 "label": "CASE" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 66, 8.34/3.09 "to": 67, 8.34/3.09 "label": "PARALLEL" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 66, 8.34/3.09 "to": 68, 8.34/3.09 "label": "PARALLEL" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 67, 8.34/3.09 "to": 69, 8.34/3.09 "label": "ONLY EVAL with clause\np(a).\nand substitution" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 68, 8.34/3.09 "to": 71, 8.34/3.09 "label": "ONLY EVAL with clause\np(X5) :- p(a).\nand substitutionX5 -> a" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 69, 8.34/3.09 "to": 70, 8.34/3.09 "label": "SUCCESS" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 71, 8.34/3.09 "to": 60, 8.34/3.09 "label": "INSTANCE with matching:\nT1 -> a" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 72, 8.34/3.09 "to": 73, 8.34/3.09 "label": "CASE" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 73, 8.34/3.09 "to": 74, 8.34/3.09 "label": "PARALLEL" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 73, 8.34/3.09 "to": 75, 8.34/3.09 "label": "PARALLEL" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 74, 8.34/3.09 "to": 76, 8.34/3.09 "label": "ONLY EVAL with clause\np(a).\nand substitution" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 75, 8.34/3.09 "to": 78, 8.34/3.09 "label": "ONLY EVAL with clause\np(X10) :- p(a).\nand substitutionX10 -> a" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 76, 8.34/3.09 "to": 77, 8.34/3.09 "label": "SUCCESS" 8.34/3.09 }, 8.34/3.09 { 8.34/3.09 "from": 78, 8.34/3.09 "to": 60, 8.34/3.09 "label": "INSTANCE with matching:\nT1 -> a" 8.34/3.09 } 8.34/3.09 ], 8.34/3.09 "type": "Graph" 8.34/3.09 } 8.34/3.09 } 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (60) 8.34/3.09 Obligation: 8.34/3.09 Triples: 8.34/3.09 8.34/3.09 pA(a) :- pA(a). 8.34/3.09 pA(X1) :- pA(a). 8.34/3.09 8.34/3.09 Clauses: 8.34/3.09 8.34/3.09 pcA(a). 8.34/3.09 pcA(a). 8.34/3.09 pcA(a) :- pcA(a). 8.34/3.09 pcA(X1). 8.34/3.09 pcA(X1) :- pcA(a). 8.34/3.09 8.34/3.09 Afs: 8.34/3.09 8.34/3.09 pA(x1) = pA(x1) 8.34/3.09 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (61) TriplesToPiDPProof (SOUND) 8.34/3.09 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.34/3.09 8.34/3.09 pA_in_1: (b) 8.34/3.09 8.34/3.09 Transforming TRIPLES into the following Term Rewriting System: 8.34/3.09 8.34/3.09 Pi DP problem: 8.34/3.09 The TRS P consists of the following rules: 8.34/3.09 8.34/3.09 PA_IN_G(a) -> U1_G(pA_in_g(a)) 8.34/3.09 PA_IN_G(a) -> PA_IN_G(a) 8.34/3.09 PA_IN_G(X1) -> U2_G(X1, pA_in_g(a)) 8.34/3.09 PA_IN_G(X1) -> PA_IN_G(a) 8.34/3.09 8.34/3.09 R is empty. 8.34/3.09 Pi is empty. 8.34/3.09 We have to consider all (P,R,Pi)-chains 8.34/3.09 8.34/3.09 8.34/3.09 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 8.34/3.09 8.34/3.09 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (62) 8.34/3.09 Obligation: 8.34/3.09 Pi DP problem: 8.34/3.09 The TRS P consists of the following rules: 8.34/3.09 8.34/3.09 PA_IN_G(a) -> U1_G(pA_in_g(a)) 8.34/3.09 PA_IN_G(a) -> PA_IN_G(a) 8.34/3.09 PA_IN_G(X1) -> U2_G(X1, pA_in_g(a)) 8.34/3.09 PA_IN_G(X1) -> PA_IN_G(a) 8.34/3.09 8.34/3.09 R is empty. 8.34/3.09 Pi is empty. 8.34/3.09 We have to consider all (P,R,Pi)-chains 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (63) DependencyGraphProof (EQUIVALENT) 8.34/3.09 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (64) 8.34/3.09 Obligation: 8.34/3.09 Pi DP problem: 8.34/3.09 The TRS P consists of the following rules: 8.34/3.09 8.34/3.09 PA_IN_G(X1) -> PA_IN_G(a) 8.34/3.09 PA_IN_G(a) -> PA_IN_G(a) 8.34/3.09 8.34/3.09 R is empty. 8.34/3.09 Pi is empty. 8.34/3.09 We have to consider all (P,R,Pi)-chains 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (65) PiDPToQDPProof (EQUIVALENT) 8.34/3.09 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (66) 8.34/3.09 Obligation: 8.34/3.09 Q DP problem: 8.34/3.09 The TRS P consists of the following rules: 8.34/3.09 8.34/3.09 PA_IN_G(X1) -> PA_IN_G(a) 8.34/3.09 PA_IN_G(a) -> PA_IN_G(a) 8.34/3.09 8.34/3.09 R is empty. 8.34/3.09 Q is empty. 8.34/3.09 We have to consider all (P,Q,R)-chains. 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (67) TransformationProof (EQUIVALENT) 8.34/3.09 By instantiating [LPAR04] the rule PA_IN_G(X1) -> PA_IN_G(a) we obtained the following new rules [LPAR04]: 8.34/3.09 8.34/3.09 (PA_IN_G(a) -> PA_IN_G(a),PA_IN_G(a) -> PA_IN_G(a)) 8.34/3.09 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (68) 8.34/3.09 Obligation: 8.34/3.09 Q DP problem: 8.34/3.09 The TRS P consists of the following rules: 8.34/3.09 8.34/3.09 PA_IN_G(a) -> PA_IN_G(a) 8.34/3.09 8.34/3.09 R is empty. 8.34/3.09 Q is empty. 8.34/3.09 We have to consider all (P,Q,R)-chains. 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (69) NonTerminationLoopProof (COMPLETE) 8.34/3.09 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 8.34/3.09 Found a loop by semiunifying a rule from P directly. 8.34/3.09 8.34/3.09 s = PA_IN_G(a) evaluates to t =PA_IN_G(a) 8.34/3.09 8.34/3.09 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 8.34/3.09 * Matcher: [ ] 8.34/3.09 * Semiunifier: [ ] 8.34/3.09 8.34/3.09 -------------------------------------------------------------------------------- 8.34/3.09 Rewriting sequence 8.34/3.09 8.34/3.09 The DP semiunifies directly so there is only one rewrite step from PA_IN_G(a) to PA_IN_G(a). 8.34/3.09 8.34/3.09 8.34/3.09 8.34/3.09 8.34/3.09 ---------------------------------------- 8.34/3.09 8.34/3.09 (70) 8.34/3.09 NO 8.61/3.14 EOF