Rewriting

One research direction to consider is rewriting systems with orbit-finite sets of rules. There is a nice application to knot theory.

 Yesterday I saw a talk by Igor Potapov (I will post a link to Igor’s slides when they are available, a paper is here), which contains an interesting application to knot theory. Namely, there exist

  • A representation of knots by words over the alphabet A =\{\mathrm{over, under}\} \times atoms. This representation is called Gauss word, every word in A^* represents (not necessarily uniquely) some knot.
  • A rewriting system.  The rewriting rules correspond to Reidemeister moves.

such that  two words w,v \in A^* represent equivalent knots if and only if one can rewrite w into v using the rewriting rules.

This motivates the study of orbit-finite rewriting problems.  Given

  • an orbit-finite set R of rewriting rules (pairs of words) ;
  • a source word w and a target word v;

consider the following problems:

Infix rewriting. Can one go from w to v by doing a finite number of steps where in each step, one replaces an infix x by a word y such that (x,y) \in R?

Prefix rewriting. The same as above, but only with prefixes.

Infix rewriting is undecidable already for finite alphabets, but maybe there are some restrictions which are decidable for orbit-finite alphabets. (One restriction that works for orbit-finite alphabets is that the system is commutative, i.e. it contains a rule (ab,ba) for every two letters a,b of the alphabet. This corresponds to Petri nets for finite alphabets, and for infinite alphabets it corresponds to some data variant of Petri nets.)

It seems likely that prefix rewriting is decidable. For finite alphabets, the set of words reachable from the source is regular. (This is essentially the set of reachable stack configurations of a pushdown automaton.) It seems to me that for orbit-finite alphabets, the set should be recognized by a nondeterministic orbit-finite automaton.

The rewriting system that is used in knot theory is even more general than infix rewriting, on the other hand it is one specific rewriting system. It might be the case that for every source word, the set of reachable word might be recognized by some kind of automaton.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>