• DocumentCode
    2645551
  • Title

    Verifying identities

  • Author

    Rajagopalan, Sridhar ; Schulman, Leonard J.

  • Author_Institution
    Princeton Univ., NJ, USA
  • fYear
    1996
  • fDate
    14-16 Oct 1996
  • Firstpage
    612
  • Lastpage
    616
  • Abstract
    The authors provide an O˜(n2) time randomized algorithm to check whether a given operation f:S×S→S is associative (letting n=|S|). They prove this performance is optimal (up to polylogarithmic factors) even in case the operation is “cancellative”. No sub-n3 algorithm was previously known for this task. More generally they give an O(nc ) time randomized algorithm to check whether a collection of c-ary operations satisfy any given “read-once” identity
  • Keywords
    associative processing; computational complexity; formal verification; randomised algorithms; associative operation; c-ary operations; identity verification; optimal performance; read-once identity; time randomized algorithm; Automata; Error probability; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
  • Conference_Location
    Burlington, VT
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-7594-2
  • Type

    conf

  • DOI
    10.1109/SFCS.1996.548520
  • Filename
    548520
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2645551