[FOM] 332: Preferred Model

[Andrej Bauer]

On Fri, Jan 23, 2009 at 1:31 AM, Harvey Friedman
<friedman at math.ohio-state.edu> wrote:
> Let P be a presentation. Let P# be the least subset of NBS such that
>
> i. The elements of NBS in P are all in P#.
> ii. Suppose (x,y) is in P and z is in P#. Let w be the result of replacing
> exactly one occurrence of x as a substring in z, by y. Then w is in P#.

This is a special case of a semi-Thue system, which in turn is a
special case of Post canonical system, see
http://en.wikipedia.org/wiki/String_rewriting_system , and falls under
the more general topic of rewrite systems. It is a well studied
subject and I would not be surprised if investigations of the kind
suggested by prof. Friedman have already been conducted.

With kind regards,

Andrej Bauer