On an Application of Algorithmic Theory of Stacks

Article type: Research Article

Authors: Szałas, Andrzej

Affiliations: Institute of Mathematics, Polish Academy of Sciences

Abstract: The fact that for every formula describing properties of programs with recursive functions there exists an equivalent while-formula with stacks is proved in a constructive way. This implies the possibility of using the algorithmic theory of stacks to prove the properties of ALGOL-like programs. The normal forms for such programs are also defined.

Keywords: algorithmic logic, algorithmic theory, block-structured program, interpretation of theories, normal forms for programs, recursive functions, relational system, translation

DOI: 10.3233/FI-1984-7313

Journal: Fundamenta Informaticae, vol. 7, no. 3, pp. 377-388, 1984