Translatability of flowcharts into while programs

摘要

A “while program” [Z. Manna, “Introduction to Mathematical Theory of Computations,” to appear] is a simple abstract model of a “GOTO-less program.” Some flowcharts, however, can not be translated into while programs in a certain sense [D. E. Knuth and R. W. Floyd, Notes on avoiding GOTO statements, Information Processing Letters 1 (1971), 23–31]. That is, there exists a flowchart which is not “congruent” (or computation-sequence-equivalent) to any while program. In this paper we give a necessary and sufficient condition for translatability of flowcharts into while programs.