• DocumentCode
    2203708
  • Title

    "Natural" properties of flowchart complexity measures

  • Author

    Baker, Theodore P.

  • fYear
    1974
  • fDate
    14-16 Oct. 1974
  • Firstpage
    178
  • Lastpage
    184
  • Abstract
    A system of flowchart program schemata is viewed as a schema for a class of natural computational complexity measures. Certain properties of this class of measures, such as recursive enumerability of complexity classes and a weak notion of "conformity", are shown to derive from the schematic structure. Other properties, earlier proposed as "natural", are shown to be more superficial, depending upon the interpretation given to the primitive operations. These are "properness", "finite invariance", and "density". Two other natural properties of the flowchart measures are given, together with a short assessment of-possible progress in defining "naturalness" in complexity measures.
  • Keywords
    Computational complexity; Computational modeling; Concurrent computing; Flowcharts; Mathematics; Particle measurements; Registers; Testing; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
  • Conference_Location
    USA
  • ISSN
    0272-4847
  • Type

    conf

  • DOI
    10.1109/SWAT.1974.1
  • Filename
    4569774