Browsing MAC Memos (1963 - 1974) by Author "Fischer, Michael J."

Now showing items 1-5 of 5

    • The Complexity of Negotion-limited Networks: A Brief Survery 

      Fischer, Michael J. (1975-06)

    • Fast On-line Integer Multiplication 

      Fischer, Michael J.; Stockmeyer, Larry J. (1974-05)
      A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general ...

    • An Improved Overlap Argument for On-line Multiplication 

      Paterson, Michael S.; Fischer, Michael J.; Meyer, Albert R. (1974-01)
      A lower bound of cN1ogN is proved for the mean time complexity of an on-line multitape Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines the corresponding bound ...

    • String-matching and Other Products 

      Fischer, Michael J.; Paterson, Michael S. (1974-01)
      The string-matching problem considered here is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is an algorithm due to Morris, ...

    • Super-exponential Complexity of Presburger Arithmetic 

      Fischer, Michael J.; Rabin, Michael O. (1974-02)
      Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first order theory of the real numbers under ...