Re: Distance in Denotational Semantics?

nobrow@xxxxxxxxx wrote:
> Is there a notion of distance in denotational semeantics? I have made
> cursory readings on the subject in the past, and all the talk of
> lattices and CPOs made me wonder if it was possible to define a
> semantic distance between two arbitary programs ... with the intention
> of using a distance d to define a region of similarity for a given
> program P (you know, P is considered similar to Q if |P Q| < d). Its a
> very vague question I know, but your feedback would be appreciated.
>
> Thanks.
>
> PS If theres a better place to post general question about den. sem.
> then please tell me.
>
If you want to argue about the behaviour abstractly, then you have to
compare the functions
f: omega -> omega union {divergence}
g: omega -> omega union {divergence}
as sets of pairs (or simply as two sequences indexed by omega) by some
distance on the set of functions. Here, P computes f and Q computes g.

If you want to argue about the textual form of the programs, construct
some distance function on finite texts modulo whitespace, variable
renaming, procedure calls, whiles (e.g transform everything to program
with gotos and ifs only. or to lambda-calculus and compare P them as
graphs in de-bruin form).

If you want to argue about transition systems, construct the process X
which branches nondeterministically to the P'=bisimulation quotient of P
and Q'=bisimulation quotient of Q and compute the bisimulation quotient
X' of X. You can consider states with different variable valuations as
different, for example. Then work with something like (2|X'|-|X|)/|X|.

Everyhting IMHO.
.

Relevant Pages

  • Re: distance function, convex domain
    ... Here dis the distance from x to the boundary of Omega. ... I think if Omega convex we have>=0. ...
    (sci.math)
  • Re: error correcting/detecting code question
    ... Bart Vandewoestyne wrote: ... where d is the distance of the code. ... to detect s errors and at the same time correct t errors is ... time one can argue by Fact 2 that 2 errors can be corrected. ...
    (sci.crypt)
  • Re: Video Exposes Forest Service Propaganda about Rainbow Gathering
    ... Don't engage with the cops, argue with them, or call things out to them. ... be aware of the distance you maintain. ... Watch for non-verbal cues as ... the other eye on them keeping an eye on you. ...
    (alt.gathering.rainbow)
  • Re: Consciousness created
    ... Rushtown wrote: ... One might argue that it still would be because of my sense of touch. ... Color, depth, distance, solidness, temperture are only there because ... I have the senses to consciously experience them. ...
    (sci.physics)
  • Re: Speed gedanken time (repaired) time dilation 099
    ... |> used a physical device to measure it. ... |> a distance = a distance per time. ... | Not something I've tried to argue - don't change the subject, ... I merely hopped in the train you started to move upon. ...
    (sci.physics)