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