zbMATH — the first resource for mathematics

Logic LNCA of non-deterministic complex algorithms. (English) Zbl 0566.68038
In this paper a classical logic of non-deterministic complex algorithms is formulated. It formalizes algorithmic properties of a class of non- deterministic regular programs with syntactic interacting stacks (i.e. stacks and queues), including those for which complex algorithms (in the sense as introduced by R. Janicki [Fundam. Inf. 1, 131-145 (1977; Zbl 0362.68056)]) are mathematical models. In particular, LNCA is a generalization of G. Mirkowska’s algorithmic logic with non- deterministic programs [ibid. 3, 45-64, 157-170 (1980; Zbl 0439.68024 and Zbl 0439.68025)], regular DL and CLCA. The approach given in this paper is similar to that presented in a forthcoming book by the present author and J. Tiuryn [”Logics of programs”, in preparation for Polish Scientific Publishers and North Holland] and applies a formalization of theories of stacks and of interacting stacks as presented by the author at the AMS Meeting, Special Session Proof Theory, Denver, Colorado (1983).
68Q65 Abstract data types; algebraic specification
PDF BibTeX Cite