On functional dependencies in \(q\)-Horn theories

DOI10.1016/S0004-3702(01)00118-7zbMath0996.68197OpenAlexW2078663304MaRDI QIDQ1606330

Alexander Kogan, Toshihide Ibaraki, Kazuhisa Makino

Publication date: 24 July 2002

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(01)00118-7

zbMATH Keywords

\(q\)-Horn theory

Mathematics Subject Classification ID

Database theory (68P15) Knowledge representation (68T30)

Related Items (3)

Logic of temporal attribute implications ⋮ On propositional definability ⋮ A subclass of Horn CNFs optimally compressible in polynomial time

Uses Software

• Ltur
• Leibniz

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generalized Horn formulas and \(k\)-resolution
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Polynomially solvable satisfiability problems
• Horn functions and their DNFs
• Structure identification in relational data
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Horn minimization by iterative decomposition
• Functional dependencies in Horn theories
• Reasoning with examples: Propositional formulae and database dependencies
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Recognition of \(q\)-Horn formulae in linear time
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Polynomial-time inference of all valid implications for Horn and related formulae
• On renamable Horn and generalized Horn functions
• Hierarchies of polynomially solvable satisfiability problems
• Inferring minimal functional dependencies in Horn and q-Horn theories
• Investigations on autark assignments
• A short note on some tractable cases of the satisfiability problem.
• Horn approximations of empirical data
• Equational characterizations of Boolean function classes
• Reasoning with models
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Renaming a Set of Clauses as a Horn Set
• Functional Dependencies in a Relational Database and Propositional Logic
• A Complexity Index for Satisfiability Problems
• Algorithms for inferring functional dependencies from relations
• Knowledge compilation and theory approximation
• On sentences which are true of direct unions of algebras
• The decision problem for some classes of sentences without quantifiers

This page was built for publication: On functional dependencies in \(q\)-Horn theories