Geodesic
Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
Applications of Mathematics, Tome 16 (1971) no. 3, pp. 188-202
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Algorithmic nets (or flow diagrams) are a generalization of logical nets. They are finite, oriented and acyclic graphs or multigraphs with labelled vertices and edges. Certain total orderings of their vertices are called courses (or programs). The following measures of complexity of a course (together with certain chromatic decomposition of certain interval graph) are introduced: its length is the number of its vertices; its width is the maximal degree of a complete subgraph in the interval graph; its capacity of storage is the number of elements of the decomposition and the non-efficiencies of its scopes or of its addresses.
Algorithmic nets (or flow diagrams) are a generalization of logical nets. They are finite, oriented and acyclic graphs or multigraphs with labelled vertices and edges. Certain total orderings of their vertices are called courses (or programs). The following measures of complexity of a course (together with certain chromatic decomposition of certain interval graph) are introduced: its length is the number of its vertices; its width is the maximal degree of a complete subgraph in the interval graph; its capacity of storage is the number of elements of the decomposition and the non-efficiencies of its scopes or of its addresses.
DOI : 10.21136/AM.1971.103345
Classification : 68A20, 68Q25, 68R10 
@article{10_21136_AM_1971_103345,
     author = {\v{C}ul{\'\i}k, Karel},
     title = {Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers},
     journal = {Applications of Mathematics},
     pages = {188--202},
     year = {1971},
     volume = {16},
     number = {3},
     doi = {10.21136/AM.1971.103345},
     mrnumber = {0309358},
     zbl = {0231.68022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103345/}
}
TY  - JOUR
AU  - Čulík, Karel
TI  - Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
JO  - Applications of Mathematics
PY  - 1971
SP  - 188
EP  - 202
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103345/
DO  - 10.21136/AM.1971.103345
LA  - en
ID  - 10_21136_AM_1971_103345
ER  - 
%0 Journal Article
%A Čulík, Karel
%T Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
%J Applications of Mathematics
%D 1971
%P 188-202
%V 16
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103345/
%R 10.21136/AM.1971.103345
%G en
%F 10_21136_AM_1971_103345
Čulík, Karel. Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers. Applications of Mathematics, Tome 16 (1971) no. 3, pp. 188-202. doi: 10.21136/AM.1971.103345

[1] K. Čulík: On semanitics of programming languages. J. Dörr, G. Hotz: Automatentheorie und formale Sprachen, Bibliographisches Institut AG, Mannheim 1970, 291-302. | MR

[2] K. Čulík V. Doležal M. Fiedler: Combinatorial analysis in praxis. (Czech), SNTL, Prague 1967.

[3] K. Čulík: On some transformations in context-free grammars and languages. Czech. Math. Jour. 17 (1967), Academia, 278-311. | MR

[4] K. Čulík: Zur Theorie der Graphen. Čas. pro pěst. mat. 83 (1958), 133-155. | MR

[5] G. Birkhoff: Lattice theory. New York 1948. | MR | Zbl

[6] C. Berge: Théorie des graphes et ses applications. Dunod, Paris 1958. | MR

[7] R. Sethi J. D. Ullman: The Generation of Optimal Code for Arithmetic Expressions. Journal of ACM, Vol. 17, No. 4, October 1970, pp. 715-728. | DOI | MR

[8] A. Blikle: Addressless units for carrying out loop-free computations. Polish Academy of Sciences, Institute of Mathematics, July 1970, Warsaw.

Cité par Sources :