Left Termination proof of /tmp/tmpjUEiDo/flat-fb.pl

Left Termination of the query pattern flat_in_2(a, g) w.r.t. the given Prolog program could not be shown:

0 Prolog

↳1 PrologToDTProblemTransformerProof (⇐)

↳2 TRIPLES

↳3 TriplesToPiDPProof (⇐)

↳4 PiDP

↳5 DependencyGraphProof (⇔)

↳6 AND

    ↳7 PiDP

        ↳8 PiDPToQDPProof (⇐)

        ↳9 QDP

        ↳10 NonTerminationProof (⇔)

        ↳11 NO

    ↳12 PiDP

        ↳13 PiDPToQDPProof (⇐)

        ↳14 QDP

        ↳15 UsableRulesReductionPairsProof (⇔)

        ↳16 QDP

        ↳17 NonTerminationProof (⇔)

        ↳18 NO

(0) Obligation:

Clauses:

flat([], []).
flat(.([], T), R) :- flat(T, R).
flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R).

Queries:

flat(a,g).

(1) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph.

digraph dp_graph {
node [outthreshold=100, inthreshold=100];
1 [label="1: flat(T1, T2)\n\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow, color=red];
2 [label="2: flat(T1, T2), SCOPE: 1, CLAUSE: 0 | flat(T1, T2), SCOPE: 1, CLAUSE: 1 | flat(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
3 [label="3: true | flat(T1, []), SCOPE: 1, CLAUSE: 1 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
4 [label="4: flat(T1, T2), SCOPE: 1, CLAUSE: 1 | flat(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground\nflat(T1, T2) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
5 [label="5: flat(T1, []), SCOPE: 1, CLAUSE: 1 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
6 [label="6: flat(T5, []) | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
7 [label="7: flat(T1, []), SCOPE: 1, CLAUSE: 2\n\nflat(T1, []) !=? flat(.([], X3), X4)", fontsize=16, style=filled, fillcolor=lightyellow];
8 [label="8: flat(T5, []), SCOPE: 2, CLAUSE: 0 | flat(T5, []), SCOPE: 2, CLAUSE: 1 | flat(T5, []), SCOPE: 2, CLAUSE: 2 | ?_2 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
9 [label="9: flat(T5, []), SCOPE: 2, CLAUSE: 0\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
10 [label="10: flat(T5, []), SCOPE: 2, CLAUSE: 1 | flat(T5, []), SCOPE: 2, CLAUSE: 2 | ?_2 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
11 [label="11: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
12 [label="12: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
13 [label="13: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
14 [label="14: flat(T5, []), SCOPE: 2, CLAUSE: 1\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
15 [label="15: flat(T5, []), SCOPE: 2, CLAUSE: 2 | ?_2 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
16 [label="16: flat(T11, [])\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
17 [label="17: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
18 [label="18: flat(T11, []), SCOPE: 3, CLAUSE: 0 | flat(T11, []), SCOPE: 3, CLAUSE: 1 | flat(T11, []), SCOPE: 3, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
19 [label="19: flat(T11, []), SCOPE: 3, CLAUSE: 0\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
20 [label="20: flat(T11, []), SCOPE: 3, CLAUSE: 1 | flat(T11, []), SCOPE: 3, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
21 [label="21: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
22 [label="22: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
23 [label="23: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
24 [label="24: flat(T11, []), SCOPE: 3, CLAUSE: 1\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
25 [label="25: flat(T11, []), SCOPE: 3, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
26 [label="26: flat(T17, [])\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
27 [label="27: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
28 [label="28: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
29 [label="29: ?_2 | flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
30 [label="30: flat(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
31 [label="31: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
32 [label="32: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
33 [label="33: flat(T34, T33) | flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
34 [label="34: flat(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground\nflat(T1, T2) !=? flat([], [])\nflat(T1, T2) !=? flat(.([], X49), X50)", fontsize=16, style=filled, fillcolor=lightyellow];
35 [label="35: flat(T34, T33), SCOPE: 4, CLAUSE: 0 | flat(T34, T33), SCOPE: 4, CLAUSE: 1 | flat(T34, T33), SCOPE: 4, CLAUSE: 2 | ?_4 | flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
36 [label="36: flat(T34, T33), SCOPE: 4, CLAUSE: 0\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
37 [label="37: flat(T34, T33), SCOPE: 4, CLAUSE: 1 | flat(T34, T33), SCOPE: 4, CLAUSE: 2 | ?_4 | flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
38 [label="38: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
39 [label="39: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
40 [label="40: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
41 [label="41: flat(T34, T33), SCOPE: 4, CLAUSE: 1\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
42 [label="42: flat(T34, T33), SCOPE: 4, CLAUSE: 2 | ?_4 | flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
43 [label="43: flat(T45, T44)\n\nT44 is ground\nflat(T1, T44) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
44 [label="44: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
45 [label="45: flat(T34, T33), SCOPE: 4, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
46 [label="46: ?_4 | flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
47 [label="47: flat(.(T66, T67), T65)\n\nT65 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
48 [label="48: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
49 [label="49: flat(T1, T33), SCOPE: 1, CLAUSE: 2\n\nT33 is ground\nflat(T1, T33) !=? flat([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
50 [label="50: flat(.(T82, T83), T81)\n\nT81 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
51 [label="51: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
52 [label="52: flat(.(T94, T95), T93)\n\nT93 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
53 [label="53: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
54 [label="54: flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 0 | flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 1 | flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 2\n\nT93 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
55 [label="55: flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 1 | flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 2\n\nT93 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
56 [label="56: flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 1\n\nT93 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
57 [label="57: flat(.(T94, T95), T93), SCOPE: 5, CLAUSE: 2\n\nT93 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
58 [label="58: flat(T106, T105)\n\nT105 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
59 [label="59: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
60 [label="60: flat(.(T119, T120), T118)\n\nT118 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
61 [label="61: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
62 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
1 -> 62 [arrowhead = none ];
62 -> 2;

63 [label="EVAL with clause\nflat([], []).\nand substitution\nT1 -> []\nT2 -> []", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 63 [arrowhead = none ];
63 -> 3;

64 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 64 [arrowhead = none ];
64 -> 4;

65 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
3 -> 65 [arrowhead = none ];
65 -> 5;

66 [label="EVAL with clause\nflat(.([], X49), X50) :- flat(X49, X50).\nand substitution\nX49 -> T34\nT1 -> .([], T34)\nT2 -> T33\nX50 -> T33\nT32 -> T34", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 66 [arrowhead = none ];
66 -> 33;

67 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 67 [arrowhead = none ];
67 -> 34;

68 [label="EVAL with clause\nflat(.([], X3), X4) :- flat(X3, X4).\nand substitution\nX3 -> T5\nT1 -> .([], T5)\nX4 -> []\nT4 -> T5", fontsize=14, style = filled, fillcolor = lightblue];
5 -> 68 [arrowhead = none ];
68 -> 6;

69 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
5 -> 69 [arrowhead = none ];
69 -> 7;

70 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
6 -> 70 [arrowhead = none ];
70 -> 8;

71 [label="BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification", fontsize=14, style = filled, fillcolor = white];
7 -> 71 [arrowhead = none ];
71 -> 32;

72 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
8 -> 72 [arrowhead = none ];
72 -> 9;

73 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
8 -> 73 [arrowhead = none ];
73 -> 10;

74 [label="EVAL with clause\nflat([], []).\nand substitution\nT5 -> []", fontsize=14, style = filled, fillcolor = lightblue];
9 -> 74 [arrowhead = none ];
74 -> 11;

75 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
9 -> 75 [arrowhead = none ];
75 -> 12;

76 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
10 -> 76 [arrowhead = none ];
76 -> 14;

77 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
10 -> 77 [arrowhead = none ];
77 -> 15;

78 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
11 -> 78 [arrowhead = none ];
78 -> 13;

79 [label="EVAL with clause\nflat(.([], X15), X16) :- flat(X15, X16).\nand substitution\nX15 -> T11\nT5 -> .([], T11)\nX16 -> []\nT10 -> T11", fontsize=14, style = filled, fillcolor = lightblue];
14 -> 79 [arrowhead = none ];
79 -> 16;

80 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
14 -> 80 [arrowhead = none ];
80 -> 17;

81 [label="BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification", fontsize=14, style = filled, fillcolor = white];
15 -> 81 [arrowhead = none ];
81 -> 29;

82 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
16 -> 82 [arrowhead = none ];
82 -> 18;

83 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
18 -> 83 [arrowhead = none ];
83 -> 19;

84 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
18 -> 84 [arrowhead = none ];
84 -> 20;

85 [label="EVAL with clause\nflat([], []).\nand substitution\nT11 -> []", fontsize=14, style = filled, fillcolor = lightblue];
19 -> 85 [arrowhead = none ];
85 -> 21;

86 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
19 -> 86 [arrowhead = none ];
86 -> 22;

87 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
20 -> 87 [arrowhead = none ];
87 -> 24;

88 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
20 -> 88 [arrowhead = none ];
88 -> 25;

89 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
21 -> 89 [arrowhead = none ];
89 -> 23;

90 [label="EVAL with clause\nflat(.([], X27), X28) :- flat(X27, X28).\nand substitution\nX27 -> T17\nT11 -> .([], T17)\nX28 -> []\nT16 -> T17", fontsize=14, style = filled, fillcolor = lightblue];
24 -> 90 [arrowhead = none ];
90 -> 26;

91 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
24 -> 91 [arrowhead = none ];
91 -> 27;

92 [label="BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification", fontsize=14, style = filled, fillcolor = white];
25 -> 92 [arrowhead = none ];
92 -> 28;

93 [label="INSTANCE with matching:\nT11 -> T17", fontsize=14, style = filled, fillcolor = lightgrey];
26 -> 93 [arrowhead = none , style=dashed];
93 -> 16[style=dashed];

94 [label="FAILURE", fontsize=14, style = filled, fillcolor = lightgreen];
29 -> 94 [arrowhead = none ];
94 -> 30;

95 [label="BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification", fontsize=14, style = filled, fillcolor = white];
30 -> 95 [arrowhead = none ];
95 -> 31;

96 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
33 -> 96 [arrowhead = none ];
96 -> 35;

97 [label="EVAL with clause\nflat(.(.(X113, X114), X115), .(X113, X116)) :- flat(.(X114, X115), X116).\nand substitution\nX113 -> T90\nX114 -> T94\nX115 -> T95\nT1 -> .(.(T90, T94), T95)\nX116 -> T93\nT2 -> .(T90, T93)\nT91 -> T94\nT92 -> T95", fontsize=14, style = filled, fillcolor = lightblue];
34 -> 97 [arrowhead = none ];
97 -> 52;

98 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
34 -> 98 [arrowhead = none ];
98 -> 53;

99 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
35 -> 99 [arrowhead = none ];
99 -> 36;

100 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
35 -> 100 [arrowhead = none ];
100 -> 37;

101 [label="EVAL with clause\nflat([], []).\nand substitution\nT34 -> []\nT33 -> []", fontsize=14, style = filled, fillcolor = lightblue];
36 -> 101 [arrowhead = none ];
101 -> 38;

102 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
36 -> 102 [arrowhead = none ];
102 -> 39;

103 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
37 -> 103 [arrowhead = none ];
103 -> 41;

104 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
37 -> 104 [arrowhead = none ];
104 -> 42;

105 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
38 -> 105 [arrowhead = none ];
105 -> 40;

106 [label="EVAL with clause\nflat(.([], X61), X62) :- flat(X61, X62).\nand substitution\nX61 -> T45\nT34 -> .([], T45)\nT33 -> T44\nX62 -> T44\nT43 -> T45", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 106 [arrowhead = none ];
106 -> 43;

107 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 107 [arrowhead = none ];
107 -> 44;

108 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
42 -> 108 [arrowhead = none ];
108 -> 45;

109 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
42 -> 109 [arrowhead = none ];
109 -> 46;

110 [label="INSTANCE with matching:\nT1 -> T45\nT2 -> T44", fontsize=14, style = filled, fillcolor = lightgrey];
43 -> 110 [arrowhead = none , style=dashed];
110 -> 1[style=dashed];

111 [label="EVAL with clause\nflat(.(.(X81, X82), X83), .(X81, X84)) :- flat(.(X82, X83), X84).\nand substitution\nX81 -> T62\nX82 -> T66\nX83 -> T67\nT34 -> .(.(T62, T66), T67)\nX84 -> T65\nT33 -> .(T62, T65)\nT63 -> T66\nT64 -> T67", fontsize=14, style = filled, fillcolor = lightblue];
45 -> 111 [arrowhead = none ];
111 -> 47;

112 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
45 -> 112 [arrowhead = none ];
112 -> 48;

113 [label="FAILURE", fontsize=14, style = filled, fillcolor = lightgreen];
46 -> 113 [arrowhead = none ];
113 -> 49;

114 [label="INSTANCE with matching:\nT1 -> .(T66, T67)\nT2 -> T65", fontsize=14, style = filled, fillcolor = lightgrey];
47 -> 114 [arrowhead = none , style=dashed];
114 -> 1[style=dashed];

115 [label="EVAL with clause\nflat(.(.(X99, X100), X101), .(X99, X102)) :- flat(.(X100, X101), X102).\nand substitution\nX99 -> T78\nX100 -> T82\nX101 -> T83\nT1 -> .(.(T78, T82), T83)\nX102 -> T81\nT33 -> .(T78, T81)\nT79 -> T82\nT80 -> T83", fontsize=14, style = filled, fillcolor = lightblue];
49 -> 115 [arrowhead = none ];
115 -> 50;

116 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
49 -> 116 [arrowhead = none ];
116 -> 51;

117 [label="INSTANCE with matching:\nT1 -> .(T82, T83)\nT2 -> T81", fontsize=14, style = filled, fillcolor = lightgrey];
50 -> 117 [arrowhead = none , style=dashed];
117 -> 1[style=dashed];

118 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
52 -> 118 [arrowhead = none ];
118 -> 54;

119 [label="BACKTRACK\nfor clause: flat([], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
54 -> 119 [arrowhead = none ];
119 -> 55;

120 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 120 [arrowhead = none ];
120 -> 56;

121 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 121 [arrowhead = none ];
121 -> 57;

122 [label="EVAL with clause\nflat(.([], X129), X130) :- flat(X129, X130).\nand substitution\nT94 -> []\nT95 -> T106\nX129 -> T106\nT93 -> T105\nX130 -> T105\nT104 -> T106", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 122 [arrowhead = none ];
122 -> 58;

123 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 123 [arrowhead = none ];
123 -> 59;

124 [label="EVAL with clause\nflat(.(.(X141, X142), X143), .(X141, X144)) :- flat(.(X142, X143), X144).\nand substitution\nX141 -> T115\nX142 -> T119\nT94 -> .(T115, T119)\nT95 -> T120\nX143 -> T120\nX144 -> T118\nT93 -> .(T115, T118)\nT116 -> T119\nT117 -> T120", fontsize=14, style = filled, fillcolor = lightblue];
57 -> 124 [arrowhead = none ];
124 -> 60;

125 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
57 -> 125 [arrowhead = none ];
125 -> 61;

126 [label="INSTANCE with matching:\nT1 -> T106\nT2 -> T105", fontsize=14, style = filled, fillcolor = lightgrey];
58 -> 126 [arrowhead = none , style=dashed];
126 -> 1[style=dashed];

127 [label="INSTANCE with matching:\nT1 -> .(T119, T120)\nT2 -> T118", fontsize=14, style = filled, fillcolor = lightgrey];
60 -> 127 [arrowhead = none , style=dashed];
127 -> 1[style=dashed];

}

(2) Obligation:

Triples:

flat16(.([], T17)) :- flat16(T17).
flat1(.([], .([], T11)), []) :- flat16(T11).
flat1(.([], .([], T45)), T44) :- flat1(T45, T44).
flat1(.([], .(.(T62, T66), T67)), .(T62, T65)) :- flat1(.(T66, T67), T65).
flat1(.(.(T78, T82), T83), .(T78, T81)) :- flat1(.(T82, T83), T81).
flat1(.(.(T90, []), T106), .(T90, T105)) :- flat1(T106, T105).
flat1(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) :- flat1(.(T119, T120), T118).

Clauses:

flatc16([]).
flatc16(.([], T17)) :- flatc16(T17).
flatc1([], []).
flatc1(.([], []), []).
flatc1(.([], .([], T11)), []) :- flatc16(T11).
flatc1(.([], []), []).
flatc1(.([], .([], T45)), T44) :- flatc1(T45, T44).
flatc1(.([], .(.(T62, T66), T67)), .(T62, T65)) :- flatc1(.(T66, T67), T65).
flatc1(.(.(T78, T82), T83), .(T78, T81)) :- flatc1(.(T82, T83), T81).
flatc1(.(.(T90, []), T106), .(T90, T105)) :- flatc1(T106, T105).
flatc1(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) :- flatc1(.(T119, T120), T118).

Afs:

flat1(x1, x2) = flat1(x2)

(3) TriplesToPiDPProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
flat1_in: (f,b)
flat16_in: (f)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

FLAT1_IN_AG(.([], .([], T11)), []) → U2_AG(T11, flat16_in_a(T11))
FLAT1_IN_AG(.([], .([], T11)), []) → FLAT16_IN_A(T11)
FLAT16_IN_A(.([], T17)) → U1_A(T17, flat16_in_a(T17))
FLAT16_IN_A(.([], T17)) → FLAT16_IN_A(T17)
FLAT1_IN_AG(.([], .([], T45)), T44) → U3_AG(T45, T44, flat1_in_ag(T45, T44))
FLAT1_IN_AG(.([], .([], T45)), T44) → FLAT1_IN_AG(T45, T44)
FLAT1_IN_AG(.([], .(.(T62, T66), T67)), .(T62, T65)) → U4_AG(T62, T66, T67, T65, flat1_in_ag(.(T66, T67), T65))
FLAT1_IN_AG(.([], .(.(T62, T66), T67)), .(T62, T65)) → FLAT1_IN_AG(.(T66, T67), T65)
FLAT1_IN_AG(.(.(T78, T82), T83), .(T78, T81)) → U5_AG(T78, T82, T83, T81, flat1_in_ag(.(T82, T83), T81))
FLAT1_IN_AG(.(.(T78, T82), T83), .(T78, T81)) → FLAT1_IN_AG(.(T82, T83), T81)
FLAT1_IN_AG(.(.(T90, []), T106), .(T90, T105)) → U6_AG(T90, T106, T105, flat1_in_ag(T106, T105))
FLAT1_IN_AG(.(.(T90, []), T106), .(T90, T105)) → FLAT1_IN_AG(T106, T105)
FLAT1_IN_AG(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) → U7_AG(T90, T115, T119, T120, T118, flat1_in_ag(.(T119, T120), T118))
FLAT1_IN_AG(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) → FLAT1_IN_AG(.(T119, T120), T118)

R is empty.
The argument filtering Pi contains the following mapping:
flat1_in_ag(x1, x2) = flat1_in_ag(x2)
[] = []
flat16_in_a(x1) = flat16_in_a
.(x1, x2) = .(x1, x2)
FLAT1_IN_AG(x1, x2) = FLAT1_IN_AG(x2)
U2_AG(x1, x2) = U2_AG(x2)
FLAT16_IN_A(x1) = FLAT16_IN_A
U1_A(x1, x2) = U1_A(x2)
U3_AG(x1, x2, x3) = U3_AG(x2, x3)
U4_AG(x1, x2, x3, x4, x5) = U4_AG(x1, x4, x5)
U5_AG(x1, x2, x3, x4, x5) = U5_AG(x1, x4, x5)
U6_AG(x1, x2, x3, x4) = U6_AG(x1, x3, x4)
U7_AG(x1, x2, x3, x4, x5, x6) = U7_AG(x1, x2, x5, x6)

We have to consider all (P,R,Pi)-chains

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(4) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

FLAT1_IN_AG(.([], .([], T11)), []) → U2_AG(T11, flat16_in_a(T11))
FLAT1_IN_AG(.([], .([], T11)), []) → FLAT16_IN_A(T11)
FLAT16_IN_A(.([], T17)) → U1_A(T17, flat16_in_a(T17))
FLAT16_IN_A(.([], T17)) → FLAT16_IN_A(T17)
FLAT1_IN_AG(.([], .([], T45)), T44) → U3_AG(T45, T44, flat1_in_ag(T45, T44))
FLAT1_IN_AG(.([], .([], T45)), T44) → FLAT1_IN_AG(T45, T44)
FLAT1_IN_AG(.([], .(.(T62, T66), T67)), .(T62, T65)) → U4_AG(T62, T66, T67, T65, flat1_in_ag(.(T66, T67), T65))
FLAT1_IN_AG(.([], .(.(T62, T66), T67)), .(T62, T65)) → FLAT1_IN_AG(.(T66, T67), T65)
FLAT1_IN_AG(.(.(T78, T82), T83), .(T78, T81)) → U5_AG(T78, T82, T83, T81, flat1_in_ag(.(T82, T83), T81))
FLAT1_IN_AG(.(.(T78, T82), T83), .(T78, T81)) → FLAT1_IN_AG(.(T82, T83), T81)
FLAT1_IN_AG(.(.(T90, []), T106), .(T90, T105)) → U6_AG(T90, T106, T105, flat1_in_ag(T106, T105))
FLAT1_IN_AG(.(.(T90, []), T106), .(T90, T105)) → FLAT1_IN_AG(T106, T105)
FLAT1_IN_AG(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) → U7_AG(T90, T115, T119, T120, T118, flat1_in_ag(.(T119, T120), T118))
FLAT1_IN_AG(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) → FLAT1_IN_AG(.(T119, T120), T118)

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

FLAT16_IN_A(.([], T17)) → FLAT16_IN_A(T17)

R is empty.
The argument filtering Pi contains the following mapping:
[] = []
.(x1, x2) = .(x1, x2)
FLAT16_IN_A(x1) = FLAT16_IN_A

We have to consider all (P,R,Pi)-chains

(8) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(9) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FLAT16_IN_A → FLAT16_IN_A

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(10) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = FLAT16_IN_A evaluates to t =FLAT16_IN_A

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:

Matcher: [ ]
Semiunifier: [ ]

Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from FLAT16_IN_A to FLAT16_IN_A.

(11) NO

(12) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

FLAT1_IN_AG(.([], .(.(T62, T66), T67)), .(T62, T65)) → FLAT1_IN_AG(.(T66, T67), T65)
FLAT1_IN_AG(.([], .([], T45)), T44) → FLAT1_IN_AG(T45, T44)
FLAT1_IN_AG(.(.(T78, T82), T83), .(T78, T81)) → FLAT1_IN_AG(.(T82, T83), T81)
FLAT1_IN_AG(.(.(T90, []), T106), .(T90, T105)) → FLAT1_IN_AG(T106, T105)
FLAT1_IN_AG(.(.(T90, .(T115, T119)), T120), .(T90, .(T115, T118))) → FLAT1_IN_AG(.(T119, T120), T118)

R is empty.
The argument filtering Pi contains the following mapping:
[] = []
.(x1, x2) = .(x1, x2)
FLAT1_IN_AG(x1, x2) = FLAT1_IN_AG(x2)

We have to consider all (P,R,Pi)-chains

(13) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(14) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FLAT1_IN_AG(.(T62, T65)) → FLAT1_IN_AG(T65)
FLAT1_IN_AG(T44) → FLAT1_IN_AG(T44)
FLAT1_IN_AG(.(T90, .(T115, T118))) → FLAT1_IN_AG(T118)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(15) UsableRulesReductionPairsProof (EQUIVALENT transformation)

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.

The following dependency pairs can be deleted:

FLAT1_IN_AG(.(T62, T65)) → FLAT1_IN_AG(T65)
FLAT1_IN_AG(.(T90, .(T115, T118))) → FLAT1_IN_AG(T118)

No rules are removed from R.

Used ordering: POLO with Polynomial interpretation [POLO]:

POL(.(x₁, x₂)) = x₁ + 2·x₂
POL(FLAT1_IN_AG(x₁)) = 2·x₁

(16) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FLAT1_IN_AG(T44) → FLAT1_IN_AG(T44)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(17) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = FLAT1_IN_AG(T44) evaluates to t =FLAT1_IN_AG(T44)

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:

Semiunifier: [ ]
Matcher: [ ]

Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from FLAT1_IN_AG(T44) to FLAT1_IN_AG(T44).

(0) Obligation:

(1) PrologToDTProblemTransformerProof (SOUND transformation)

(2) Obligation:

(3) TriplesToPiDPProof (SOUND transformation)

(4) Obligation:

(5) DependencyGraphProof (EQUIVALENT transformation)

(6) Complex Obligation (AND)

(7) Obligation:

(8) PiDPToQDPProof (SOUND transformation)

(9) Obligation:

(10) NonTerminationProof (EQUIVALENT transformation)

(11) NO

(12) Obligation:

(13) PiDPToQDPProof (SOUND transformation)

(14) Obligation:

(15) UsableRulesReductionPairsProof (EQUIVALENT transformation)

(16) Obligation:

(17) NonTerminationProof (EQUIVALENT transformation)

(18) NO