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
Link To Document :
بازگشت