Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Newsgroups | sci.math |
| Subject | The good thing is we have at least Mercio’s Algorithm (Re: Szpilrajn Theorem and Suzumura Consistency) |
| Date | 2025-08-06 08:09 +0200 |
| Message-ID | <106uria$3c5n2$2@solani.org> (permalink) |
| References | <106p0ct$3b6se$3@solani.org> <106u5h7$3bpia$3@solani.org> |
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