A note on complexity of algorithmic nets without cycles

Čulík, Karel

Applications of Mathematics, Tome 16 (1971) no. 4, pp. 297-301.

Résumé

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})$.

Détail

DOI : 10.21136/AM.1971.103359

Classification : 68A20, 68Q25, 68R10