Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14767

Should we use minimum_coa/3 ? (Was: The good thing is we have at least Mercio’s Algorithm)

Show all headers | View raw

You have the habit to post incomplete code:

bfs_sort(X, Y):- minimum_coa(X, Is, Mcoa),

My friend, where did you hide the predicate
minimum_coa/3 ? Also its irrelevant to mercio/3
or any frontier method. The TRUNCATIONS are
the same either with

or without a canonical form as input. The
only thing that might be a little faster is
the (==)/2 pretest in mercio/3, and short cuts
like here profit also:

fpl_compare(C, [I-J|F], FPL, FPL0, Mcoa):-
	(	I = J -> fpl_compare(C, F, FPL, FPL0, Mcoa)

But practically one could also use same_term/2
and gain some speed. But given that minimum_coa/3
can be quite expensive, I don’t count this as the

real mercio/3 sorting method. If sorting is O(N * log(N))
for a fast compare but minimum_coa/3 is O(N^2),
not much is gained, rather contra productive.

Thats basically why bisimiliarity was invented
by Hopcroft and Carp and reported in their 1971
paper to avoid the trap of doing equality via
expensive canonical form.

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:52 +0200
  The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:48 +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 14:00 +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:11 +0200
  Szpilrajn Theorem and Suzumura Consistency (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:50 +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:10 +0200
      Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:13 +0200
        Re: Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
      Should we use minimum_coa/3 ? (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:45 +0200
        Perfectly balanced , as all things should be! (Was: Should we use minimum_coa/3 ?) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:49 +0200
  Mercios decidability was already attested in 2012 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:26 +0200
    Performance of Mercio’s Total Order (Was: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:49 +0200
      Fuzzy Testing is your Swiss Knife (Re: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:55 +0200
        Yeah, we have another name! (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:38 +0200
        Monte Carlo sampling the frontier version (Was: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:42 +0200
        AI most hated by formal verification (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-11-26 17:02 +0100
  An NPU could give 1000x more LIPS (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:19 +0100
    Neural Network based dif/2 respectively (#\=)/2 (Re: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:51 +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:03 +0100
        Googles TPU muscle in 2017 [Prolog Community is Sleepy Joe] (Re: Zeus: A Language for Expressing Algorithms in Hardware) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:23 +0100
    100% serious Giga Logical Inferences per Second (GLIPS) (Was: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:50 +0100
      The tables have turned: GigaLIP on the Laptop? (Re: 100% serious Giga Logical Inferences per Second (GLIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 15:12 +0100

csiph-web