Horn clause formulation: Difference between revisions
TobiasFritz (talk | contribs) created with essentially no content yet |
TobiasFritz (talk | contribs) begin adding content |
||
| Line 1: | Line 1: | ||
The members of a union-closed family can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. | The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form | ||
<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A}</math> | |||
To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>. | |||
== Canonical systems == | |||
There are at least three canonical systems of Horn clauses that describe a given union-closed family. | |||
=== Maximal one === | |||
Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not contained in any <math>\mathcal{A}</math>-member; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>. | |||
In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. | |||
=== Using minimal transversals === | |||
<ref>{{cite paper|title=The multiple facets of the canonical direct unit implicational basis|url=http://www.sciencedirect.com/science/article/pii/S0304397510000034}}</ref> | |||
== Literature == | |||
For intersection-closed families, there are plenty of papers in certain areas of artificial intelligence research, including data analysis and formal concept analysis. | |||
Revision as of 03:37, 9 March 2016
The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form
[math]\displaystyle{ x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A} }[/math]
To keep the notation concise, we use the shorthand notation [math]\displaystyle{ (x,S) }[/math] for such a Horn clause. The following page provides various details of this formulation. Throughout, [math]\displaystyle{ \mathcal{A}\subseteq 2^X }[/math] is union-closed with [math]\displaystyle{ \emptyset\in\mathcal{A} }[/math].
Canonical systems
There are at least three canonical systems of Horn clauses that describe a given union-closed family.
Maximal one
Considering all [math]\displaystyle{ (x,S) }[/math] that are satisfied by [math]\displaystyle{ \mathcal{A} }[/math] characterizes [math]\displaystyle{ \mathcal{A} }[/math]. To see this, we need to show that every set not in [math]\displaystyle{ \mathcal{A} }[/math] violates some [math]\displaystyle{ (x,S) }[/math]. Indeed for [math]\displaystyle{ A\not\in\mathcal{A} }[/math], take some [math]\displaystyle{ x\in A }[/math] that is not contained in any [math]\displaystyle{ \mathcal{A} }[/math]-member; this is possible due to the union-closure assumption. Then put [math]\displaystyle{ S:=X\setminus A }[/math].
In most cases, there are smaller systems of Horn clauses that still characterize [math]\displaystyle{ \mathcal{A} }[/math].
Using minimal transversals
<ref>Template:Cite paper</ref>
Literature
For intersection-closed families, there are plenty of papers in certain areas of artificial intelligence research, including data analysis and formal concept analysis.
