Technical Report CS0329

Title: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples
Authors: J.A. Makowsky
Abstract: We introduce the notion of generic examples as a unifying principle for various phenomena in computer science, such as initial stuctures in the area of abstract data types. Armstrong relations in the area ot data bases. Generic examples are also useful in defining the semantics of logic programming, in the formal theory of program testing and in complexity theory. We characterize initial structures in terms of their genericity properties and give a syntactic characterization of first order theories admitting initial structures. The latter can be ued to explain why Horn formuias have gained such a predominant role in various areas of computer science.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion