Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Prove (or disprove) "iter after iter" equation #187

Open
Lysxia opened this issue Aug 15, 2020 · 1 comment
Open

Prove (or disprove) "iter after iter" equation #187

Lysxia opened this issue Aug 15, 2020 · 1 comment
Labels
question Further information is requested

Comments

@Lysxia
Copy link
Collaborator

Lysxia commented Aug 15, 2020

@YaZko wondered about this equation to rewrite the sequential composition of two iter:

iter f >>> iter g
=
inl_ >>> iter (case_ (f >>> inl_) (g >>> inr_ >>> assoc_l))

Because the equation looks similar to theorems we've already proved about loop rather than iter, I think it's provable from the iterative axioms but haven't succeeded at it. Another way is to specialize it to itree and construct the bisimulation explicitly.

It might actually be simpler and more interesting to implement a solver to settle this type of question once and for all, although I don't know whether the problem is decidable.

@Lysxia Lysxia added the question Further information is requested label Aug 15, 2020
@YaZko
Copy link
Collaborator

YaZko commented Aug 17, 2020

I proved the equation in the special case of itrees (see db77cb9).

I remain very curious as to whether it can be proved abstractly.
Certainly investigating the decidability of all the equational theory sounds interesting!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
question Further information is requested
Projects
None yet
Development

No branches or pull requests

2 participants