welcome: please sign in
location: Diff for "FinalProblemDescriptions/MinimalDiagnosis"
Differences between revisions 1 and 12 (spanning 11 versions)
⇤ ← Revision 1 as of 2011-01-18 16:51:53 →
Size: 2795
Editor: CarmenSantoro
Comment:
← Revision 12 as of 2011-02-08 13:36:37 → ⇥
Size: 4315
Editor: GiovambattistaIanni
Comment:
Deletions are marked like this. Additions are marked like this.
Line 7: Line 7:
* Input Predicates: edge/2, input/1, obs_elabel/3, obs_vlabel/2, vertex/1

* Output Predicates: active/1

This problem is motivated by an existing application in systems biology, described here:

http://www.cs.uni-potsdam.de/wv/pdfformat/gescthve10a.pdf		 This problem is motivated by an existing application in systems biology, described here: http://www.cs.uni-potsdam.de/wv/pdfformat/gescthve10a.pdf
Line 16: Line 10:
{{{
vertex(0). ... vertex(n).
input(i_0). ... input(i_m).
obs_vlabel(v_0,l_0). ... obs_vlabel(v_j,l_j).
Line 17: Line 15:
vertex(0). ... vertex(n). <<BR>>
input(i_0). ... input(i_m). <<BR>>
obs_vlabel(v_0,l_0). ... obs_vlabel(v_j,l_j). <<BR>>

edge(e_0,e_1). ... edge(e_{k-1},e_k). <<BR>>
obs_elabel(e_0,e_1,s_(0,1)). ... obs_elabel(e_{k-1},e_k,s_(k-1,k)). <<BR>>		 edge(e_0,e_1). ... edge(e_{k-1},e_k).
obs_elabel(e_0,e_1,s_(0,1)). ... obs_elabel(e_{k-1},e_k,s_(k-1,k)).
}}}
Line 26: Line 20:
{{{
i_0,...,i_m, v_0,...,v_j, e_0,...,e_k.
}}}
The following vertex labels or edge labels, respectively, are either "p" or "m" each:
{{{
l_0,...,l_j, s_(0,1),...,s_(k-1,k).
}}}
A total labeling of vertices is a total function f : [0,n] -> {p,m} such that f(v,,i,,) = l,,i,, if a fact {{{obs_vlabel(v_i,l_i)}}} belongs to the input.
Line 27: Line 29:
i_0,...,i_m, v_0,...,v_j, e_0,...,e_k. The labeling f is consistent for a vertex v in [0,n] if the following holds:
Line 29: Line 31:
The following vertex labels or edge labels, respectively, are either "p" or "m" each:  * If f(v) = p, then there is some u in [0,n] for which {{{edge(u,v)}}}, {{{obs_elabel(u,v,s)}}}, and f(u) = s hold.
 * If f(v) = m, then there is some u in [0,n] for which {{{edge(u,v)}}}, {{{obs_elabel(u,v,s)}}}, and f(u) = t hold such that s is different from t.
Line 31: Line 34:
l_0,...,l_j, s_(0,1),...,s_(k-1,k). A Minimal Inconsistent Core M is a subset of [0,n] \ {i,,0,,,...,i,,m,,} such that:
Line 33: Line 36:
A total labeling of vertices is a total function f : [0,n] -> {p,m} such that f(v_i) = l_i
if a fact obs_vlabel(v_i,l_i) belongs to the input. The labeling f is consistent
for a vertex v in [0,n] if the following holds:		  * There is no total labeling f that is consistent for every vertex v in M.
 * For every proper subset N of M, there is some total labeling f that is consistent for every vertex v in N.
Line 37: Line 39:
 - If f(v) = p, then edge(u,v), obs_elabel(u,v,s), and f(u) = s hold.
 - If f(v) = m, then edge(u,v), obs_elabel(u,v,s), and f(u) = t hold such that s is different from t. 		Note that vertices in the relation expressed by predicate {{{input/1}}} cannot belong to a Minimal Inconsistent Core.
