Complexity of NFA

Hello,

I'm not very familiar with the theory of computation. When I read a
paper recently,
I can't understand why the following proposition is true.

"... Consider an NFA N, and a string a1 ... an ∈L(N). There is a
sequence of
renamings u(ai1, b1), ... , u(aim, bm), where i1 < i2 < ... < im.
The renaming u(aij, bj) requires that the aij be renamed to bj. We
would like
to efficiently check whether the updated string
a1 ... ai1-1 b1 ai1+1 ... aim-1 bm aim+1 ... an ∈L(N)

Validating the new string from scratch by running it through N takes O(
n * |Q|^2 * log|Q| ) ..."

I don't know how the complexity O( n * |Q|^2 * log|Q| ) for the
algorithm that recognizes the
language accepted by NFA is derived. Is this a well-known conclusion in
the automaton theory, or
a result that must be calculated in some way?

Would anyone kindly help me please?

Thanks in advance.

.

Relevant Pages

  • Merry Christmas!
    ... dictionaries and every variant possibility has a separate "word" entry. ... The byte string of the "word", whose length is specified by a four ... match is found for a source byte sequence in the dictionary. ...
    (rec.arts.sf.written)
  • Merry Christmas! Linux RULES! New applications to develop!
    ... dictionaries and every variant possibility has a separate "word" ... Each entry in the dictionary contains: ... The byte string of the "word", whose length is specified by a four ... addresses whose entry is selected by the first byte of the sequence. ...
    (comp.os.linux.misc)
  • Re: CSI Challenge
    ... Every computable string is compressible under Algorithmic Information ... and 1s have as their shortest description just the sequence itself. ... Machine depends on the selection of the Universal Turing Machine. ... Machine (or the algorithm) is what determines which set of strings is ...
    (talk.origins)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... the sequence appears to be part of a "normal" number or not. ... This compression algorithm can then be used to predict ... If this prediction succeeds, it gains predictive ... predictive value as the string in question increases in size with each ...
    (talk.origins)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... The digits of pi are not a sequence in the sense that knowing the ... without the proper reference algorithm. ... What is your prediction as to what will come next? ... pattern and use it to inductively predict the future of the string. ...
    (talk.origins)