Why Horn formulas matter in computer science: initial structures and generic examples

DOI10.1016/0022-0000(87)90027-4zbMath0619.68029OpenAlexW2041182895MaRDI QIDQ1089797

Johann A. Makowsky

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90027-4

zbMATH Keywords

abstract data typesHorn formulasArmstrong relations

Mathematics Subject Classification ID

Data structures (68P05) General topics in the theory of software (68N01)

Related Items (14)

Algebraic Characterizations for Universal Fragments of Logic ⋮ Specifications in an arbitrary institution ⋮ On the existence of free models in fuzzy universal Horn classes ⋮ A Conceptual Framework for Secrecy-preserving Reasoning in Knowledge Bases ⋮ Logics of Finite Hankel Rank ⋮ Information-based distance measures and the canonical reflection of view updates ⋮ Exploiting data dependencies in many-valued logics ⋮ Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ The meaning of specifications I: Domains and initial models ⋮ Syntactic characterization of closure under connected limits ⋮ Data exchange: semantics and query answering ⋮ Data types over multiple-valued logics ⋮ Double Horn functions ⋮ Unique complements and decompositions of database schemata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• Arithmetic analogues of McAloon's unique Rosser sentences
• Model theory
• On the expressive power of data dependencies
• Introduction to model theory and to the metamathematics of algebra
• A formal notion of program-based test data adequacy
• An Evaluation Based Theorem Prover
• Unit Refutations and Horn Sets
• Horn clause computability
• Polynomials with Rational Coefficients Which are Hard to Compute
• The decision problem for some classes of sentences without quantifiers

This page was built for publication: Why Horn formulas matter in computer science: initial structures and generic examples