Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Newsgroups | sci.math |
| Subject | Re: Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) |
| Date | 2025-08-06 08:23 +0200 |
| Message-ID | <106usd2$3c6a7$3@solani.org> (permalink) |
| References | <106p0ct$3b6se$3@solani.org> <106u5h7$3bpia$3@solani.org> <106uria$3c5n2$2@solani.org> <106urv9$3c5n2$6@solani.org> |
Disclaimer: I don’t know whether Non-Naive HK is even allowed in this setting, and how one would exactly implement it. Realization should not distort future (<) or (>) outcomes. Mild Shock schrieb: > > How could we speed it up any further. Well > we can make at least the following observation. > Let A and B be two lists of truncation pairs. > > Capital greek letters denote sublists: > > A = Γ, P, Δ, P, Π > > B = Γ, P, Δ, Π > > Then mercio2_iter(A) gives the same comparison > like the shorter mercio2_iter(B). The truncation > leafs obey a contraction law. So if we find methods > > to get smaller pair lists, then I guess > we will also get faster Mercio’s Algorithm > implementation. Possible methods to contract the > > pair list are at least either Naive HK based > on same_term/2 or Non-Naive HK based on same_term/2: > > Hopcroft and Karp’s algorithm (HK) > https://inria.hal.science/hal-00639716v2 > > But there is a twist, which stuns me, how to > make contraction between levels? Is such an inter > level optimization even somehow defined? It seems > > levels are still copied during expansion? > > Mild Shock schrieb: >> >> The good thing is we have at least Mercio’s >> Algorithm. This can be used for Total Order Sorting >> of Prolog terms, cyclic and acyclic. But how speed >> >> it up? Here is a take. The idea is sketched as follows: >> >> Sketch to determine (<) or (>): >> >> 1. Use a list of pairs. These are the leafs of >> a truncation. >> 2. Compare this list, if the result >> differs from (=) you are done. >> 3. Expand the list of pairs to get a new level, >> and continue with step 1. >> >> The Prolog code reads as follows: >> >> Step 1: >> >> compare_truncs(C, []) :- !, C = (=). >> compare_truncs(C, [X-Y|_]) :- >> trunc(X, A), >> trunc(Y, B), >> compare(D, A, B), >> D \== (=), !, C = D. >> compare_truncs(C, [_|L]) :- >> compare_truncs(C, L). >> >> trunc(X, A) :- var(X), !, A = X. >> trunc(X, F/N) :- functor(X, F, N). >> >> Step 2: >> >> next_truncs([], []). >> next_truncs([X-_|L], R) :- var(X), !, >> next_truncs(L, R). >> next_truncs([X-Y|L], R) :- >> next_truncs(L, H), >> X =.. [_|A], >> Y =.. [_|B], >> zip(A, B, J), >> append(J, H, R). >> >> zip([], [], []). >> zip([X|L], [Y|R], [X-Y|H]) :- >> zip(L, R, H). >> >> Step 3: >> >> mercio2(C, X, Y) :- X == Y, !, C = (=). >> mercio2(C, X, Y) :- mercio2_iter(C, [X-Y]). >> >> mercio2_iter(C, L) :- >> compare_truncs(D, L), >> D \== (=), !, C = D. >> mercio2_iter(C, L) :- >> next_truncs(L, R), >> mercio2_iter(C, R). >> >> The new mercio2/3 is an itch faster than the old mercio/3: >> >> ?- X = s(s(X, 1), 0), Y = s(X, 1), >> Z = s(s(1, s(Z, 1)), 1), >> time((between(1,10000,_), mercio(C, X, Z), >> mercio(D, Z, Y), fail; true)). >> % Zeit 184 ms, GC 0 ms, Lips 11141728, Uhr 06.08.2025 07:39 >> >> ?- X = s(s(X, 1), 0), Y = s(X, 1), >> Z = s(s(1, s(Z, 1)), 1), >> time((between(1,10000,_), mercio2(C, X, Z), >> mercio2(D, Z, Y), fail; true)). >> % Zeit 145 ms, GC 0 ms, Lips 9379848, Uhr 06.08.2025 07:39 >> >> Mild Shock schrieb: >> > >> > Now question is whether compare_rat/2 can >> > be extended to a total order or not. On >> > the positive side we find that a partial >> > >> > order can always be extended: >> > >> > Szpilrajn Extension Theorem >> > https://en.wikipedia.org/wiki/Szpilrajn_extension_theorem >> > >> > But what if compare_rat/2 by @kuniaki.mukai >> > is not a partial order? What if it is only a >> > preorder, or even worse only a binary relation. >> > >> > Returning 4 values doesn’t guarantee that it >> > is a partial order. We have help from here: >> > >> > Szpilrajn, Arrow and Suzumura >> > >> https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-999X.2011.04130.x >> > >> > A binary relation needs to be Suzumura >> > consistent, so that it can be extended >> > into a total order. And compare_rat/2 is >> > >> > not Suzumura consistent, as the following >> > cycle a < c < b < a shows: >> > >> > /* Not SWI, Windows Console is SNAFU */ >> > ?- repeat, fuzzy(A), fuzzy(C), >> > compare_rat(_X, A, C), _X = (<), >> > fuzzy(B), compare_rat(_Y, C, B), _Y = (<), >> > compare_rat(_Z, B, A), _Z = (<). >> > A = s(s(A, A), 1), _A = s(_A, s(_, 1)), C = s(_A, _), >> > _B = s(1, _B), B = s(B, s(1, _B)) >> > >> > Was only testing with compare_rat/3, but >> > the theorem applies also to other compare >> > proposals, and can be used to exclude >> > >> > them, as soon as a Suzumura inconsistency is found. >
Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:54 +0200
The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:50 +0200
The Bitrot called Math Stack Exchange (Re: The Original Ganster (OG) of Gameification: IEEE 1044.1-1995) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:57 +0200
I guess its back to Hopcroft and Karp (Re: The Bitrot called Math Stack Exchange) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:12 +0200
Szpilrajn Theorem and Suzumura Consistency (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:53 +0200
The good thing is we have at least Mercio’s Algorithm (Re: Szpilrajn Theorem and Suzumura Consistency) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:09 +0200
Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:16 +0200
Re: Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
Mercios decidability was already attested in 2012 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:40 +0200
Performance of Mercio’s Total Order (Re: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:51 +0200
Fuzzy Testing is your Swiss Knife (Was: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:54 +0200
Yeah, we have another name! (Re: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:40 +0200
Monte Carlo sampling the frontier version (Re: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:44 +0200
An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:23 +0100
Zeus: A Language for Expressing Algorithms in Hardware (Re: Neural Network based dif/2 respectively (#\=)/2) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:02 +0100
100% serious Giga Logical Inferences per Second (GLIPS) (Re: An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:53 +0100
csiph-web