Solving ../../benchmarks/smtlib/true/timbuk_reverseImplies.smt2...

Inference procedure has parameters:
Ice fuel: 200
Timeout: Some(60.) (sec)
Teacher_type: Checks all clauses every time
Approximation method: remove every clause that can be safely removed



Learning problem is:

env: {
elt -> {a, b}  ;  eltlist -> {cons, nil}
}
definition:
{
(leq, P:
{
leq(a, y) <= True
leq(b, b) <= True
False <= leq(b, a)
}
)
(append, F:
{
append(nil, l2, l2) <= True
append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf)
}
eq_eltlist(_tf, _uf) <= append(_rf, _sf, _tf) /\ append(_rf, _sf, _uf)
)
(reverse, F:
{
reverse(nil, nil) <= True
reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf)
}
eq_eltlist(_yf, _zf) <= reverse(_xf, _yf) /\ reverse(_xf, _zf)
)
(insert, F:
{
insert(x, nil, cons(x, nil)) <= True
insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag)
insert(x, cons(y, z), cons(x, cons(y, z))) <= leq(x, y)
}
eq_eltlist(_dg, _eg) <= insert(_bg, _cg, _dg) /\ insert(_bg, _cg, _eg)
)
(sort, F:
{
sort(nil, nil) <= True
sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg)
}
eq_eltlist(_ig, _jg) <= sort(_hg, _ig) /\ sort(_hg, _jg)
)
(sorted, P:
{
sorted(cons(x, nil)) <= True
sorted(nil) <= True
}
)
}

properties:
{
sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l)
}


over-approximation: {append, insert, leq, reverse, sort}
under-approximation: {insert, leq, sort}

Clause system for inference is:

{
append(nil, l2, l2) <= True -> 0
reverse(nil, nil) <= True -> 0
sorted(cons(x, nil)) <= True -> 0
sorted(nil) <= True -> 0
reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf) -> 0
append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf) -> 0
insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag) -> 0
sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg) -> 0
sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l) -> 0
}


Solving took 0.075008 seconds.
Yes: |_
name: None

append ->
[
append : <eltlist * eltlist * eltlist>
{
  append(cons(x_0_0, x_0_1), cons(x_1_0, x_1_1), cons(x_2_0, x_2_1)) <= True
  append(cons(x_0_0, x_0_1), nil, cons(x_2_0, x_2_1)) <= True
  append(nil, cons(x_1_0, x_1_1), cons(x_2_0, x_2_1)) <= True
  append(nil, nil, nil) <= True
}
]


;
insert ->
[
insert : <elt * eltlist * eltlist>
{
  
}
]


;
leq ->
[
leq : <elt * elt>
{
  
}
]


;
reverse ->
[
reverse : <eltlist * eltlist>
{
  reverse(cons(x_0_0, x_0_1), cons(x_1_0, x_1_1)) <= True
  reverse(nil, nil) <= True
}
]


;
sort ->
[
sort : <eltlist * eltlist>
{
  
}
]


;
sorted ->
[
sorted : <eltlist>
{
  sorted(cons(x_0_0, x_0_1)) <= True
  sorted(nil) <= True
}
]



--
Equality automata are defined for: {elt, eltlist}
_|
-------------------
STEPS:
-------------------------------------------
Step 0, which took 0.014603 s (model generation: 0.014445,  model checking: 0.000158):

Clauses:
{
append(nil, l2, l2) <= True -> 0
reverse(nil, nil) <= True -> 0
sorted(cons(x, nil)) <= True -> 0
sorted(nil) <= True -> 0
reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf) -> 0
append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf) -> 0
insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag) -> 0
sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg) -> 0
sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l) -> 0
}

Accumulated learning constraints:
{

}

Current best model:
|_
name: None

append ->
[
append : <eltlist * eltlist * eltlist>
{
  
}
]


;
insert ->
[
insert : <elt * eltlist * eltlist>
{
  
}
]


;
leq ->
[
leq : <elt * elt>
{
  
}
]


;
reverse ->
[
reverse : <eltlist * eltlist>
{
  
}
]


;
sort ->
[
sort : <eltlist * eltlist>
{
  
}
]


;
sorted ->
[
sorted : <eltlist>
{
  
}
]



--
Equality automata are defined for: {elt, eltlist}
_|




Answer of teacher:

append(nil, l2, l2) <= True  :
Yes: {
l2 -> nil
}

reverse(nil, nil) <= True  :
Yes: {

}

sorted(cons(x, nil)) <= True  :
Yes: {

}

sorted(nil) <= True  :
Yes: {

}

reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf)  :
No: ()

append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf)  :
No: ()

insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag)  :
No: ()

sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg)  :
No: ()

sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l)  :
No: ()


-------------------------------------------
Step 1, which took 0.015892 s (model generation: 0.015799,  model checking: 0.000093):

Clauses:
{
append(nil, l2, l2) <= True -> 0
reverse(nil, nil) <= True -> 0
sorted(cons(x, nil)) <= True -> 0
sorted(nil) <= True -> 0
reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf) -> 0
append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf) -> 0
insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag) -> 0
sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg) -> 0
sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l) -> 0
}

Accumulated learning constraints:
{
append(nil, nil, nil) <= True
reverse(nil, nil) <= True
sorted(cons(a, nil)) <= True
sorted(nil) <= True
}

Current best model:
|_
name: None

