# Candidatura PEx - Zugzwang


## 2024-01-05 - Next Research Lines

> After the base-setting work of "_An Algebraic Approach to Stochastic ASP_" these are the next tasks to consider. Is summary:
> 1. **Logic Programming** - Stratified & Non-stratified programs
> 2. **Computer Science** - Inductive Logic Programming
> 3. **Software** - Integration with Potassco and other frameworks
> 4. **Applications**

#### Line 1: Logic Programming - Stratified & Non-stratified programs

##### Line 1a - Logic Programs Structure and Properties

> _Stratified_ & _non-stratified_ programs are quoted in the "CREDAL" papers as important classes of logic programs.

Minimal example of a **non-stratified program**.

The following annotated LP, with clauses $c_1, c_2, c_3$ respectively, is non-stratified (because has a cycle with negated arcs) but no head is disjunctive:
```prolog
0.3::a.                 % c1
b :- not c, not a.      % c2
c :- not b.             % c3
```

This program has three stable models:
$$
\begin{aligned}
m_1 &= \set{ a, c } \cr
m_2 &= \set{ \neg a, b } \cr
m_3 &= \set{ \neg a, c }
\end{aligned}
$$

> We should **investigate** _What are stratified programs and why are they important?_ and how does our approach deals with such programs?

##### Line 1b - Investigate the expressiveness of PASP

Consider:

- Recursion
- Variables,
- Functional symbols,

##### Line 1c - The equivalence relation

Consider the cases where only $s \subseteq e$ and $e \subseteq s$. Or other refinements. Also consider the inconsistent and independent events.

##### Line 1d - Stability of the error function

Consider alternative error functions. See statistics, Kullback-Leibler divergence

#### Line 2: Computer Science - Inductive Logic Programming

> Proceed from scoring programs to support genetic algorithms or other program space exploration methods.

Scoring programs, as described in our paper, is just a step into **Inductive Logic Programming**. To go further, we need to explore algorithms that:

1. Use **background knowledge**, expressed as a PLP.
2. Consult **positive examples** that should be _soft_ induced.
3. Consult **negative examples** that should be _soft_ excluded.
4. Generate **PLPs** that are scored.
5. Recombine the **best scored** into a new _population_, using recombination rules.

> In order to do that, **PLPs must be expressed as data structures** to be manipulated. Also **recombination rules** must investigated before become formally expressed and supported with adequate methods.

#### Line 3: Software - Integration with Potassco and other frameworks

> Support annotated programs with zugzwang semantics.

- Bayesian Networks (BII Alice)
  - Generate an annotated asp program from a bayesian network and run it trough `clingo`.
  - Recover the stable models from the previous ste and compute the respective probabilities.
- Program Manipulation
  - Annotated ASP program _representation_ and a _parser_.

#### Line 4: Applications

> Apply zugzwang to a few showcases, besides the theoretic corner stones (non-stratified, disjunctive, bayes networks), preferably based in real world scenarios, with complex structure and large datasets.

- (Stochastic) Plan Generation
- Yale-Shooting Problem
- (Stochastic) Situation Calculus
- Frame Problem
- Latent Facts - and core assumptions.
- Given a **Bayesian Network** (or a **Markov Networks**):
  - Represent it. (**done** for BNs; MNs?)
  - Solve the common probability tasks: join (**done**), marginals, conditionals, parameter learning, inferring unobserved variables, sample generation, _etc._
- Given a _solved_ ASP specification:
  - What is the marginal probability of the atom `a`? (**done**)
  - What other probability queries are important to consider?
- Given an _unsolved_ ASP specification:
  - What is the probability (distribution?) of the probabilistic fact `a`?
  - What other questions are relevant? _E.g._ the distribution family of a fact?
- Given a _solved_ ASP specification and a set of _samples_:
  - How do the probabilities inferred from the specification match the ones from the empiric distribution? (**done** might see alternative approaches)
- Given two _solved_ ASP specification and a set of _samples_:
  - Which specification best describes the empiric distribution? (**done**)

## Tarefas

- [ ] Submeter
- [ ] Redigir
- [ ] Preparar
  - [ ] Consultar documentação
  - [ ] Reunir requisitos
  - [ ] Delinear proposta

## Memória Externa

- [ ] Irene
- [ ] Salvador