Unbounded program memory adds to the expressive power of first-order dynamic logic

1 October 1981

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

https://doi.org/10.1109/sfcs.1981.54

Abstract

The aim of this paper is to-compare various logics of programs with respect to their expressibility. The main result of the paper states that no logic of bounded memory programs is capable of defining the algebra of standard binary trees T = (T, CONS, NIL). Since the usual logics of unbounded memory programs are able to define the above algebra - we derive from the main result a couple of results which solve some questions about comparing expressive powers of programming logics.

Keywords

BINARY TREES
PROGRAMMABLE LOGIC ARRAYS
ALGEBRA
BOOKS
SOCIOTECHNICAL SYSTEMS
LABORATORIES
COMPUTER SCIENCE

This publication has 2 references indexed in Scilit:

Definability in Dynamic Logic
Published by Association for Computing Machinery (ACM) ,1980
First-Order Dynamic Logic
Lecture Notes in Computer Science, 1979