append ->
[
append : <eltlist * eltlist * eltlist>
{
  append(nil, nil, nil) <= True
}
]


;
insert ->
[
insert : <elt * eltlist * eltlist>
{
  
}
]


;
leq ->
[
leq : <elt * elt>
{
  
}
]


;
reverse ->
[
reverse : <eltlist * eltlist>
{
  reverse(nil, nil) <= True
}
]


;
sort ->
[
sort : <eltlist * eltlist>
{
  
}
]


;
sorted ->
[
sorted : <eltlist>
{
  sorted(cons(x_0_0, x_0_1)) <= True
  sorted(nil) <= True
}
]



--
Equality automata are defined for: {elt, eltlist}
_|




Answer of teacher:

append(nil, l2, l2) <= True  :
Yes: {
l2 -> cons(_mfmcd_0, _mfmcd_1)
}

reverse(nil, nil) <= True  :
No: ()

sorted(cons(x, nil)) <= True  :
No: ()

sorted(nil) <= True  :
No: ()

reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf)  :
No: ()

append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf)  :
Yes: {
_qf -> nil  ;  l2 -> nil  ;  t1 -> nil
}

insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag)  :
No: ()

sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg)  :
No: ()

sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l)  :
No: ()


-------------------------------------------
Step 2, which took 0.018216 s (model generation: 0.018073,  model checking: 0.000143):

Clauses:
{
append(nil, l2, l2) <= True -> 0
reverse(nil, nil) <= True -> 0
sorted(cons(x, nil)) <= True -> 0
sorted(nil) <= True -> 0
reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf) -> 0
append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf) -> 0
insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag) -> 0
sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg) -> 0
sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l) -> 0
}

Accumulated learning constraints:
{
append(cons(a, nil), nil, cons(a, nil)) <= True
append(nil, cons(a, nil), cons(a, nil)) <= True
append(nil, nil, nil) <= True
reverse(nil, nil) <= True
sorted(cons(a, nil)) <= True
sorted(nil) <= True
}

Current best model:
|_
name: None

append ->
[
append : <eltlist * eltlist * eltlist>
{
  append(cons(x_0_0, x_0_1), nil, cons(x_2_0, x_2_1)) <= True
  append(nil, cons(x_1_0, x_1_1), cons(x_2_0, x_2_1)) <= True
  append(nil, nil, nil) <= True
}
]


;
insert ->
[
insert : <elt * eltlist * eltlist>
{
  
}
]


;
leq ->
[
leq : <elt * elt>
{
  
}
]


;
reverse ->
[
reverse : <eltlist * eltlist>
{
  reverse(nil, nil) <= True
}
]


;
sort ->
[
sort : <eltlist * eltlist>
{
  
}
]


;
sorted ->
[
sorted : <eltlist>
{
  sorted(cons(x_0_0, x_0_1)) <= True
  sorted(nil) <= True
}
]



--
Equality automata are defined for: {elt, eltlist}
_|




Answer of teacher:

append(nil, l2, l2) <= True  :
No: ()

reverse(nil, nil) <= True  :
No: ()

sorted(cons(x, nil)) <= True  :
No: ()

sorted(nil) <= True  :
No: ()

reverse(cons(h1, t1), _wf) <= append(_vf, cons(h1, nil), _wf) /\ reverse(t1, _vf)  :
Yes: {
_vf -> nil  ;  _wf -> cons(_rfmcd_0, _rfmcd_1)  ;  t1 -> nil
}

append(cons(h1, t1), l2, cons(h1, _qf)) <= append(t1, l2, _qf)  :
Yes: {
_qf -> cons(_tfmcd_0, _tfmcd_1)  ;  l2 -> cons(_ufmcd_0, _ufmcd_1)  ;  t1 -> nil
}

insert(x, cons(y, z), cons(y, _ag)) \/ leq(x, y) <= insert(x, z, _ag)  :
No: ()

sort(cons(y, z), _gg) <= insert(y, _fg, _gg) /\ sort(z, _fg)  :
No: ()

sorted(_lg) <= reverse(_kg, _lg) /\ reverse(l, _kg) /\ sorted(l)  :
No: ()


Total time: 0.075008
Learner time: 0.048317
Teacher time: 0.000394
Reasons for stopping: Yes: |_
name: None

append ->
[
append : <eltlist * eltlist * eltlist>
{
  append(cons(x_0_0, x_0_1), cons(x_1_0, x_1_1), cons(x_2_0, x_2_1)) <= True
  append(cons(x_0_0, x_0_1), nil, cons(x_2_0, x_2_1)) <= True
  append(nil, cons(x_1_0, x_1_1), cons(x_2_0, x_2_1)) <= True
  append(nil, nil, nil) <= True
}
]


;
insert ->
[
insert : <elt * eltlist * eltlist>
{
  
}
]


;
leq ->
[
leq : <elt * elt>
{
  
}
]


;
reverse ->
[
reverse : <eltlist * eltlist>
{
  reverse(cons(x_0_0, x_0_1), cons(x_1_0, x_1_1)) <= True
  reverse(nil, nil) <= True
}
]


;
sort ->
[
sort : <eltlist * eltlist>
{
  
}
]


;
sorted ->
[
sorted : <eltlist>
{
  sorted(cons(x_0_0, x_0_1)) <= True
  sorted(nil) <= True
}
]



--
Equality automata are defined for: {elt, eltlist}
_|