4
$\begingroup$

I found a seminal paper of renowned authors (Inference of Finite Automata Using Homing Sequences (1993) by Ron Rivest and Robert Schapire) in which the authors define the very same set-theoretic concept twice but giving it two different names:

Information and Computation 103, 299-347 (1993)

p. 303:

enter image description here

p. 307:

enter image description here

Usually this is bad habit: defining the very same (set theoretic) concept twice but giving it two different names, especially in one single paper.

But the authors did, and they were aware of it:

enter image description here

My first question:

Why do they say "the structures appear to be quite similar" when they are obviously just identical?

What makes the difference - so the authors claim - is the interpretation:

enter image description here

On first blush, this is unsatisfactory. The difference in terms of interpretation seems deep and it seems to be possible to make it more explicit (e.g. in terms of model theory). It should not be left left to the reader to make it by "mental interpretation".

My second question thus is:

Did the authors probably (and correctly) assume that the reader interprets "interpretation" in the model theoretic sense and "fills in the gaps"?

How could/should the authors have made it better?

Improve this question
$\endgroup$
10
  • 8
    $\begingroup$ I am not a computer scientist, but my (likely faulty) outsider's understanding is that interpretation is very important, and that much progress gets made when it is recognized that very different "objects" (meaning in particular different interpretations) are modeled by the same mathematics. In physics this is also true. $\endgroup$
    – Theo Johnson-Freyd
    Commented Oct 17, 2016 at 14:51
  • 1
    $\begingroup$ But should not equal effort (in terms of formal precision) be made to distinguish the (different) intended interpretations compared to make the (identical) set-theoretic concept precise? (There seems to me some imbalance.) $\endgroup$
    – Hans-Peter Stricker
    Commented Oct 17, 2016 at 15:56
  • 1
    $\begingroup$ @Theo: My question is not about the importance of interpretation. And it is also clear to me that very different structures can be modeled by the same mathematics. My question is about how to reflect this. $\endgroup$
    – Hans-Peter Stricker
    Commented Oct 17, 2016 at 17:11
  • 1
    $\begingroup$ And further (in your lines): why and which progress gets made by recognizing that different structures can be modeled by the same mathematics. $\endgroup$
    – Hans-Peter Stricker
    Commented Oct 17, 2016 at 17:13
  • 6
    $\begingroup$ I would say that these are two concepts, as explained by the authors, which just have identical or rather isomorphic implementations. Names and interpretations matter. Another example which comes to my mind is the definition of a combinatorial game as a (well-founded) set. The interpretation is that the elements of this set are the options of the game, which are games themselves again. I hope that we all agree that the concept of a combinatorial game is different from the concept of a set, though! $\endgroup$
    – HeinrichD
    Commented Oct 17, 2016 at 19:27

1 Answer 1

Reset to default
3
$\begingroup$

First, I agree with the commenters in not understanding your objection to giving different names to the same mathematical objects if they are used to model different phenomena. The terms "position" and "velocity" can both refer to vectors in $\mathbb{R}^3$, but this doesn't imply that using both terms is bad habit or that there are modeling gaps that need filling in.

When modeling some phenomenon, it's important to distinguish between the mathematical structure of a thing and the meaning given to this structure. (For example, in CS we often refer informally to the need for both syntax and semantics.)

One good example is the pair $G = (V,E)$ where $V$ is a finite set and $E \subseteq V \times V$. We often interpret this structure as a "connectivity graph" where $(u,v) \in E$ has the semantic meaning "there is an edge from $u$ to $v$" and it makes sense to ask the question "Is there any path from $s$ to $t$?" where a path is a sequence of pairs $((u_1,v_1), \cdots, (u_n,v_n))$ where $v_i = u_{i+1} ~ (\forall 1 \leq i M n)$ and each $(u_i,v_i) \in E$.

On the other hand we can also use $G$ as a model of eligible partners where $(u,v) \in E$ has the semantic meaning "$u$ can be assigned as a partner to $v$" and a reasonable question is "what is the largest matching in $G$?" where a matching is an $M \subseteq E$ where $(u_1,u_2),(u_3,u_4) \in M \implies u_i \neq u_j (\forall i < j)$.

Of course, you could technically ask the path question in the second example or the matching question in the first example, but it wouldn't make much sense, nor does restricting ourselves to only one interpretation of the formalism $G = (V,E)$.

More concretely, it sounds like you might want to check their prior work for more explanation, as they say (p302):

enter image description here

See the bottom of p304 and top of p305 for a reiteration of this point.

So it looks like to me that what's happening is that the same phenomenon -- i.e. a robot with a set of things it can sense and actions it can take -- is being modeled two different ways. These two ways have the same formalism but different meanings. The first, state-based way, explicitly tracks all possible states the world might be in, the set $Q$. The second, "diversity-based" way tracks the number of equivalence classes of "tests" that produce different results for the robot; this is modeled by $V$.

Importantly, a particular state-based representation (your first definition) models the same phenomenon as a particular diversity-based representation (your second definition), but the mapping between these is NOT the identity!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .