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

browser freeze McCune group example #28

Open
Jean-Luc-Picard-2021 opened this issue May 1, 2024 · 2 comments
Open

browser freeze McCune group example #28

Jean-Luc-Picard-2021 opened this issue May 1, 2024 · 2 comments

Comments

@Jean-Luc-Picard-2021
Copy link

Jean-Luc-Picard-2021 commented May 1, 2024

I am trying the McCune group example, and I noticed a browser freeze:

image

Its usually freezing here:

image

The problem link is:

https://www.umsu.de/trees/#(~6X(m(0,X)=X)~1~6X(m(i(X),X)=0)~1~6X~6Y~6Z(m(m(X,Y),Z)=m(X,m(Y,Z))))~5(m(a,b)=m(b,a))

@wo
Copy link
Owner

wo commented May 4, 2024

The problem occurs in the equality reasoner. The script doesn't seem to be stuck in a loop, but it's exploring too many possibilities, considering deeply nested terms like "[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,[m,[i,ξ4],ξ4],[m,ξ2,ξ3]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]".

Need to investigate.

@Jean-Luc-Picard-2021
Copy link
Author

Jean-Luc-Picard-2021 commented May 5, 2024

Its a quite difficult problem when attacked brute force.
And maybe what you show is a large Skolem term?

You find some timing mesurements here, by a method
that works without Skolemization, just as McCune's Mace4
does. The method is without Skolemization and also

without caching, basically a classical DPLL variant, i.e.
heavy backtracking which doesn't use much space,
only much time:

does this terminate, i.e. model finder
trealla-prolog/trealla#533

Ciao Prolog does it in about 4 minutes. McCune
himself does it in less than 1 second, according to
the Mace4 PDF. Mace4 applies some cell selection

ordering and some symmetry breaking heuristics,
making it not really brute force. Unfortunately I
could not yet replicate these heuristics in Prolog.

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

No branches or pull requests

2 participants