LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 328-330 of 486

    • Ω(n log n) Lower Bounds on Length of Boolean Formulas 

      Fischer, Michael J.; Meyer, Albert R.; Paterson, Michael S. (1980-11)
      A property of Boolean functions of n variables is described and shown to imply lower bounds as large as Ω(n log n) on the number of literals in any Boolean formula for any function with the property. Formulas over the full ...

    • BRAND X Manual 

      Szolovits, Peter; Martin, William A. (1980-11)
      BRAND X is a simple representation language implemented as a pure extension of LISP. BRAND X provides the following additional facilities over LISP: Unique and canonical structures, property lists for all objects, labels ...

    • An Optimality Theory of Concurrency Control for Databases 

      Kung, Hsing-Tsung; Papadimitrou, Christos H. (1980-11)
      A concurrency control mechanism (or a scheduler) is the component of a database system that safeguards the consistency of the database in the presence of interleaved accesses and update requests. We formally show that the ...