Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract)
We introduce the notion of generic examples as a unifying principle for various phenomena in computer science such as initial structures in the area of abstract data types and Armstrong relations in the area of data bases. Generic examples are also useful in defining the semantics of logig programming, in the formal theory of program testing and in complexity theory. We characterize initial structures in terms of their generic properties and give a syntactic characterization of first order theories admitting initial structures. The latter can be used to explain why Horn formulas have gained a predominant role in various areas of computer science.