Abstract
An algebraic approach to programs called recursive coroutines — due to Janicki [3] — is based on the idea to consider certain complex algorithms as algebraics models of those programs. Complex algorithms are generalizations of pushdown algorithms being algebraic models of recursive procedures (see Mazurkiewicz [4]). LCA — logic of complex algorithms — was formulated in [11]. It formalizes algorithmic properties of a class of deterministic programs called here complex recursive ones or interacting stacks-programs, for which complex algorithms constitute mathematical models. LCA is in a sense an extension of algorithmic logic as initiated by Salwicki [14] and of extended algorithmic logic EAL as formulated and examined by the present author in [8], [9], [10]. In LCA — similarly as in EAL-ω + -valued logic is applied as a tool to construct control systems (stacks) occurring in corresponding algorithms.
The aim of this paper is to give a complete axiomatization. of LCA and to prove a completeness theorem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. E. Coway,Design of a separable-transition diagram compiler, Comm. ACM 6 July 1963, 396–408.
D. Harel,First-order dynamic logic, Lecture Notes in Computer Science 68, 1979.
R. Janicki,An algebraic approach to the theory of recursive coroutines,Fundamenta Informaticae 1 (1977), pp. 131–145.
A. Mazurkiewicz,Recursive algorithms and formal languages,Bull. Ac. Pol. Sci., Ser. Sci. Math. Astronom. Phys. 20 (1972), pp. 799–809.
G. Mirkowska,Algorithmic logic with nondeterministic programs, ICS PAS Reports 343, 1979, 17.
V. R. Pratt,Semantical considerations in Floyd-Hoare logic. Proc. 17th IEEE Symp. on FCS, 1976.
H. Rasiowa,On generalized Post algebras of order ω + and ω + -valued predicate calculi,Bull. Ac. Pol. Sci., Ser. Sci.Math. Astron. Phys. 21 (1973), pp. 209–219.
H. Rasiowa,ω +-valued algorithmic logic as a tool to investigate procedures Proc. MFCS'74, Lecture Notes in Computer Science 28, 1974, Springer.
H. Rasiowa,Completeness theorem for extended algorithmic logic, Proc. Vth Int. Congress of Logic, Methodology and Philosophy of Science, 1975, III, 13–15
H. Rasiowa,Algorithmic logic. Multiple-valued extensions.Studia Logica 38 (1979), pp. 317–335.
H. Rasiowa,Logic of complex algorithms, Proc. FCT'79, Berlin ed. by L. Budach, Mathematische Forschung 2, 1979, Akademie Verlag, pp. 370–381.
H. Rasiowa,Completeness in classical logic of complex algorithms, Proc. MFCS'80, Lecture Notes in Computer Science, 88 (1980), pp. 488–503, Springer.
H. Rasiowa andR. Sikorski,The Mathematics of Metamathematics, Warsaw, 3rd ed. 1970.
A. Salwicki,Formalized algorithmic languages,Bull. Ac. Pol. Sci., Ser. Math Astron. Phys. 18 (1970), pp. 227–232.
J. Tiuryn,Logic of effective definitions, RWTH Aachen Schriften zur Informatik und Angewandten Mathematik, 55, Juli 1979; Fundamenta Informaticae, to appear.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rasiowa, H. On logic of complex algorithms. Stud Logica 40, 289–310 (1981). https://doi.org/10.1007/BF02584062
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02584062