README.md 5.56 KB
Newer Older
Merlin's avatar
Merlin committed
1
# COOL - The **Co**algebraic **O**ntology **L**ogic Reasoner
2
3
4
5
6
7

[[_TOC_]]

COOL is a generic reasoner for modal, hybrid and fixpoint logics, developed jointly at FAU Erlangen-Nürnberg and the Australian National University ([Dirk Pattinson](http://users.cecs.anu.edu.au/~dpattinson/)); it can be instantiated to any modal, hybrid or alternation-free fixpoint logic admitting an axiomatization in terms of so-called rank-1 rules or axioms. Current instantiations include multimodal K (i.e. the description logic ALC), serial monotone neighborhood logic (the next-step logic of game logic GL), and coalition logic (the next-step logic of alternating temporal logic ATL). COOL currently supports global assumptions, i.e. general TBoxes, nominals, satisfaction operators; the latter features are similar in expressivity to Boolean ABoxes. COOL implements two global caching algorithms as separate reasoner cores: the global caching algorithm described in [this paper](http://link.springer.com/chapter/10.1007/978-3-642-14203-1_5) (also available [here](/wp-content/uploads/staff/schroeder/papers/hyGlobalCaching.pdf)) and the global caching algorithm for alternation-free fixpoint logics described in [this paper](http://drops.dagstuhl.de/opus/volltexte/2016/6172/pdf/LIPIcs-CONCUR-2016-34.pdf); the latter reasoner core decides the alternation-free mu-calculi over all supported logics (including in particular CTL, ATL and the star-nesting free fragment of GL). **Recently, the fixpoint core has been extended with support for aconjunctive mu-calculi via permutation games, as described [here](https://arxiv.org/pdf/1710.08996.pdf); an archive containing according binaries, a formula generator and benchmarking scripts is available [here](/wp-content/uploads/media/research/cool/artifact.zip).**


8
9
10
## Installation 

### Prebuilt Binaries
11
12
13
14
15
16
17

Alternatively, here is a [tarball](/wp-content/uploads/media/research/cool/cool-src-2014-02-01.tar.gz) of a snapshot. The sources of the global caching solver for [alternation-free](https://git8.cs.fau.de/software/cool) and **aconjunctive** mu-calculi can currently be found in separate branches of the repository. There also are

- a 64 bit linux build of COOL [cool-bin-x86_64.tar.gz](/wp-content/uploads/media/research/cool/cool-bin-x86_64.tar.gz) (2014-02-01);
- a 64 bit linux build of COOL including the alternation-free fixpoint solving core [cool-afmu-2016-05-24.tgz](/wp-content/uploads/media/research/cool/cool-afmu-2016-05-24.tgz) (2016-05-24).
- a 64 bit linux build of COOL **including the aconjunctive fixpoint solving core** [cool-x86-64-2017-11-07.zip](/wp-content/uploads/media/research/cool/cool-bin-x86_64.tar.gz/cool-x86-64-2017-11-07.zip) (2017-11-07).

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
### Dependencies

Install ocaml include files, minisat include files. Place them in the include
directory (e.g. `/usr/include`, `/usr/lib/ocaml`, or `.`).

Dependencies:
  - dune
  - ocamlfind (package called ocaml-findlib)
  - ocamlgraph (package ocaml-ocamlgraph)
  - readline
  - minisat (at least minisat 2)

On Debian or Ubuntu, install the following packages:
  - git
  - build-essential
  - dune
  - libocamlgraph-ocaml-dev
  - libreadline-dev
  - minisat


### Building from Source

To build the cool executable
```
dune build
```
Run it with
```
dune exec cool
```
To build everything just run
```
dune build @all
```
If you want the executables statically linked, then run the build with
the flag `--profile=static`.

#### Verbose manual installation tutorial of the git version

Install the packaged dependencies (see above). Install minisat, e.g. manually
via git:
```bash
git clone https://git8.cs.fau.de/software/cool
cd cool
./ci/apt-setup.sh
dune build @all
```

## Usage

To see a longer list of example formulas, just run the testsuite:

  dune exec cool-testsuite

### Coalition Logic

Some formulas are

```
[{1}] C & [{ 2 }] ~C
[{1}] C & <{ 2 }> ~C
[{1}] C & <{ 1 2 }> ~C
<{ 1 2 }> C & <{ 1 2 3 4 5 6 7 8 9 10 }> ~C
<{ 1 2 }> C & <{ 1 2 3 4 5 6 7 8 9 }> ~C
<{ 1 2 }> C & <{ 1 2 }> ~C
<{ 1 2 }> C & [{ 1 2 }] ~C
```

So call for example:
```bash
./coalg sat CL  <<< '<{ 1 2 }> C & [{ 1 2 }] ~C'
```

92
93
94
95
96
97
98
99
100
101
## Experimental Results 

**Recent benchmarking results that compare [MLSolver](https://github.com/tcsprojects/mlsolver) with the permutation game solving core of COOL for aconjunctive formulas can be found in this file: [benchmarks.zip](https://www8.cs.fau.de/_media/research:cool:benchmarks.zip)**

We also compare the runtimes of three variants of the CTL-instantiation of the alternation-free fixpoint-reasoning core of COOL (with different frequencies of intermediate propagation -- *always*, *never* and *adaptive*) with TreeTab and GMUL on various series of CTL formulas; for descriptions of the benchmark formulas and the provers TreeTab and GMUL, see *An Experimental Comparison of Theorem Provers for CTL*, R. Goré, J. Thomson and F. Widmann, TIME 2011. More benchmarking results can be found in this file: [comparison_CTL.zip](https://www8.cs.fau.de/_media/research:cool:comparison_CTL.zip)

## Literature 

- A system description of COOL ([COOL --- A Generic Satisfiability Checker For Coalgebraic Logics with Global Assumptions](https://www8.cs.fau.de/_media/research:papers:cool.pdf), D. Gorin, D. Pattinson, L. Schröder, F. Widmann and T. Wißmann) has been published at [IJCAR 2014](http://cs.nyu.edu/ijcar2014/).
- A paper on global caching for alternation-free fixpoint logics ([Global Caching for the Alternation-free µ-Calculus](http://drops.dagstuhl.de/opus/volltexte/2016/6172/pdf/LIPIcs-CONCUR-2016-34.pdf), D. Hausmann, L. Schröder and C. Egger) has been published at [CONCUR 2016](https://www.concur2016.ulaval.ca/no_cache/home/).