Algorithmic Logic with Stacks and Its Model-Theoretical Properties

Article type: Research Article

Authors: Dańko, Wiktor

Affiliations: University of Warsaw, Białystok Division

Abstract: In this paper we propose to transform the Algorithmic Theory of Stacks (cf. Salwicki [30]) into a logic for expressing and proving properties of programs with stacks. We compare this logic to the Weak Second Order Logic (cf. [11, 15]) and prove theorems concerning axiomatizability without quantifiers (an analogon of Łoś-Tarski theorem) and χ0 - categoricity (an analogon of Ryll-Nardzewski’s theorem).

Keywords: logics of programs, infinitary logics, categoricity in power, data structures

DOI: 10.3233/FI-1984-7402

Journal: Fundamenta Informaticae, vol. 7, no. 4, pp. 391-428, 1984