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

Groups > comp.lang.prolog > #14721

The Original Ganster (OG) of Bisimilarity are Hopcroft and Karp (1971) (Re: Fathers of Bisimulation: Robin Milner (1934–2010))

Show all headers | View raw

The Original Ganster (OG) of Bisimilarity are
Hopcroft and Karp (1971). These hand-outs discuss a
coalgebra with the compound ->(_,_) and the atom -.
Coalgebra seem to have the feature that both vertices

and edges have labels. The algorithm does attack a ~ b,
and nf(a) respectively nf(b) at the same time by using
union find. The algorithm is space linear, can be

implemented with an extra pointer in each Prolog compound
for the union find. Mostlikely what SWI-Prolo gdoes
with reference to Folk Knowledge and Bart Demoen. The

algorithm is also almost time linear:

Bisimulation and Equirecursive Equality -2014
https://www.cs.cornell.edu/courses/cs6110/2014sp/Lectures/lec35a.pdf

Mild Shock schrieb:
> Hi,
> 
> Despite these efforts:
> 
> The development of concurrent logic programming
> was given an impetus when Guarded Horn Clause was
> used to implement KL1, the systems programming
> language of the Japanese Fifth Generation
> Project (FGCS). The FGCS Project was a $400M
> initiative by Japan's Ministry of International
> Trade and Industry, begun in 1982, to use
> massively parallel computing/processing for
> artificial intelligence applications.
> https://en.wikipedia.org/wiki/Concurrent_logic_programming
> 
> And relation ship to rational trees, in
> Alain Colmerauers WINDOW PRINCIPLE, mostlikely
> Bisimulation has a more lasting impact.
> 
> But who were the founding fathers of bisimulation?
> 
> Robin Milner (1934–2010)
> Primary founder of the concept of bisimulation. Introduced
> the idea in the context of Calculus of Communicating
> Systems (CCS) in the late 1970s and early 1980s. Bisimulation
> became central to his work on concurrency theory. He won
> the Turing Award in 1991, partly for this work.
> 
> Gordon Plotkin
> While not the originator of bisimulation itself,
> Plotkin worked closely with Milner and contributed
> significantly to the theoretical foundations of
> operational semantics and domain theory, which
> intersect with bisimulation.
> 
> David Park
> Credited with influencing the notion of bisimulation.
> His unpublished manuscript (c. 1981) and personal
> communications inspired Milner’s formalization.
> He clarified the distinction between simulation
> and bisimulation.
> 
> Bye
> 

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

Thread

Fathers of Bisimulation: Robin Milner (1934–2010) Mild Shock <janburse@fastmail.fm> - 2025-07-21 14:28 +0200
  From Bisimulation to Bisimilarity: A Complete Inference System (Was: Fathers of Bisimulation: Robin Milner (1934–2010)) Mild Shock <janburse@fastmail.fm> - 2025-07-21 22:44 +0200
    Bonus: Prolog Systems with Strings, Bigints, etc.. (Re: From Bisimulation to Bisimilarity: A Complete Inference System) Mild Shock <janburse@fastmail.fm> - 2025-07-21 23:04 +0200
      At least 3 methods for Bisimilarity [Python BisPy] (Was: Bonus: Prolog Systems with Strings, Bigints, etc.. ) Mild Shock <janburse@fastmail.fm> - 2025-07-21 23:25 +0200
        sets or tuples? be warned (Re: At least 3 methods for Bisimilarity [Python BisPy]) Mild Shock <janburse@fastmail.fm> - 2025-07-21 23:36 +0200
  The Original Ganster (OG) of Bisimilarity are Hopcroft and Karp (1971) (Re: Fathers of Bisimulation: Robin Milner (1934–2010)) Mild Shock <janburse@fastmail.fm> - 2025-07-22 00:50 +0200
    All-in-One DAM-GT: Wuhan, Hopcroft and Attention (Was: The Original Ganster (OG) of Bisimilarity are Hopcroft and Karp (1971)) Mild Shock <janburse@fastmail.fm> - 2025-08-06 15:10 +0200

csiph-web