Previous |  Up |  Next


The program is defined syntactically as an ordered finite set of labelled commands which are certain strings over a finite alphabet. The labelled branch of a program is a finite sequence of labelled commands of the program, which represents a possible order of commands in a completed computation. Several syntactical requirements, motivated by the computation process, are added in the strong definition of the program. The flow diagram of a program is introduced as an oriented graph with labelled vertices and edges. An algorithm of synthesis of a program from a flow-diagram is presented. Non-labelled and operational branches are introduced for programs and also for flow diagrams. The necessary and sufficient conditions are presented for two programs to have the same set of labelled and non-labelled branches, which always is a regular event. A survey on all possible flow diagrams is given algebraically by a graph factorization, where the factor $r$-graph is connected and acyclic with a single input vertex while the corresponding subgraphs are strongly connected.
[1] Čulík K.: Classifications of programming theories and languages. Information Processing Machines 17 (in print) .
[2] Čulík K.: Some notes on finite state languages and events represented by finite automata using labelled graphs. Čas. pro pěst. mat. 86 (1961), 43 - 55. MR 0130062
[3] Čulík K.: Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers. Aplikace mat. 16 (1971), 188 - 202. MR 0309358
[4] Čulík K.: Algorithmization of algebras and relational structures. Commentationes Mathematicae Universitatis Carolinae 13, 3 (1972), 457-477. MR 0317574
[5] Engeler E.: Algorithmic Approximations. Journal of Computer and System Sciences 5 (1971), 67-82. DOI 10.1016/S0022-0000(71)80008-9 | MR 0293874 | Zbl 0238.68016
Partner of
EuDML logo