Geodesic
A note on complexity of algorithmic nets without cycles
Applications of Mathematics, Tome 16 (1971) no. 4, pp. 297-301
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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})$.
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})$.
DOI : 10.21136/AM.1971.103359
Classification : 68A20, 68Q25, 68R10 
@article{10_21136_AM_1971_103359,
     author = {\v{C}ul{\'\i}k, Karel},
     title = {A note on complexity of algorithmic nets without cycles},
     journal = {Applications of Mathematics},
     pages = {297--301},
     year = {1971},
     volume = {16},
     number = {4},
     doi = {10.21136/AM.1971.103359},
     mrnumber = {0309359},
     zbl = {0234.68019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103359/}
}
TY  - JOUR
AU  - Čulík, Karel
TI  - A note on complexity of algorithmic nets without cycles
JO  - Applications of Mathematics
PY  - 1971
SP  - 297
EP  - 301
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103359/
DO  - 10.21136/AM.1971.103359
LA  - en
ID  - 10_21136_AM_1971_103359
ER  - 
%0 Journal Article
%A Čulík, Karel
%T A note on complexity of algorithmic nets without cycles
%J Applications of Mathematics
%D 1971
%P 297-301
%V 16
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.1971.103359/
%R 10.21136/AM.1971.103359
%G en
%F 10_21136_AM_1971_103359
Čulík, Karel. A note on complexity of algorithmic nets without cycles. Applications of Mathematics, Tome 16 (1971) no. 4, pp. 297-301. doi: 10.21136/AM.1971.103359

[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

[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

[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 | MR | Zbl

[6] Čulík K.: Theory of programming languages and of algorithms. a textbook for Institute of Technology in Prague (in print), July 1970.

Cité par Sources :