| Title:
|
Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers (English) |
| Author:
|
Čulík, Karel |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
16 |
| Issue:
|
3 |
| Year:
|
1971 |
| Pages:
|
188-202 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. () |
| MSC:
|
68A20 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0231.68022 |
| idMR:
|
MR0309358 |
| DOI:
|
10.21136/AM.1971.103345 |
| . |
| Date available:
|
2008-05-20T17:50:35Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103345 |
| . |
| Reference:
|
[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 0421123 |
| Reference:
|
[2] K. Čulík V. Doležal M. Fiedler: Combinatorial analysis in praxis.(Czech), SNTL, Prague 1967. |
| Reference:
|
[3] K. Čulík: On some transformations in context-free grammars and languages.Czech. Math. Jour. 17 (1967), Academia, 278-311. MR 0214410 |
| Reference:
|
[4] K. Čulík: Zur Theorie der Graphen.Čas. pro pěst. mat. 83 (1958), 133-155. MR 0097805 |
| Reference:
|
[5] G. Birkhoff: Lattice theory.New York 1948. Zbl 0033.10103, MR 0029876 |
| Reference:
|
[6] C. Berge: Théorie des graphes et ses applications.Dunod, Paris 1958. MR 0102822 |
| Reference:
|
[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. MR 0275722, 10.1145/321607.321620 |
| Reference:
|
[8] A. Blikle: Addressless units for carrying out loop-free computations.Polish Academy of Sciences, Institute of Mathematics, July 1970, Warsaw. |
| . |
