Time Complexity of TSL

We will describe a procedure which, given a TS and an input string of length n, will accept the string if and only if it is in the 

The main part of the algorithm consists of filling in the entries of the recognition matrix M of w this is described by the block diagram in Fig. 5.1  

1) The entries of H are filled in by columns from right to left, the last column is filled in first. 

However, if less than r passes have been made and no other entry can be filled in, all entries (i,j) such that m(i,j) e are set to 2 (we have in this case loop failures). When finally M is filled in, the value of m(l,l) is checked. If m(l,l) - (o,n) the string is accepted. 

Let the Input string be w aaaaaa. By applying the Algorithm 5.1 we get from Mon w  

---

Some of the results for the TS can be extended to gTS. One example is the result concerning the time complexity of TSL. The Algorithm 5.1 can be, with little change, applied to any given gTS and so we have the following theorem ... 

---