scientific article; zbMATH DE number 3936509

From MaRDI portal
Publication:3707401





[For the entire collection see Zbl 0551.00013.] [English version in Lect. Notes Comput. Sci. 122, 430-440 (1981; Zbl 0477.68035).] Algebraic transformations of simple iterative algorithms are quoted. Two interesting examples are given. The first one concerns the computation of strongly connected components of a graph. The method shows how to obtain from a straightforward \(mn^ 2\)-algorithm an efficient max(m,n)- algorithm. Another example shows how to obtain an efficient algorithm for the computation of the minimal relation Q satisfying: \[ P(x_ 1,...,x_ n)\quad \Rightarrow \quad Q(x_ 1,...,x_ n) \] \[ Q(x_ 1,...,x_ n)\quad and\quad R(z_ 1,...,z_ m)\quad \Rightarrow \quad Q(y_ 1,...,y_ n). \] The algebraic method was also used in practice, e.g. the author quotes an example of a PL/1 program of over 2000 statements optimized to a 10 times speed-up.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3707401)