7.48/2.89 MAYBE 7.79/2.91 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 7.79/2.91 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.79/2.91 7.79/2.91 7.79/2.91 Left Termination of the query pattern 7.79/2.91 7.79/2.91 fl(a,a,g) 7.79/2.91 7.79/2.91 w.r.t. the given Prolog program could not be shown: 7.79/2.91 7.79/2.91 (0) Prolog 7.79/2.91 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 7.79/2.91 (2) TRIPLES 7.79/2.91 (3) TriplesToPiDPProof [SOUND, 15 ms] 7.79/2.91 (4) PiDP 7.79/2.91 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.91 (6) PiDP 7.79/2.91 (7) PiDPToQDPProof [SOUND, 0 ms] 7.79/2.91 (8) QDP 7.79/2.91 (9) UsableRulesReductionPairsProof [EQUIVALENT, 12 ms] 7.79/2.91 (10) QDP 7.79/2.91 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.91 (12) QDP 7.79/2.91 (13) NonTerminationLoopProof [COMPLETE, 0 ms] 7.79/2.91 (14) NO 7.79/2.91 (15) PrologToTRSTransformerProof [SOUND, 0 ms] 7.79/2.91 (16) QTRS 7.79/2.91 (17) QTRSRRRProof [EQUIVALENT, 70 ms] 7.79/2.91 (18) QTRS 7.79/2.91 (19) QTRSRRRProof [EQUIVALENT, 0 ms] 7.79/2.91 (20) QTRS 7.79/2.91 (21) QTRSRRRProof [EQUIVALENT, 2 ms] 7.79/2.91 (22) QTRS 7.79/2.91 (23) Overlay + Local Confluence [EQUIVALENT, 0 ms] 7.79/2.91 (24) QTRS 7.79/2.91 (25) DependencyPairsProof [EQUIVALENT, 3 ms] 7.79/2.91 (26) QDP 7.79/2.91 (27) UsableRulesProof [EQUIVALENT, 0 ms] 7.79/2.91 (28) QDP 7.79/2.91 (29) QReductionProof [EQUIVALENT, 0 ms] 7.79/2.91 (30) QDP 7.79/2.91 (31) NonTerminationLoopProof [COMPLETE, 0 ms] 7.79/2.91 (32) NO 7.79/2.91 (33) PrologToPiTRSProof [SOUND, 0 ms] 7.79/2.91 (34) PiTRS 7.79/2.91 (35) DependencyPairsProof [EQUIVALENT, 11 ms] 7.79/2.91 (36) PiDP 7.79/2.91 (37) DependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.91 (38) AND 7.79/2.91 (39) PiDP 7.79/2.91 (40) UsableRulesProof [EQUIVALENT, 0 ms] 7.79/2.91 (41) PiDP 7.79/2.91 (42) PiDPToQDPProof [SOUND, 0 ms] 7.79/2.91 (43) QDP 7.79/2.91 (44) NonTerminationLoopProof [COMPLETE, 0 ms] 7.79/2.91 (45) NO 7.79/2.91 (46) PiDP 7.79/2.91 (47) UsableRulesProof [EQUIVALENT, 0 ms] 7.79/2.91 (48) PiDP 7.79/2.91 (49) PiDPToQDPProof [SOUND, 0 ms] 7.79/2.91 (50) QDP 7.79/2.91 (51) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.79/2.91 (52) YES 7.79/2.91 (53) PrologToPiTRSProof [SOUND, 0 ms] 7.79/2.91 (54) PiTRS 7.79/2.91 (55) DependencyPairsProof [EQUIVALENT, 4 ms] 7.79/2.91 (56) PiDP 7.79/2.91 (57) DependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.91 (58) AND 7.79/2.92 (59) PiDP 7.79/2.92 (60) UsableRulesProof [EQUIVALENT, 0 ms] 7.79/2.92 (61) PiDP 7.79/2.92 (62) PiDPToQDPProof [SOUND, 0 ms] 7.79/2.92 (63) QDP 7.79/2.92 (64) NonTerminationLoopProof [COMPLETE, 0 ms] 7.79/2.92 (65) NO 7.79/2.92 (66) PiDP 7.79/2.92 (67) UsableRulesProof [EQUIVALENT, 0 ms] 7.79/2.92 (68) PiDP 7.79/2.92 (69) PiDPToQDPProof [SOUND, 0 ms] 7.79/2.92 (70) QDP 7.79/2.92 (71) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.79/2.92 (72) YES 7.79/2.92 (73) PrologToIRSwTTransformerProof [SOUND, 37 ms] 7.79/2.92 (74) AND 7.79/2.92 (75) IRSwT 7.79/2.92 (76) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.92 (77) IRSwT 7.79/2.92 (78) IntTRSCompressionProof [EQUIVALENT, 19 ms] 7.79/2.92 (79) IRSwT 7.79/2.92 (80) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.79/2.92 (81) IRSwT 7.79/2.92 (82) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 7.79/2.92 (83) IRSwT 7.79/2.92 (84) FilterProof [EQUIVALENT, 0 ms] 7.79/2.92 (85) IntTRS 7.79/2.92 (86) IntTRSPeriodicNontermProof [COMPLETE, 7 ms] 7.79/2.92 (87) NO 7.79/2.92 (88) IRSwT 7.79/2.92 (89) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 7.79/2.92 (90) IRSwT 7.79/2.92 (91) IntTRSCompressionProof [EQUIVALENT, 7 ms] 7.79/2.92 (92) IRSwT 7.79/2.92 (93) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.79/2.92 (94) IRSwT 7.79/2.92 (95) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] 7.79/2.92 (96) IRSwT 7.79/2.92 (97) FilterProof [EQUIVALENT, 0 ms] 7.79/2.92 (98) IntTRS 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (0) 7.79/2.92 Obligation: 7.79/2.92 Clauses: 7.79/2.92 7.79/2.92 fl([], [], 0). 7.79/2.92 fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). 7.79/2.92 append([], X, X). 7.79/2.92 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 7.79/2.92 7.79/2.92 7.79/2.92 Query: fl(a,a,g) 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (1) PrologToDTProblemTransformerProof (SOUND) 7.79/2.92 Built DT problem from termination graph DT10. 7.79/2.92 7.79/2.92 { 7.79/2.92 "root": 1, 7.79/2.92 "program": { 7.79/2.92 "directives": [], 7.79/2.92 "clauses": [ 7.79/2.92 [ 7.79/2.92 "(fl ([]) ([]) (0))", 7.79/2.92 null 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(fl (. E X) R (s Z))", 7.79/2.92 "(',' (append E Y R) (fl X Y Z))" 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(append ([]) X X)", 7.79/2.92 null 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(append (. X Xs) Ys (. X Zs))", 7.79/2.92 "(append Xs Ys Zs)" 7.79/2.92 ] 7.79/2.92 ] 7.79/2.92 }, 7.79/2.92 "graph": { 7.79/2.92 "nodes": { 7.79/2.92 "22": { 7.79/2.92 "goal": [ 7.79/2.92 { 7.79/2.92 "clause": 2, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(',' (append T15 X13 T16) (fl T17 X13 T14))" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "clause": 3, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(',' (append T15 X13 T16) (fl T17 X13 T14))" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": ["X13"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "12": { 7.79/2.92 "goal": [ 7.79/2.92 { 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(true)" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 (0))" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "23": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 2, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(',' (append T15 X13 T16) (fl T17 X13 T14))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": ["X13"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "24": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 3, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(',' (append T15 X13 T16) (fl T17 X13 T14))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": ["X13"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "14": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [[ 7.79/2.92 "(fl T1 T2 T3)", 7.79/2.92 "(fl ([]) ([]) (0))" 7.79/2.92 ]], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "25": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(fl T23 T24 T14)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "26": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "16": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 (0))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "17": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "type": "Nodes", 7.79/2.92 "1": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "6": { 7.79/2.92 "goal": [ 7.79/2.92 { 7.79/2.92 "clause": 0, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "20": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(',' (append T15 X13 T16) (fl T17 X13 T14))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": ["X13"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "42": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(',' (append T34 X38 T35) (fl T36 X38 T14))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T14"], 7.79/2.92 "free": ["X38"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "21": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "43": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "edges": [ 7.79/2.92 { 7.79/2.92 "from": 1, 7.79/2.92 "to": 6, 7.79/2.92 "label": "CASE" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 6, 7.79/2.92 "to": 12, 7.79/2.92 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 6, 7.79/2.92 "to": 14, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 12, 7.79/2.92 "to": 16, 7.79/2.92 "label": "SUCCESS" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 14, 7.79/2.92 "to": 20, 7.79/2.92 "label": "EVAL with clause\nfl(.(X9, X10), X11, s(X12)) :- ','(append(X9, X13, X11), fl(X10, X13, X12)).\nand substitutionX9 -> T15,\nX10 -> T17,\nT1 -> .(T15, T17),\nT2 -> T16,\nX11 -> T16,\nX12 -> T14,\nT3 -> s(T14),\nT11 -> T15,\nT13 -> T16,\nT12 -> T17" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 14, 7.79/2.92 "to": 21, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 16, 7.79/2.92 "to": 17, 7.79/2.92 "label": "BACKTRACK\nfor clause: fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z))because of non-unification" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 20, 7.79/2.92 "to": 22, 7.79/2.92 "label": "CASE" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 22, 7.79/2.92 "to": 23, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 22, 7.79/2.92 "to": 24, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 23, 7.79/2.92 "to": 25, 7.79/2.92 "label": "EVAL with clause\nappend([], X22, X22).\nand substitutionT15 -> [],\nX13 -> T24,\nX22 -> T24,\nT16 -> T24,\nX23 -> T24,\nT17 -> T23,\nT22 -> T24" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 23, 7.79/2.92 "to": 26, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 24, 7.79/2.92 "to": 42, 7.79/2.92 "label": "EVAL with clause\nappend(.(X34, X35), X36, .(X34, X37)) :- append(X35, X36, X37).\nand substitutionX34 -> T31,\nX35 -> T34,\nT15 -> .(T31, T34),\nX13 -> X38,\nX36 -> X38,\nX37 -> T35,\nT16 -> .(T31, T35),\nT32 -> T34,\nT33 -> T35,\nT17 -> T36" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 24, 7.79/2.92 "to": 43, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 25, 7.79/2.92 "to": 1, 7.79/2.92 "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T24\nT3 -> T14" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 42, 7.79/2.92 "to": 20, 7.79/2.92 "label": "INSTANCE with matching:\nT15 -> T34\nX13 -> X38\nT16 -> T35\nT17 -> T36" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "type": "Graph" 7.79/2.92 } 7.79/2.92 } 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (2) 7.79/2.92 Obligation: 7.79/2.92 Triples: 7.79/2.92 7.79/2.92 pB([], X1, X1, X2, X3) :- flA(X2, X1, X3). 7.79/2.92 pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). 7.79/2.92 flA(.(X1, X2), X3, s(X4)) :- pB(X1, X5, X3, X2, X4). 7.79/2.92 7.79/2.92 Clauses: 7.79/2.92 7.79/2.92 flcA([], [], 0). 7.79/2.92 flcA(.(X1, X2), X3, s(X4)) :- qcB(X1, X5, X3, X2, X4). 7.79/2.92 qcB([], X1, X1, X2, X3) :- flcA(X2, X1, X3). 7.79/2.92 qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). 7.79/2.92 7.79/2.92 Afs: 7.79/2.92 7.79/2.92 flA(x1, x2, x3) = flA(x3) 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (3) TriplesToPiDPProof (SOUND) 7.79/2.92 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.79/2.92 7.79/2.92 flA_in_3: (f,f,b) 7.79/2.92 7.79/2.92 pB_in_5: (f,f,f,f,b) 7.79/2.92 7.79/2.92 Transforming TRIPLES into the following Term Rewriting System: 7.79/2.92 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FLA_IN_AAG(.(X1, X2), X3, s(X4)) -> U3_AAG(X1, X2, X3, X4, pB_in_aaaag(X1, X5, X3, X2, X4)) 7.79/2.92 FLA_IN_AAG(.(X1, X2), X3, s(X4)) -> PB_IN_AAAAG(X1, X5, X3, X2, X4) 7.79/2.92 PB_IN_AAAAG([], X1, X1, X2, X3) -> U1_AAAAG(X1, X2, X3, flA_in_aag(X2, X1, X3)) 7.79/2.92 PB_IN_AAAAG([], X1, X1, X2, X3) -> FLA_IN_AAG(X2, X1, X3) 7.79/2.92 PB_IN_AAAAG(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_AAAAG(X1, X2, X3, X4, X5, X6, pB_in_aaaag(X2, X3, X4, X5, X6)) 7.79/2.92 PB_IN_AAAAG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAAG(X2, X3, X4, X5, X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 flA_in_aag(x1, x2, x3) = flA_in_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 pB_in_aaaag(x1, x2, x3, x4, x5) = pB_in_aaaag(x5) 7.79/2.92 7.79/2.92 FLA_IN_AAG(x1, x2, x3) = FLA_IN_AAG(x3) 7.79/2.92 7.79/2.92 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x4, x5) 7.79/2.92 7.79/2.92 PB_IN_AAAAG(x1, x2, x3, x4, x5) = PB_IN_AAAAG(x5) 7.79/2.92 7.79/2.92 U1_AAAAG(x1, x2, x3, x4) = U1_AAAAG(x3, x4) 7.79/2.92 7.79/2.92 U2_AAAAG(x1, x2, x3, x4, x5, x6, x7) = U2_AAAAG(x6, x7) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 7.79/2.92 7.79/2.92 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (4) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FLA_IN_AAG(.(X1, X2), X3, s(X4)) -> U3_AAG(X1, X2, X3, X4, pB_in_aaaag(X1, X5, X3, X2, X4)) 7.79/2.92 FLA_IN_AAG(.(X1, X2), X3, s(X4)) -> PB_IN_AAAAG(X1, X5, X3, X2, X4) 7.79/2.92 PB_IN_AAAAG([], X1, X1, X2, X3) -> U1_AAAAG(X1, X2, X3, flA_in_aag(X2, X1, X3)) 7.79/2.92 PB_IN_AAAAG([], X1, X1, X2, X3) -> FLA_IN_AAG(X2, X1, X3) 7.79/2.92 PB_IN_AAAAG(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_AAAAG(X1, X2, X3, X4, X5, X6, pB_in_aaaag(X2, X3, X4, X5, X6)) 7.79/2.92 PB_IN_AAAAG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAAG(X2, X3, X4, X5, X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 flA_in_aag(x1, x2, x3) = flA_in_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 pB_in_aaaag(x1, x2, x3, x4, x5) = pB_in_aaaag(x5) 7.79/2.92 7.79/2.92 FLA_IN_AAG(x1, x2, x3) = FLA_IN_AAG(x3) 7.79/2.92 7.79/2.92 U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x4, x5) 7.79/2.92 7.79/2.92 PB_IN_AAAAG(x1, x2, x3, x4, x5) = PB_IN_AAAAG(x5) 7.79/2.92 7.79/2.92 U1_AAAAG(x1, x2, x3, x4) = U1_AAAAG(x3, x4) 7.79/2.92 7.79/2.92 U2_AAAAG(x1, x2, x3, x4, x5, x6, x7) = U2_AAAAG(x6, x7) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (5) DependencyGraphProof (EQUIVALENT) 7.79/2.92 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (6) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FLA_IN_AAG(.(X1, X2), X3, s(X4)) -> PB_IN_AAAAG(X1, X5, X3, X2, X4) 7.79/2.92 PB_IN_AAAAG([], X1, X1, X2, X3) -> FLA_IN_AAG(X2, X1, X3) 7.79/2.92 PB_IN_AAAAG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAAG(X2, X3, X4, X5, X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 FLA_IN_AAG(x1, x2, x3) = FLA_IN_AAG(x3) 7.79/2.92 7.79/2.92 PB_IN_AAAAG(x1, x2, x3, x4, x5) = PB_IN_AAAAG(x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (7) PiDPToQDPProof (SOUND) 7.79/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (8) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FLA_IN_AAG(s(X4)) -> PB_IN_AAAAG(X4) 7.79/2.92 PB_IN_AAAAG(X3) -> FLA_IN_AAG(X3) 7.79/2.92 PB_IN_AAAAG(X6) -> PB_IN_AAAAG(X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 Q is empty. 7.79/2.92 We have to consider all (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (9) UsableRulesReductionPairsProof (EQUIVALENT) 7.79/2.92 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.79/2.92 7.79/2.92 The following dependency pairs can be deleted: 7.79/2.92 7.79/2.92 FLA_IN_AAG(s(X4)) -> PB_IN_AAAAG(X4) 7.79/2.92 No rules are removed from R. 7.79/2.92 7.79/2.92 Used ordering: POLO with Polynomial interpretation [POLO]: 7.79/2.92 7.79/2.92 POL(FLA_IN_AAG(x_1)) = 2 + x_1 7.79/2.92 POL(PB_IN_AAAAG(x_1)) = 2 + x_1 7.79/2.92 POL(s(x_1)) = 2 + 2*x_1 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (10) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 PB_IN_AAAAG(X3) -> FLA_IN_AAG(X3) 7.79/2.92 PB_IN_AAAAG(X6) -> PB_IN_AAAAG(X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 Q is empty. 7.79/2.92 We have to consider all (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (11) DependencyGraphProof (EQUIVALENT) 7.79/2.92 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (12) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 PB_IN_AAAAG(X6) -> PB_IN_AAAAG(X6) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 Q is empty. 7.79/2.92 We have to consider all (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (13) NonTerminationLoopProof (COMPLETE) 7.79/2.92 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.79/2.92 Found a loop by semiunifying a rule from P directly. 7.79/2.92 7.79/2.92 s = PB_IN_AAAAG(X6) evaluates to t =PB_IN_AAAAG(X6) 7.79/2.92 7.79/2.92 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.79/2.92 * Matcher: [ ] 7.79/2.92 * Semiunifier: [ ] 7.79/2.92 7.79/2.92 -------------------------------------------------------------------------------- 7.79/2.92 Rewriting sequence 7.79/2.92 7.79/2.92 The DP semiunifies directly so there is only one rewrite step from PB_IN_AAAAG(X6) to PB_IN_AAAAG(X6). 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (14) 7.79/2.92 NO 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (15) PrologToTRSTransformerProof (SOUND) 7.79/2.92 Transformed Prolog program to TRS. 7.79/2.92 7.79/2.92 { 7.79/2.92 "root": 3, 7.79/2.92 "program": { 7.79/2.92 "directives": [], 7.79/2.92 "clauses": [ 7.79/2.92 [ 7.79/2.92 "(fl ([]) ([]) (0))", 7.79/2.92 null 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(fl (. E X) R (s Z))", 7.79/2.92 "(',' (append E Y R) (fl X Y Z))" 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(append ([]) X X)", 7.79/2.92 null 7.79/2.92 ], 7.79/2.92 [ 7.79/2.92 "(append (. X Xs) Ys (. X Zs))", 7.79/2.92 "(append Xs Ys Zs)" 7.79/2.92 ] 7.79/2.92 ] 7.79/2.92 }, 7.79/2.92 "graph": { 7.79/2.92 "nodes": { 7.79/2.92 "33": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "44": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(append T39 X47 T40)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": ["X47"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "34": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(append T16 X14 T17)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": ["X14"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "45": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "35": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(fl T22 T21 T15)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T15"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "36": { 7.79/2.92 "goal": [ 7.79/2.92 { 7.79/2.92 "clause": 2, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(append T16 X14 T17)" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "clause": 3, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(append T16 X14 T17)" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": ["X14"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "37": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 2, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(append T16 X14 T17)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": ["X14"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "38": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 3, 7.79/2.92 "scope": 2, 7.79/2.92 "term": "(append T16 X14 T17)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": ["X14"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "39": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(true)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "29": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(true)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "type": "Nodes", 7.79/2.92 "3": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "4": { 7.79/2.92 "goal": [ 7.79/2.92 { 7.79/2.92 "clause": 0, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "9": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 0, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "40": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "30": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "41": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "31": { 7.79/2.92 "goal": [], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": [], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "10": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": 1, 7.79/2.92 "scope": 1, 7.79/2.92 "term": "(fl T1 T2 T3)" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T3"], 7.79/2.92 "free": [], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "32": { 7.79/2.92 "goal": [{ 7.79/2.92 "clause": -1, 7.79/2.92 "scope": -1, 7.79/2.92 "term": "(',' (append T16 X14 T17) (fl T18 X14 T15))" 7.79/2.92 }], 7.79/2.92 "kb": { 7.79/2.92 "nonunifying": [], 7.79/2.92 "intvars": {}, 7.79/2.92 "arithmetic": { 7.79/2.92 "type": "PlainIntegerRelationState", 7.79/2.92 "relations": [] 7.79/2.92 }, 7.79/2.92 "ground": ["T15"], 7.79/2.92 "free": ["X14"], 7.79/2.92 "exprvars": [] 7.79/2.92 } 7.79/2.92 } 7.79/2.92 }, 7.79/2.92 "edges": [ 7.79/2.92 { 7.79/2.92 "from": 3, 7.79/2.92 "to": 4, 7.79/2.92 "label": "CASE" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 4, 7.79/2.92 "to": 9, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 4, 7.79/2.92 "to": 10, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 9, 7.79/2.92 "to": 29, 7.79/2.92 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 9, 7.79/2.92 "to": 30, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 10, 7.79/2.92 "to": 32, 7.79/2.92 "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T18,\nT1 -> .(T16, T18),\nT2 -> T17,\nX12 -> T17,\nX13 -> T15,\nT3 -> s(T15),\nT12 -> T16,\nT14 -> T17,\nT13 -> T18" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 10, 7.79/2.92 "to": 33, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 29, 7.79/2.92 "to": 31, 7.79/2.92 "label": "SUCCESS" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 32, 7.79/2.92 "to": 34, 7.79/2.92 "label": "SPLIT 1" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 32, 7.79/2.92 "to": 35, 7.79/2.92 "label": "SPLIT 2\nreplacements:X14 -> T21,\nT18 -> T22" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 34, 7.79/2.92 "to": 36, 7.79/2.92 "label": "CASE" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 35, 7.79/2.92 "to": 3, 7.79/2.92 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T15" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 36, 7.79/2.92 "to": 37, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 36, 7.79/2.92 "to": 38, 7.79/2.92 "label": "PARALLEL" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 37, 7.79/2.92 "to": 39, 7.79/2.92 "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T29,\nX31 -> T29,\nT17 -> T29,\nX32 -> T29" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 37, 7.79/2.92 "to": 40, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 38, 7.79/2.92 "to": 44, 7.79/2.92 "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T36,\nX44 -> T39,\nT16 -> .(T36, T39),\nX14 -> X47,\nX45 -> X47,\nX46 -> T40,\nT17 -> .(T36, T40),\nT37 -> T39,\nT38 -> T40" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 38, 7.79/2.92 "to": 45, 7.79/2.92 "label": "EVAL-BACKTRACK" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 39, 7.79/2.92 "to": 41, 7.79/2.92 "label": "SUCCESS" 7.79/2.92 }, 7.79/2.92 { 7.79/2.92 "from": 44, 7.79/2.92 "to": 34, 7.79/2.92 "label": "INSTANCE with matching:\nT16 -> T39\nX14 -> X47\nT17 -> T40" 7.79/2.92 } 7.79/2.92 ], 7.79/2.92 "type": "Graph" 7.79/2.92 } 7.79/2.92 } 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (16) 7.79/2.92 Obligation: 7.79/2.92 Q restricted rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f3_in(0) -> f3_out1 7.79/2.92 f3_in(s(T15)) -> U1(f32_in(T15), s(T15)) 7.79/2.92 U1(f32_out1, s(T15)) -> f3_out1 7.79/2.92 f34_in -> f34_out1 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 U2(f34_out1) -> f34_out1 7.79/2.92 f32_in(T15) -> U3(f34_in, T15) 7.79/2.92 U3(f34_out1, T15) -> U4(f3_in(T15), T15) 7.79/2.92 U4(f3_out1, T15) -> f32_out1 7.79/2.92 7.79/2.92 Q is empty. 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (17) QTRSRRRProof (EQUIVALENT) 7.79/2.92 Used ordering: 7.79/2.92 f3_in/1(YES) 7.79/2.92 0/0) 7.79/2.92 f3_out1/0) 7.79/2.92 s/1(YES) 7.79/2.92 U1/2(YES,YES) 7.79/2.92 f32_in/1(YES) 7.79/2.92 f32_out1/0) 7.79/2.92 f34_in/0) 7.79/2.92 f34_out1/0) 7.79/2.92 U2/1)YES( 7.79/2.92 U3/2(YES,YES) 7.79/2.92 U4/2(YES,YES) 7.79/2.92 7.79/2.92 Quasi precedence: 7.79/2.92 0 > f3_out1 > f32_out1 > [U1_2, U4_2] 7.79/2.92 s_1 > f3_out1 > f32_out1 > [U1_2, U4_2] 7.79/2.92 s_1 > f32_in_1 > [f34_in, f34_out1] > [f3_in_1, U3_2] > [U1_2, U4_2] 7.79/2.92 7.79/2.92 7.79/2.92 Status: 7.79/2.92 f3_in_1: multiset status 7.79/2.92 0: multiset status 7.79/2.92 f3_out1: multiset status 7.79/2.92 s_1: [1] 7.79/2.92 U1_2: multiset status 7.79/2.92 f32_in_1: multiset status 7.79/2.92 f32_out1: multiset status 7.79/2.92 f34_in: multiset status 7.79/2.92 f34_out1: multiset status 7.79/2.92 U3_2: multiset status 7.79/2.92 U4_2: [2,1] 7.79/2.92 7.79/2.92 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.79/2.92 7.79/2.92 f3_in(0) -> f3_out1 7.79/2.92 f3_in(s(T15)) -> U1(f32_in(T15), s(T15)) 7.79/2.92 U1(f32_out1, s(T15)) -> f3_out1 7.79/2.92 f32_in(T15) -> U3(f34_in, T15) 7.79/2.92 U3(f34_out1, T15) -> U4(f3_in(T15), T15) 7.79/2.92 U4(f3_out1, T15) -> f32_out1 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (18) 7.79/2.92 Obligation: 7.79/2.92 Q restricted rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f34_in -> f34_out1 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 U2(f34_out1) -> f34_out1 7.79/2.92 7.79/2.92 Q is empty. 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (19) QTRSRRRProof (EQUIVALENT) 7.79/2.92 Used ordering: 7.79/2.92 Polynomial interpretation [POLO]: 7.79/2.92 7.79/2.92 POL(U2(x_1)) = x_1 7.79/2.92 POL(f34_in) = 2 7.79/2.92 POL(f34_out1) = 0 7.79/2.92 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.79/2.92 7.79/2.92 f34_in -> f34_out1 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (20) 7.79/2.92 Obligation: 7.79/2.92 Q restricted rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 U2(f34_out1) -> f34_out1 7.79/2.92 7.79/2.92 Q is empty. 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (21) QTRSRRRProof (EQUIVALENT) 7.79/2.92 Used ordering: 7.79/2.92 Polynomial interpretation [POLO]: 7.79/2.92 7.79/2.92 POL(U2(x_1)) = 2*x_1 7.79/2.92 POL(f34_in) = 0 7.79/2.92 POL(f34_out1) = 1 7.79/2.92 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.79/2.92 7.79/2.92 U2(f34_out1) -> f34_out1 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (22) 7.79/2.92 Obligation: 7.79/2.92 Q restricted rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 7.79/2.92 Q is empty. 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (23) Overlay + Local Confluence (EQUIVALENT) 7.79/2.92 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (24) 7.79/2.92 Obligation: 7.79/2.92 Q restricted rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 7.79/2.92 The set Q consists of the following terms: 7.79/2.92 7.79/2.92 f34_in 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (25) DependencyPairsProof (EQUIVALENT) 7.79/2.92 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (26) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 F34_IN -> F34_IN 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 f34_in -> U2(f34_in) 7.79/2.92 7.79/2.92 The set Q consists of the following terms: 7.79/2.92 7.79/2.92 f34_in 7.79/2.92 7.79/2.92 We have to consider all minimal (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (27) UsableRulesProof (EQUIVALENT) 7.79/2.92 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. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (28) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 F34_IN -> F34_IN 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The set Q consists of the following terms: 7.79/2.92 7.79/2.92 f34_in 7.79/2.92 7.79/2.92 We have to consider all minimal (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (29) QReductionProof (EQUIVALENT) 7.79/2.92 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.79/2.92 7.79/2.92 f34_in 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (30) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 F34_IN -> F34_IN 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 Q is empty. 7.79/2.92 We have to consider all minimal (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (31) NonTerminationLoopProof (COMPLETE) 7.79/2.92 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.79/2.92 Found a loop by semiunifying a rule from P directly. 7.79/2.92 7.79/2.92 s = F34_IN evaluates to t =F34_IN 7.79/2.92 7.79/2.92 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.79/2.92 * Matcher: [ ] 7.79/2.92 * Semiunifier: [ ] 7.79/2.92 7.79/2.92 -------------------------------------------------------------------------------- 7.79/2.92 Rewriting sequence 7.79/2.92 7.79/2.92 The DP semiunifies directly so there is only one rewrite step from F34_IN to F34_IN. 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (32) 7.79/2.92 NO 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (33) PrologToPiTRSProof (SOUND) 7.79/2.92 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.79/2.92 7.79/2.92 fl_in_3: (f,f,b) 7.79/2.92 7.79/2.92 append_in_3: (f,f,f) 7.79/2.92 7.79/2.92 Transforming Prolog into the following Term Rewriting System: 7.79/2.92 7.79/2.92 Pi-finite rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (34) 7.79/2.92 Obligation: 7.79/2.92 Pi-finite rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (35) DependencyPairsProof (EQUIVALENT) 7.79/2.92 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> APPEND_IN_AAA(E, Y, R) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_AAG(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 7.79/2.92 7.79/2.92 U2_AAG(x1, x2, x3, x4, x5) = U2_AAG(x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (36) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> APPEND_IN_AAA(E, Y, R) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_AAG(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 7.79/2.92 7.79/2.92 U2_AAG(x1, x2, x3, x4, x5) = U2_AAG(x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (37) DependencyGraphProof (EQUIVALENT) 7.79/2.92 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (38) 7.79/2.92 Complex Obligation (AND) 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (39) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (40) UsableRulesProof (EQUIVALENT) 7.79/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (41) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (42) PiDPToQDPProof (SOUND) 7.79/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (43) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 APPEND_IN_AAA -> APPEND_IN_AAA 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 Q is empty. 7.79/2.92 We have to consider all (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (44) NonTerminationLoopProof (COMPLETE) 7.79/2.92 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.79/2.92 Found a loop by semiunifying a rule from P directly. 7.79/2.92 7.79/2.92 s = APPEND_IN_AAA evaluates to t =APPEND_IN_AAA 7.79/2.92 7.79/2.92 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.79/2.92 * Matcher: [ ] 7.79/2.92 * Semiunifier: [ ] 7.79/2.92 7.79/2.92 -------------------------------------------------------------------------------- 7.79/2.92 Rewriting sequence 7.79/2.92 7.79/2.92 The DP semiunifies directly so there is only one rewrite step from APPEND_IN_AAA to APPEND_IN_AAA. 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (45) 7.79/2.92 NO 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (46) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (47) UsableRulesProof (EQUIVALENT) 7.79/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (48) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (49) PiDPToQDPProof (SOUND) 7.79/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (50) 7.79/2.92 Obligation: 7.79/2.92 Q DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 U1_AAG(Z, append_out_aaa) -> FL_IN_AAG(Z) 7.79/2.92 FL_IN_AAG(s(Z)) -> U1_AAG(Z, append_in_aaa) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 append_in_aaa -> append_out_aaa 7.79/2.92 append_in_aaa -> U3_aaa(append_in_aaa) 7.79/2.92 U3_aaa(append_out_aaa) -> append_out_aaa 7.79/2.92 7.79/2.92 The set Q consists of the following terms: 7.79/2.92 7.79/2.92 append_in_aaa 7.79/2.92 U3_aaa(x0) 7.79/2.92 7.79/2.92 We have to consider all (P,Q,R)-chains. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (51) QDPSizeChangeProof (EQUIVALENT) 7.79/2.92 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 7.79/2.92 7.79/2.92 From the DPs we obtained the following set of size-change graphs: 7.79/2.92 *FL_IN_AAG(s(Z)) -> U1_AAG(Z, append_in_aaa) 7.79/2.92 The graph contains the following edges 1 > 1 7.79/2.92 7.79/2.92 7.79/2.92 *U1_AAG(Z, append_out_aaa) -> FL_IN_AAG(Z) 7.79/2.92 The graph contains the following edges 1 >= 1 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (52) 7.79/2.92 YES 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (53) PrologToPiTRSProof (SOUND) 7.79/2.92 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.79/2.92 7.79/2.92 fl_in_3: (f,f,b) 7.79/2.92 7.79/2.92 append_in_3: (f,f,f) 7.79/2.92 7.79/2.92 Transforming Prolog into the following Term Rewriting System: 7.79/2.92 7.79/2.92 Pi-finite rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (54) 7.79/2.92 Obligation: 7.79/2.92 Pi-finite rewrite system: 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (55) DependencyPairsProof (EQUIVALENT) 7.79/2.92 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> APPEND_IN_AAA(E, Y, R) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_AAG(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 7.79/2.92 7.79/2.92 U2_AAG(x1, x2, x3, x4, x5) = U2_AAG(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (56) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 FL_IN_AAG(.(E, X), R, s(Z)) -> APPEND_IN_AAA(E, Y, R) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_AAG(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.92 7.79/2.92 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.92 7.79/2.92 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) 7.79/2.92 7.79/2.92 U2_AAG(x1, x2, x3, x4, x5) = U2_AAG(x4, x5) 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (57) DependencyGraphProof (EQUIVALENT) 7.79/2.92 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (58) 7.79/2.92 Complex Obligation (AND) 7.79/2.92 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (59) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 7.79/2.92 The TRS R consists of the following rules: 7.79/2.92 7.79/2.92 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.92 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.92 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.92 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.92 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.92 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.92 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.92 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.92 7.79/2.92 0 = 0 7.79/2.92 7.79/2.92 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.92 7.79/2.92 s(x1) = s(x1) 7.79/2.92 7.79/2.92 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.92 7.79/2.92 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.92 7.79/2.92 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.92 7.79/2.92 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.92 7.79/2.92 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.92 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (60) UsableRulesProof (EQUIVALENT) 7.79/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (61) 7.79/2.92 Obligation: 7.79/2.92 Pi DP problem: 7.79/2.92 The TRS P consists of the following rules: 7.79/2.92 7.79/2.92 APPEND_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAA(Xs, Ys, Zs) 7.79/2.92 7.79/2.92 R is empty. 7.79/2.92 The argument filtering Pi contains the following mapping: 7.79/2.92 APPEND_IN_AAA(x1, x2, x3) = APPEND_IN_AAA 7.79/2.92 7.79/2.92 7.79/2.92 We have to consider all (P,R,Pi)-chains 7.79/2.92 ---------------------------------------- 7.79/2.92 7.79/2.92 (62) PiDPToQDPProof (SOUND) 7.79/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.79/2.92 ---------------------------------------- 7.79/2.93 7.79/2.93 (63) 7.79/2.93 Obligation: 7.79/2.93 Q DP problem: 7.79/2.93 The TRS P consists of the following rules: 7.79/2.93 7.79/2.93 APPEND_IN_AAA -> APPEND_IN_AAA 7.79/2.93 7.79/2.93 R is empty. 7.79/2.93 Q is empty. 7.79/2.93 We have to consider all (P,Q,R)-chains. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (64) NonTerminationLoopProof (COMPLETE) 7.79/2.93 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.79/2.93 Found a loop by semiunifying a rule from P directly. 7.79/2.93 7.79/2.93 s = APPEND_IN_AAA evaluates to t =APPEND_IN_AAA 7.79/2.93 7.79/2.93 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.79/2.93 * Matcher: [ ] 7.79/2.93 * Semiunifier: [ ] 7.79/2.93 7.79/2.93 -------------------------------------------------------------------------------- 7.79/2.93 Rewriting sequence 7.79/2.93 7.79/2.93 The DP semiunifies directly so there is only one rewrite step from APPEND_IN_AAA to APPEND_IN_AAA. 7.79/2.93 7.79/2.93 7.79/2.93 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (65) 7.79/2.93 NO 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (66) 7.79/2.93 Obligation: 7.79/2.93 Pi DP problem: 7.79/2.93 The TRS P consists of the following rules: 7.79/2.93 7.79/2.93 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.93 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.93 7.79/2.93 The TRS R consists of the following rules: 7.79/2.93 7.79/2.93 fl_in_aag([], [], 0) -> fl_out_aag([], [], 0) 7.79/2.93 fl_in_aag(.(E, X), R, s(Z)) -> U1_aag(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.93 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.93 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.93 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.93 U1_aag(E, X, R, Z, append_out_aaa(E, Y, R)) -> U2_aag(E, X, R, Z, fl_in_aag(X, Y, Z)) 7.79/2.93 U2_aag(E, X, R, Z, fl_out_aag(X, Y, Z)) -> fl_out_aag(.(E, X), R, s(Z)) 7.79/2.93 7.79/2.93 The argument filtering Pi contains the following mapping: 7.79/2.93 fl_in_aag(x1, x2, x3) = fl_in_aag(x3) 7.79/2.93 7.79/2.93 0 = 0 7.79/2.93 7.79/2.93 fl_out_aag(x1, x2, x3) = fl_out_aag(x3) 7.79/2.93 7.79/2.93 s(x1) = s(x1) 7.79/2.93 7.79/2.93 U1_aag(x1, x2, x3, x4, x5) = U1_aag(x4, x5) 7.79/2.93 7.79/2.93 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.93 7.79/2.93 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.93 7.79/2.93 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.93 7.79/2.93 U2_aag(x1, x2, x3, x4, x5) = U2_aag(x4, x5) 7.79/2.93 7.79/2.93 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.93 7.79/2.93 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.93 7.79/2.93 7.79/2.93 We have to consider all (P,R,Pi)-chains 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (67) UsableRulesProof (EQUIVALENT) 7.79/2.93 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (68) 7.79/2.93 Obligation: 7.79/2.93 Pi DP problem: 7.79/2.93 The TRS P consists of the following rules: 7.79/2.93 7.79/2.93 U1_AAG(E, X, R, Z, append_out_aaa(E, Y, R)) -> FL_IN_AAG(X, Y, Z) 7.79/2.93 FL_IN_AAG(.(E, X), R, s(Z)) -> U1_AAG(E, X, R, Z, append_in_aaa(E, Y, R)) 7.79/2.93 7.79/2.93 The TRS R consists of the following rules: 7.79/2.93 7.79/2.93 append_in_aaa([], X, X) -> append_out_aaa([], X, X) 7.79/2.93 append_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, append_in_aaa(Xs, Ys, Zs)) 7.79/2.93 U3_aaa(X, Xs, Ys, Zs, append_out_aaa(Xs, Ys, Zs)) -> append_out_aaa(.(X, Xs), Ys, .(X, Zs)) 7.79/2.93 7.79/2.93 The argument filtering Pi contains the following mapping: 7.79/2.93 s(x1) = s(x1) 7.79/2.93 7.79/2.93 append_in_aaa(x1, x2, x3) = append_in_aaa 7.79/2.93 7.79/2.93 append_out_aaa(x1, x2, x3) = append_out_aaa 7.79/2.93 7.79/2.93 U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) 7.79/2.93 7.79/2.93 FL_IN_AAG(x1, x2, x3) = FL_IN_AAG(x3) 7.79/2.93 7.79/2.93 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x4, x5) 7.79/2.93 7.79/2.93 7.79/2.93 We have to consider all (P,R,Pi)-chains 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (69) PiDPToQDPProof (SOUND) 7.79/2.93 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (70) 7.79/2.93 Obligation: 7.79/2.93 Q DP problem: 7.79/2.93 The TRS P consists of the following rules: 7.79/2.93 7.79/2.93 U1_AAG(Z, append_out_aaa) -> FL_IN_AAG(Z) 7.79/2.93 FL_IN_AAG(s(Z)) -> U1_AAG(Z, append_in_aaa) 7.79/2.93 7.79/2.93 The TRS R consists of the following rules: 7.79/2.93 7.79/2.93 append_in_aaa -> append_out_aaa 7.79/2.93 append_in_aaa -> U3_aaa(append_in_aaa) 7.79/2.93 U3_aaa(append_out_aaa) -> append_out_aaa 7.79/2.93 7.79/2.93 The set Q consists of the following terms: 7.79/2.93 7.79/2.93 append_in_aaa 7.79/2.93 U3_aaa(x0) 7.79/2.93 7.79/2.93 We have to consider all (P,Q,R)-chains. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (71) QDPSizeChangeProof (EQUIVALENT) 7.79/2.93 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 7.79/2.93 7.79/2.93 From the DPs we obtained the following set of size-change graphs: 7.79/2.93 *FL_IN_AAG(s(Z)) -> U1_AAG(Z, append_in_aaa) 7.79/2.93 The graph contains the following edges 1 > 1 7.79/2.93 7.79/2.93 7.79/2.93 *U1_AAG(Z, append_out_aaa) -> FL_IN_AAG(Z) 7.79/2.93 The graph contains the following edges 1 >= 1 7.79/2.93 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (72) 7.79/2.93 YES 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (73) PrologToIRSwTTransformerProof (SOUND) 7.79/2.93 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 7.79/2.93 7.79/2.93 { 7.79/2.93 "root": 2, 7.79/2.93 "program": { 7.79/2.93 "directives": [], 7.79/2.93 "clauses": [ 7.79/2.93 [ 7.79/2.93 "(fl ([]) ([]) (0))", 7.79/2.93 null 7.79/2.93 ], 7.79/2.93 [ 7.79/2.93 "(fl (. E X) R (s Z))", 7.79/2.93 "(',' (append E Y R) (fl X Y Z))" 7.79/2.93 ], 7.79/2.93 [ 7.79/2.93 "(append ([]) X X)", 7.79/2.93 null 7.79/2.93 ], 7.79/2.93 [ 7.79/2.93 "(append (. X Xs) Ys (. X Zs))", 7.79/2.93 "(append Xs Ys Zs)" 7.79/2.93 ] 7.79/2.93 ] 7.79/2.93 }, 7.79/2.93 "graph": { 7.79/2.93 "nodes": { 7.79/2.93 "11": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(true)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "13": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "46": { 7.79/2.93 "goal": [ 7.79/2.93 { 7.79/2.93 "clause": 2, 7.79/2.93 "scope": 2, 7.79/2.93 "term": "(append T16 X14 T17)" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "clause": 3, 7.79/2.93 "scope": 2, 7.79/2.93 "term": "(append T16 X14 T17)" 7.79/2.93 } 7.79/2.93 ], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": ["X14"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "47": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": 2, 7.79/2.93 "scope": 2, 7.79/2.93 "term": "(append T16 X14 T17)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": ["X14"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "15": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "48": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": 3, 7.79/2.93 "scope": 2, 7.79/2.93 "term": "(append T16 X14 T17)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": ["X14"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "27": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(append T16 X14 T17)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": ["X14"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "49": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(true)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "28": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(fl T22 T21 T15)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T15"], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "18": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(',' (append T16 X14 T17) (fl T18 X14 T15))" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T15"], 7.79/2.93 "free": ["X14"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "19": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "type": "Nodes", 7.79/2.93 "2": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(fl T1 T2 T3)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T3"], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "5": { 7.79/2.93 "goal": [ 7.79/2.93 { 7.79/2.93 "clause": 0, 7.79/2.93 "scope": 1, 7.79/2.93 "term": "(fl T1 T2 T3)" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "clause": 1, 7.79/2.93 "scope": 1, 7.79/2.93 "term": "(fl T1 T2 T3)" 7.79/2.93 } 7.79/2.93 ], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T3"], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "7": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": 0, 7.79/2.93 "scope": 1, 7.79/2.93 "term": "(fl T1 T2 T3)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T3"], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "8": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": 1, 7.79/2.93 "scope": 1, 7.79/2.93 "term": "(fl T1 T2 T3)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": ["T3"], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "50": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "51": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "52": { 7.79/2.93 "goal": [{ 7.79/2.93 "clause": -1, 7.79/2.93 "scope": -1, 7.79/2.93 "term": "(append T39 X47 T40)" 7.79/2.93 }], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": ["X47"], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "53": { 7.79/2.93 "goal": [], 7.79/2.93 "kb": { 7.79/2.93 "nonunifying": [], 7.79/2.93 "intvars": {}, 7.79/2.93 "arithmetic": { 7.79/2.93 "type": "PlainIntegerRelationState", 7.79/2.93 "relations": [] 7.79/2.93 }, 7.79/2.93 "ground": [], 7.79/2.93 "free": [], 7.79/2.93 "exprvars": [] 7.79/2.93 } 7.79/2.93 } 7.79/2.93 }, 7.79/2.93 "edges": [ 7.79/2.93 { 7.79/2.93 "from": 2, 7.79/2.93 "to": 5, 7.79/2.93 "label": "CASE" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 5, 7.79/2.93 "to": 7, 7.79/2.93 "label": "PARALLEL" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 5, 7.79/2.93 "to": 8, 7.79/2.93 "label": "PARALLEL" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 7, 7.79/2.93 "to": 11, 7.79/2.93 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 7, 7.79/2.93 "to": 13, 7.79/2.93 "label": "EVAL-BACKTRACK" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 8, 7.79/2.93 "to": 18, 7.79/2.93 "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T18,\nT1 -> .(T16, T18),\nT2 -> T17,\nX12 -> T17,\nX13 -> T15,\nT3 -> s(T15),\nT12 -> T16,\nT14 -> T17,\nT13 -> T18" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 8, 7.79/2.93 "to": 19, 7.79/2.93 "label": "EVAL-BACKTRACK" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 11, 7.79/2.93 "to": 15, 7.79/2.93 "label": "SUCCESS" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 18, 7.79/2.93 "to": 27, 7.79/2.93 "label": "SPLIT 1" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 18, 7.79/2.93 "to": 28, 7.79/2.93 "label": "SPLIT 2\nreplacements:X14 -> T21,\nT18 -> T22" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 27, 7.79/2.93 "to": 46, 7.79/2.93 "label": "CASE" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 28, 7.79/2.93 "to": 2, 7.79/2.93 "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T15" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 46, 7.79/2.93 "to": 47, 7.79/2.93 "label": "PARALLEL" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 46, 7.79/2.93 "to": 48, 7.79/2.93 "label": "PARALLEL" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 47, 7.79/2.93 "to": 49, 7.79/2.93 "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T29,\nX31 -> T29,\nT17 -> T29,\nX32 -> T29" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 47, 7.79/2.93 "to": 50, 7.79/2.93 "label": "EVAL-BACKTRACK" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 48, 7.79/2.93 "to": 52, 7.79/2.93 "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T36,\nX44 -> T39,\nT16 -> .(T36, T39),\nX14 -> X47,\nX45 -> X47,\nX46 -> T40,\nT17 -> .(T36, T40),\nT37 -> T39,\nT38 -> T40" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 48, 7.79/2.93 "to": 53, 7.79/2.93 "label": "EVAL-BACKTRACK" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 49, 7.79/2.93 "to": 51, 7.79/2.93 "label": "SUCCESS" 7.79/2.93 }, 7.79/2.93 { 7.79/2.93 "from": 52, 7.79/2.93 "to": 27, 7.79/2.93 "label": "INSTANCE with matching:\nT16 -> T39\nX14 -> X47\nT17 -> T40" 7.79/2.93 } 7.79/2.93 ], 7.79/2.93 "type": "Graph" 7.79/2.93 } 7.79/2.93 } 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (74) 7.79/2.93 Complex Obligation (AND) 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (75) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f27_out -> f52_out :|: TRUE 7.79/2.93 f46_in -> f47_in :|: TRUE 7.79/2.93 f48_out -> f46_out :|: TRUE 7.79/2.93 f47_out -> f46_out :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f52_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f53_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f53_in :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 f46_out -> f27_out :|: TRUE 7.79/2.93 f5_out(T3) -> f2_out(T3) :|: TRUE 7.79/2.93 f2_in(x) -> f5_in(x) :|: TRUE 7.79/2.93 f7_out(x1) -> f5_out(x1) :|: TRUE 7.79/2.93 f5_in(x2) -> f7_in(x2) :|: TRUE 7.79/2.93 f5_in(x3) -> f8_in(x3) :|: TRUE 7.79/2.93 f8_out(x4) -> f5_out(x4) :|: TRUE 7.79/2.93 f8_in(x5) -> f19_in :|: TRUE 7.79/2.93 f19_out -> f8_out(x6) :|: TRUE 7.79/2.93 f18_out(T15) -> f8_out(s(T15)) :|: TRUE 7.79/2.93 f8_in(s(x7)) -> f18_in(x7) :|: TRUE 7.79/2.93 f28_out(x8) -> f18_out(x8) :|: TRUE 7.79/2.93 f18_in(x9) -> f27_in :|: TRUE 7.79/2.93 f27_out -> f28_in(x10) :|: TRUE 7.79/2.93 Start term: f2_in(T3) 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (76) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 7.79/2.93 Constructed simple dependency graph. 7.79/2.93 7.79/2.93 Simplified to the following IRSwTs: 7.79/2.93 7.79/2.93 intTRSProblem: 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (77) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (78) IntTRSCompressionProof (EQUIVALENT) 7.79/2.93 Compressed rules. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (79) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f46_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (80) IRSFormatTransformerProof (EQUIVALENT) 7.79/2.93 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (81) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f46_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (82) IRSwTTerminationDigraphProof (EQUIVALENT) 7.79/2.93 Constructed termination digraph! 7.79/2.93 Nodes: 7.79/2.93 (1) f46_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 Arcs: 7.79/2.93 (1) -> (1) 7.79/2.93 7.79/2.93 This digraph is fully evaluated! 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (83) 7.79/2.93 Obligation: 7.79/2.93 7.79/2.93 Termination digraph: 7.79/2.93 Nodes: 7.79/2.93 (1) f46_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 Arcs: 7.79/2.93 (1) -> (1) 7.79/2.93 7.79/2.93 This digraph is fully evaluated! 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (84) FilterProof (EQUIVALENT) 7.79/2.93 Used the following sort dictionary for filtering: 7.79/2.93 f46_in() 7.79/2.93 Replaced non-predefined constructor symbols by 0. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (85) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f46_in -> f46_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (86) IntTRSPeriodicNontermProof (COMPLETE) 7.79/2.93 Normalized system to the following form: 7.79/2.93 f(pc) -> f(1) :|: pc = 1 && TRUE 7.79/2.93 Witness term starting non-terminating reduction: f(1) 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (87) 7.79/2.93 NO 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (88) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f7_out(T3) -> f5_out(T3) :|: TRUE 7.79/2.93 f5_in(x) -> f7_in(x) :|: TRUE 7.79/2.93 f5_in(x1) -> f8_in(x1) :|: TRUE 7.79/2.93 f8_out(x2) -> f5_out(x2) :|: TRUE 7.79/2.93 f5_out(x3) -> f2_out(x3) :|: TRUE 7.79/2.93 f2_in(x4) -> f5_in(x4) :|: TRUE 7.79/2.93 f49_in -> f49_out :|: TRUE 7.79/2.93 f46_in -> f47_in :|: TRUE 7.79/2.93 f48_out -> f46_out :|: TRUE 7.79/2.93 f47_out -> f46_out :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f8_in(x5) -> f19_in :|: TRUE 7.79/2.93 f19_out -> f8_out(x6) :|: TRUE 7.79/2.93 f18_out(T15) -> f8_out(s(T15)) :|: TRUE 7.79/2.93 f8_in(s(x7)) -> f18_in(x7) :|: TRUE 7.79/2.93 f28_in(x8) -> f2_in(x8) :|: TRUE 7.79/2.93 f2_out(x9) -> f28_out(x9) :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 f46_out -> f27_out :|: TRUE 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f27_out -> f52_out :|: TRUE 7.79/2.93 f49_out -> f47_out :|: TRUE 7.79/2.93 f47_in -> f50_in :|: TRUE 7.79/2.93 f50_out -> f47_out :|: TRUE 7.79/2.93 f47_in -> f49_in :|: TRUE 7.79/2.93 f52_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f53_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f53_in :|: TRUE 7.79/2.93 f28_out(x10) -> f18_out(x10) :|: TRUE 7.79/2.93 f18_in(x11) -> f27_in :|: TRUE 7.79/2.93 f27_out -> f28_in(x12) :|: TRUE 7.79/2.93 Start term: f2_in(T3) 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (89) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 7.79/2.93 Constructed simple dependency graph. 7.79/2.93 7.79/2.93 Simplified to the following IRSwTs: 7.79/2.93 7.79/2.93 intTRSProblem: 7.79/2.93 f5_in(x1) -> f8_in(x1) :|: TRUE 7.79/2.93 f2_in(x4) -> f5_in(x4) :|: TRUE 7.79/2.93 f49_in -> f49_out :|: TRUE 7.79/2.93 f46_in -> f47_in :|: TRUE 7.79/2.93 f48_out -> f46_out :|: TRUE 7.79/2.93 f47_out -> f46_out :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f8_in(s(x7)) -> f18_in(x7) :|: TRUE 7.79/2.93 f28_in(x8) -> f2_in(x8) :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 f46_out -> f27_out :|: TRUE 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f27_out -> f52_out :|: TRUE 7.79/2.93 f49_out -> f47_out :|: TRUE 7.79/2.93 f47_in -> f49_in :|: TRUE 7.79/2.93 f52_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f18_in(x11) -> f27_in :|: TRUE 7.79/2.93 f27_out -> f28_in(x12) :|: TRUE 7.79/2.93 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (90) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f5_in(x1) -> f8_in(x1) :|: TRUE 7.79/2.93 f2_in(x4) -> f5_in(x4) :|: TRUE 7.79/2.93 f49_in -> f49_out :|: TRUE 7.79/2.93 f46_in -> f47_in :|: TRUE 7.79/2.93 f48_out -> f46_out :|: TRUE 7.79/2.93 f47_out -> f46_out :|: TRUE 7.79/2.93 f46_in -> f48_in :|: TRUE 7.79/2.93 f8_in(s(x7)) -> f18_in(x7) :|: TRUE 7.79/2.93 f28_in(x8) -> f2_in(x8) :|: TRUE 7.79/2.93 f27_in -> f46_in :|: TRUE 7.79/2.93 f46_out -> f27_out :|: TRUE 7.79/2.93 f52_in -> f27_in :|: TRUE 7.79/2.93 f27_out -> f52_out :|: TRUE 7.79/2.93 f49_out -> f47_out :|: TRUE 7.79/2.93 f47_in -> f49_in :|: TRUE 7.79/2.93 f52_out -> f48_out :|: TRUE 7.79/2.93 f48_in -> f52_in :|: TRUE 7.79/2.93 f18_in(x11) -> f27_in :|: TRUE 7.79/2.93 f27_out -> f28_in(x12) :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (91) IntTRSCompressionProof (EQUIVALENT) 7.79/2.93 Compressed rules. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (92) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f27_in -> f27_out :|: TRUE 7.79/2.93 f27_out -> f27_out :|: TRUE 7.79/2.93 f27_out -> f27_in :|: TRUE 7.79/2.93 f27_in -> f27_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (93) IRSFormatTransformerProof (EQUIVALENT) 7.79/2.93 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (94) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f27_in -> f27_out :|: TRUE 7.79/2.93 f27_out -> f27_out :|: TRUE 7.79/2.93 f27_out -> f27_in :|: TRUE 7.79/2.93 f27_in -> f27_in :|: TRUE 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (95) IRSwTTerminationDigraphProof (EQUIVALENT) 7.79/2.93 Constructed termination digraph! 7.79/2.93 Nodes: 7.79/2.93 (1) f27_in -> f27_out :|: TRUE 7.79/2.93 (2) f27_out -> f27_out :|: TRUE 7.79/2.93 (3) f27_out -> f27_in :|: TRUE 7.79/2.93 (4) f27_in -> f27_in :|: TRUE 7.79/2.93 7.79/2.93 Arcs: 7.79/2.93 (1) -> (2), (3) 7.79/2.93 (2) -> (2), (3) 7.79/2.93 (3) -> (1), (4) 7.79/2.93 (4) -> (1), (4) 7.79/2.93 7.79/2.93 This digraph is fully evaluated! 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (96) 7.79/2.93 Obligation: 7.79/2.93 7.79/2.93 Termination digraph: 7.79/2.93 Nodes: 7.79/2.93 (1) f27_in -> f27_out :|: TRUE 7.79/2.93 (2) f27_in -> f27_in :|: TRUE 7.79/2.93 (3) f27_out -> f27_in :|: TRUE 7.79/2.93 (4) f27_out -> f27_out :|: TRUE 7.79/2.93 7.79/2.93 Arcs: 7.79/2.93 (1) -> (3), (4) 7.79/2.93 (2) -> (1), (2) 7.79/2.93 (3) -> (1), (2) 7.79/2.93 (4) -> (3), (4) 7.79/2.93 7.79/2.93 This digraph is fully evaluated! 7.79/2.93 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (97) FilterProof (EQUIVALENT) 7.79/2.93 Used the following sort dictionary for filtering: 7.79/2.93 f27_in() 7.79/2.93 f27_out() 7.79/2.93 Replaced non-predefined constructor symbols by 0. 7.79/2.93 ---------------------------------------- 7.79/2.93 7.79/2.93 (98) 7.79/2.93 Obligation: 7.79/2.93 Rules: 7.79/2.93 f27_in -> f27_out :|: TRUE 7.79/2.93 f27_in -> f27_in :|: TRUE 7.79/2.93 f27_out -> f27_in :|: TRUE 7.79/2.93 f27_out -> f27_out :|: TRUE 7.94/3.02 EOF