Line 40: Line 41:
A Minimal Inconsistent Core M is a subset of [0,n] \ {i_0,...,i_m} such that: A solution, i.e., a Minimal Inconsistent Core is represented by instances of active/1: {{{active(v)}}}.
Line 42: Line 43:
 - There is no total labeling f that is consistent for every vertex v in M.
 - For every proper subset N of M, there is some total labeling f that is consistent for every
  vertex v in N.		 The vertices v for which {{{active(v)}}} holds must form a Minimal Inconsistent Core for the given input.
Line 46: Line 45:
A solution, i.e., a Minimal Inconsistent Core is represented by instances of active/1:

active(v).

The vertices v for which active(v) holds must form a Minimal Inconsistent Core for the given input.

Verifying whether a given set of vertices is a Minimal Inconsistent Core is D^P-complete, cf.:		 Verifying whether a given set of vertices is a Minimal Inconsistent Core is D^P^-complete, cf.:
Line 57: Line 50:
== Example == == Predicates ==

 * '''Input''': {{{edge/2, input/1, obs_elabel/3, obs_vlabel/2, vertex/1}}}

 * '''Output''': {{{active/1}}}

== Input format ==

Vertices of the input graph are specified by means of predicate {{{vertex/1}}}.
More specifically, if the graph has {{{n}}} vertices, the input comprises
{{{n+1}}} facts of the form {{{vertex(i)}}}, where {{{i = 0, ..., n}}}.

A set of vertices that cannot belong to a Minimal Inconsistent Core is specified
by means of predicate {{{input/1}}}.

Edges of the input graph are specified by means of predicate {{{edge/2}}}.

A partial labeling of vertices is specified by means of predicate {{{obs_vlabel/2}}},
where the first argument is a vertex index (an integer between 0 and n),
and the second argument is either {{{p}}} or {{{m}}}.

A total labeling of edges is specified by means of predicate {{{obs_elabel/3}}},
where the first two arguments represent an edge,
and the third argument is either {{{p}}} or {{{m}}}.


== Output format ==

A Minimal Inconsistent Core represented by means of predicate {{{active/1}}}.
More specifically, the output should comprise facts of the form {{{active(v)}}}
whenever the vertex {{{v}}} is part of the Minimal Inconsistent Core.

== Example(s) ==
Line 60: Line 85:
{{{
vertex(0). vertex(1). vertex(2). vertex(3). vertex(4).
obs_vlabel(1,p). obs_vlabel(3,p).
Line 61: Line 89:
vertex(0). vertex(1). vertex(2). vertex(3). vertex(4). <<BR>>
obs_vlabel(1,p). obs_vlabel(3,p).<<BR>>

edge(0,1). edge(0,3). edge(0,4). <<BR>>
obs_elabel(0,1,p). obs_elabel(0,3,m). obs_elabel(0,4,m). <<BR>>		 edge(0,1). edge(0,3). edge(0,4).
obs_elabel(0,1,p). obs_elabel(0,3,m). obs_elabel(0,4,m).
Line 78: Line 103:
}}}
The only Minimal Inconsistent Core contains the vertices 0 and 3. It is represented by:
{{{
active(0). active(3).
}}}
Line 79: Line 109:
The only Minimal Inconsistent Core contains the vertices 0 and 3. It is represented by: Example Figure:
Line 81: Line 111:
active(0). active(3). {{attachment:mindiagfig.png|Example Figure|width=600}}

== Author(s) ==
 * Author: Martin Gebser
   * Affiliation: University of Potsdam

Minimal Diagnosis

Contents

  1. Minimal Diagnosis
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Author(s)

Problem Description

This problem is motivated by an existing application in systems biology, described here: http://www.cs.uni-potsdam.de/wv/pdfformat/gescthve10a.pdf

The input is an influence graph provided in terms of facts of the form: 

vertex(0). ... vertex(n).
input(i_0). ... input(i_m). 
obs_vlabel(v_0,l_0). ... obs_vlabel(v_j,l_j). 

