Horn clause formulation - Revision history

TobiasFritz at 09:50, 11 March 2016

2016-03-11T09:50:50Z

← Older revision		Revision as of 02:50, 11 March 2016
Line 28:		Line 28:

	For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].		For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

			[[Category:Frankl's union-closed sets conjecture]]

TobiasFritz: correction

2016-03-11T09:44:06Z

correction

← Older revision		Revision as of 02:44, 11 March 2016
Line 1:		Line 1:
	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		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>		<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in 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>.		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>.

TobiasFritz at 14:49, 10 March 2016

2016-03-10T14:49:02Z

← Older revision		Revision as of 07:49, 10 March 2016
Line 23:		Line 23:
	=== Using free sets ===		=== Using free sets ===

	A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (~~This~~ terminology ~~seems motivated by~~ the dual ~~notion for~~ intersection-closed families, ~~applied~~ to the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.		A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

	== Literature ==		== Literature ==

	For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].		For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

TobiasFritz at 14:46, 10 March 2016

2016-03-10T14:46:50Z

← Older revision		Revision as of 07:46, 10 March 2016
Line 27:		Line 27:
	== Literature ==		== Literature ==

	For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis.		For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

TobiasFritz at 12:35, 10 March 2016

2016-03-10T12:35:49Z

← Older revision		Revision as of 05:35, 10 March 2016
Line 11:		Line 11:
	=== Maximal one ===		=== 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>.		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 an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; 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>.		In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families.

	=== Using minimal transversals ===		=== 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~~>		It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>.

			Various reformulations of this can be found in the paper above.

			=== Using free sets ===

			A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (This terminology seems motivated by the dual notion for intersection-closed families, applied to the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

	== Literature ==		== Literature ==

	For intersection-closed families, there are plenty of papers in certain areas of artificial intelligence research, including data analysis and formal concept analysis.		For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis.

TobiasFritz: begin adding content

2016-03-09T10:37:36Z

begin adding content

← Older revision		Revision as of 03:37, 9 March 2016
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.

TobiasFritz: created with essentially no content yet

2016-03-09T09:21:52Z

created with essentially no content yet

New page

The members of a union-closed family can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses.