| Title:
|
A note on complexity of algorithmic nets without cycles (English) |
| Author:
|
Čulík, Karel |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
16 |
| Issue:
|
4 |
| Year:
|
1971 |
| Pages:
|
297-301 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
The scope width of an algorithmic net without cycles $N$ is the integer $scwi^*(N)=min_{P\in P(N)} scwi^*(P)$, where $scwi^*(P)$ is a modified scope width of the course $P$ of the net $N$ and $P(N)$ is the set of all courses of $N$. If $T$ is an algorithmic rooted tree (i.e. a net with one output vertex and without parallel paths) with the root $v$ and if $v_1,v_2,\ldots,v_n$ are all the vertices where start all edges which terminate in $v$, then we conjecture that $scwi^*(T)=max_{1\leq q\leq p}.[scwi^*(T_{s_q})+s_q-1]$ where $p$ is the number of different scope width $scwi^*(T_i)$ and the integers $s_1,s_2,\ldots,s_q=n$ are determined by the following inequalities $scwi^*(T_1)=\ldots = scwi^*(T_{s_1})>scwi^*(T_{s_1+1})=\ldots = scwi^*(T_{s_2}>\ldots >scwi^*(T_{{s_{p-1}+1}})=\ldots =scwi^*(T_{s_p})$. () |
| MSC:
|
68A20 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0234.68019 |
| idMR:
|
MR0309359 |
| DOI:
|
10.21136/AM.1971.103359 |
| . |
| Date available:
|
2008-05-20T17:51:16Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103359 |
| . |
| Reference:
|
[1] Blikle A.: Addressless units for carrying out loop-free computations.pp. 48, Polish Academy of Sciences, Institute of Mathematics, July 1970. |
| Reference:
|
[2] Čulík K.: Combinatorial problems in theory of complexity of algorithmic nets without cycles for simple computers.Aplikace matematiky 16 (1971), 188 - 202. MR 0309358 |
| Reference:
|
[3] Čulík K.: On semantics of programming languages.Automatentheorie und formale Sprachen ed. J. Dörr, G. Hotz, Bibliographisches Institut, Mannheim- Wien- Zurich, 1970, pp. 291-303. MR 0421123 |
| Reference:
|
[4] Čulík K.: Structural similarity of programs and some concepts of algorithmic metod.preprint of a lecture presented at the GI - Conference in Munich, March 1971. |
| Reference:
|
[5] Sethi R., Ullman J. D.: The generation of optimal code for arithmetic expressions.Jour. of ACM, vol. 17, No. 4, October 1970, pp. 715-728. Zbl 0212.18802, MR 0275722, 10.1145/321607.321620 |
| Reference:
|
[6] Čulík K.: Theory of programming languages and of algorithms.a textbook for Institute of Technology in Prague (in print), July 1970. |
| . |
