This work presents a purely classical first-order logical approach to the field of study in theoretical computer science sometimes referred to as the theory of programs, or programming theory. This field essentially attempts to provide a precise mathematical basis for the common activities involved in reasoning about computer programs and programming languages, and it also attempts to find practical applications in the areas of program specification, verification and programming language design. Many different approaches with different mathematical frameworks have been proposed as a basis for programming theory. They differ in the mathe matical machinery they use to define and investigate programs and program properties and they also differ in the concepts they deal with to understand the programming paradigm. Different approaches use different tools and viewpoints to characterize the data environment of programs. Most of the approaches are related to mathe matical logic and they provide their own logic. These logics, however, are very eclectic since they use special entities to reflect a special world of programs, and also, they are usually incomparable with each other. This Babel's mess irritated us and we decided to peel off the eclectic com ponents and try to answer all the questions by using classical first-order logic.
Author(s): Tamás Gergely, László Úry
Series: EATCS Monographs on Theoretical Computer Science 24
Publisher: Springer
Year: 1991
Language: English
Pages: 341
Tags: Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Mathematical Logic and Foundations
Front Matter....Pages I-IX
Introduction....Pages 1-12
Front Matter....Pages 13-13
Logic and Model Theory....Pages 15-35
Inductive Definability....Pages 37-45
Front Matter....Pages 47-47
Introduction to Part I....Pages 49-52
Main Properties of Program Schemas....Pages 53-76
Extension of Program Schemas....Pages 77-89
Program Schemas with Stacks....Pages 91-102
Computability....Pages 103-117
On Inductive Definability of 1- and 2- Computable Relations....Pages 119-131
Front Matter....Pages 133-133
Introduction to Part II....Pages 135-138
Description of Program Properties....Pages 139-142
Den-based Descriptive Languages....Pages 143-153
The Problem of Completeness....Pages 155-170
Dynamic Logic Generated by Extension....Pages 171-178
Continuous Denotational Semantics....Pages 179-210
Definable Denotational Semantics....Pages 211-225
Front Matter....Pages 227-227
Introduction to Part III....Pages 229-232
Temporal Logic....Pages 233-238
Temporal Logical Description of Program Properties....Pages 239-242
Is Temporal Logic Expressible in Dynamic Logic?....Pages 243-245
Front Matter....Pages 227-227
Is Dynamic Logic Expressible in Temporal Logic?....Pages 247-261
The Case of Enumerable Models....Pages 263-266
Temporal Axiomatization of Program Verification Methods....Pages 267-282
Front Matter....Pages 283-283
Introduction to Part IV....Pages 285-287
Time Logic....Pages 289-295
Definability in Regular Time Theories....Pages 297-308
Expressive Power of Time Logic....Pages 309-323
Back Matter....Pages 325-353