edge(e_0,e_1). ... edge(e_{k-1},e_k). 
obs_elabel(e_0,e_1,s_(0,1)). ... obs_elabel(e_{k-1},e_k,s_(k-1,k)).

The facts over vertex/1 include consecutive integers in [0,n] as the names of vertices. The values of the following arguments of other facts are also in [0,n]: 

i_0,...,i_m, v_0,...,v_j, e_0,...,e_k.

The following vertex labels or edge labels, respectively, are either "p" or "m" each: 

l_0,...,l_j, s_(0,1),...,s_(k-1,k).

A total labeling of vertices is a total function f : [0,n] -> {p,m} such that f(vi) = li if a fact obs_vlabel(v_i,l_i) belongs to the input.

The labeling f is consistent for a vertex v in [0,n] if the following holds:

  • If f(v) = p, then there is some u in [0,n] for which edge(u,v), obs_elabel(u,v,s), and f(u) = s hold.

  • If f(v) = m, then there is some u in [0,n] for which edge(u,v), obs_elabel(u,v,s), and f(u) = t hold such that s is different from t.

A Minimal Inconsistent Core M is a subset of [0,n] \ {i0,...,im} such that:

  • There is no total labeling f that is consistent for every vertex v in M.
  • For every proper subset N of M, there is some total labeling f that is consistent for every vertex v in N.

Note that vertices in the relation expressed by predicate input/1 cannot belong to a Minimal Inconsistent Core.

A solution, i.e., a Minimal Inconsistent Core is represented by instances of active/1: active(v).

The vertices v for which active(v) holds must form a Minimal Inconsistent Core for the given input.

Verifying whether a given set of vertices is a Minimal Inconsistent Core is DP-complete, cf.:

Papadimitriou, C. and Yannakakis, M. 1982. The complexity of facets (and some facets of complexity). Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC’82). ACM Press, 255–260.

Predicates

  • Input: edge/2, input/1, obs_elabel/3, obs_vlabel/2, vertex/1

  • Output: active/1

Input format

Vertices of the input graph are specified by means of predicate vertex/1. More specifically, if the graph has n vertices, the input comprises n+1 facts of the form vertex(i), where i = 0, ..., n.

A set of vertices that cannot belong to a Minimal Inconsistent Core is specified by means of predicate input/1.

Edges of the input graph are specified by means of predicate edge/2.

A partial labeling of vertices is specified by means of predicate obs_vlabel/2, where the first argument is a vertex index (an integer between 0 and n), and the second argument is either p or m.

A total labeling of edges is specified by means of predicate obs_elabel/3, where the first two arguments represent an edge, and the third argument is either p or m.

Output format

A Minimal Inconsistent Core represented by means of predicate active/1. More specifically, the output should comprise facts of the form active(v) whenever the vertex v is part of the Minimal Inconsistent Core.

Example(s)

Consider the following input: 

vertex(0). vertex(1). vertex(2). vertex(3). vertex(4). 
obs_vlabel(1,p). obs_vlabel(3,p).

edge(0,1).         edge(0,3).         edge(0,4).
obs_elabel(0,1,p). obs_elabel(0,3,m). obs_elabel(0,4,m).

edge(1,0).
obs_elabel(1,0,p).

edge(1,2).
obs_elabel(1,2,p).

edge(2,4).
obs_elabel(2,4,m).

edge(3,1).         edge(3,2).         edge(3,4).
obs_elabel(3,1,p). obs_elabel(3,2,p). obs_elabel(3,4,p).

The only Minimal Inconsistent Core contains the vertices 0 and 3. It is represented by: 

active(0). active(3).

Example Figure:

Example Figure

Author(s)

  • Author: Martin Gebser
    • Affiliation: University of Potsdam

ASP Competition 2011: FinalProblemDescriptions/MinimalDiagnosis (last edited 2011-02-08 13:36:37 by GiovambattistaIanni)