Newsgroups: comp.theory
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!andrews
From: andrews@cs.ubc.ca (Jamie Andrews)
Subject: Term/tree-rewriting systems with monoidal subsystems?
Message-ID: <1991May21.213311.12104@cs.ubc.ca>
Sender: usenet@cs.ubc.ca (Usenet News)
Organization: University of British Columbia, Vancouver, B.C., Canada
Date: Tue, 21 May 91 21:33:11 GMT

     Has anyone done any work on term- or tree-rewriting systems
which have monoidal subsystems?  What I mean is, a system in
which we have a binary function symbol "concat" and a nullary
function symbol "null", and in which the following rewrites and
their inverses are possible:

concat(concat(X, Y), Z) => concat(X, concat(Y, Z))
concat(null, X) => X
concat(X, null) => X

     Have there been efficient algorithms developed for the
"rewrites to" relation for such systems?  (I assume the
consequences for general algorithms would be pretty severe.)
What are the consequences for the theoretical basis of the
systems?  (That is, are some important theorems easier, harder,
impossible to prove?)

     Please respond by e-mail if you can.  Thanks.

     The application I have in mind is to logic grammars.

--Jamie.
  andrews@cs.ubc.ca