Article
Full entry |
PDF
(0.8 MB)
Feedback
PDF
(0.8 MB)
Feedback
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})$.
References:
[1] Blikle A.: Addressless units for carrying out loop-free computations. pp. 48, Polish Academy of Sciences, Institute of Mathematics, July 1970.
[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
[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
[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.
[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. DOI 10.1145/321607.321620 | MR 0275722 | Zbl 0212.18802
[6] Čulík K.: Theory of programming languages and of algorithms. a textbook for Institute of Technology in Prague (in print), July 1970.
Search
Partner of
