|
Size: 3837
Comment:
|
← Revision 13 as of 2011-02-03 09:51:20 ⇥
Size: 4532
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Predicates == * '''Input''': company/1, owns/3 * '''Query''': hasMaxControls/1 * '''Output''': controls/2 |
|
| Line 14: | Line 6: |
| Line 29: | Line 20: |
| == Predicates == * '''Input''': {{{company/1, owns/3, hasMaxControls/1}}} * '''Output''': {{{controls/2}}} |
|
| Line 31: | Line 28: |
| The company C is specified by an a ground query for predicate "hasMaxControls", for example: | The company C is specified by a ground query for predicate "hasMaxControls", for example: |
| Line 33: | Line 30: |
| hasMaxControls(c1)? | {{{hasMaxControls(c1).}}} |
| Line 37: | Line 34: |
| company(c1). company(c2). company(c3). company(c4). | {{{company(c1). company(c2). company(c3). company(c4).}}} |
| Line 42: | Line 39: |
| owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). | {{{owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51).}}} |
| Line 48: | Line 45: |
| controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4). | {{{controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4).}}} |
| Line 52: | Line 49: |
| == Example == | == Example(s) == |
| Line 55: | Line 52: |
| {{{ | |
| Line 58: | Line 55: |
| hasMaxControls(c1)? | hasMaxControls(c1). }}} |
| Line 61: | Line 58: |
| {{{ | |
| Line 63: | Line 60: |
| }}} | |
| Line 73: | Line 70: |
| {{{ | |
| Line 76: | Line 73: |
| hasMaxControls(c3)? | hasMaxControls(c3). }}} the output should be {{{INCONSISTENT}}} |
| Line 78: | Line 77: |
| the output should be NO ANSWER SET FOUND | == Notes and Updates == * Specification: updated on date 26/01/2011; The problem goal is slightly changed with respect to the former competition. * Training Instances: updated on date 03/02/2011; == Problem peculiarities == '''Type''': Search/P '''Competition''': Model & Solve only The problem has polynomial complexity. Worth noting however, that its natural declarative specification requires the availability of an aggregate quantifier (a sum) which is recursively dependent from the predicate one aggregates on. We expect thus this benchmark will stress both modelling skills and the ability of efficiently evaluating this kind of encoding. |
| Line 81: | Line 90: |
| Author: Mario Alviano <<BR>> Affiliation: University of Calabria, Italy |
* Author: Mario Alviano * Affiliation: University of Calabria, Italy |
Company Controls
Contents
Problem Description
Company Controls is a problem in the area of stock market, in which the goal is to determine the pair of companies X,Y such that X controls Y, given information on stock possessions of companies. We are interested in a decision version of this problem.
Given a situation of shareholdership and a company C, is it true that C is the main controller? In other words, is the number of companies controlled by C greater than or equals to the number of companies controlled by any other company?
Remind that, in order to control a company Y, a company X has to exert control over more than 50% of the stock of Y. Company X can exert control over stock of Y in two different ways: X itself may possess a certain percentage of stock of Y, in this case we say that X directly exerts control over the respective percentage of stock of Y. Alternatively, if X controls a company Z, which exerts control over stock of Y, then we say that X indirectly exerts control over the respective stock of Y. Company X then exerts control over the sum of stock of Y over which it directly and indirectly exerts control. Alternatively, we can define the control relation inductively, by saying that company X controls Y if the sum of the shares in Y possessed by X and by companies controlled by X is more than 50%.
The input is comprised of the company C, the set of all companies and the percentages of directly controlled stock.
More details in the following papers:
* Inderpal Singh Mumick and Hamid Pirahesh and Raghu Ramakrishnan, "The Magic of Duplicates and Aggregates", Proceedings of the 16th International Conference on Very Large Data Bases (VLDB'90), pp. 264-277;
* David B. Kemp and Peter J. Stuckey, "Semantics of Logic Programs with Aggregates", Proceedings of the International Symposium on Logic Programming (ISLP'91), pp. 387-401.
Predicates
Input: company/1, owns/3, hasMaxControls/1
Output: controls/2
Input format
The company C is specified by a ground query for predicate "hasMaxControls", for example:
hasMaxControls(c1).
The set of companies is specified by instances of "company", for example:
company(c1). company(c2). company(c3). company(c4).
The percentages of directly controlled stock is given by instances of "owns", for example:
owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51).
Output format
If the number of companies which are controlled by C is greater than or equals to the number of controlled companies by any other company, the output should be a witness specified by instances of "controls", where controls(x,y) states that company x exerts control on company y. For example, a valid output for the instance above is the following:
controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4).
Otherwise, if there is a company exerting control on a number of companies greater than the number of companies controlled by C, the output should be the string "NO ANSWER SET FOUND".
Example(s)
For the input
company(c1). company(c2). company(c3). company(c4). owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). hasMaxControls(c1).
the output should be
controls(c1,c2). controls(c1,c3). controls(c1,c4). controls(c3,c4).
because
- c1 controls 3 companies, that is c2, c3, c4;
- c3 controls only 1 company, that is c4;
- c2 and c4 do not control any company.
Similarly, for
company(c1). company(c2). company(c3). company(c4). owns(c1,c2,60). owns(c1,c3,20). owns(c2,c3,40). owns(c3,c4,51). hasMaxControls(c3).
the output should be INCONSISTENT
Notes and Updates
- Specification: updated on date 26/01/2011; The problem goal is slightly changed with respect to the former competition.
- Training Instances: updated on date 03/02/2011;
Problem peculiarities
Type: Search/P Competition: Model & Solve only
The problem has polynomial complexity. Worth noting however, that its natural declarative specification requires the availability of an aggregate quantifier (a sum) which is recursively dependent from the predicate one aggregates on. We expect thus this benchmark will stress both modelling skills and the ability of efficiently evaluating this kind of encoding.
Author(s)
- Author: Mario Alviano
- Affiliation: University of Calabria, Italy