What's the definition of a TRS / SRS?

[ffrohn]

Important point, apart form syntax discussions: What's the definition of a SRS or TRS? I hope we do agree that an SRS is a set of rules, and a rule is a a pair of arbitrary strings. Similarly, a TRS is a set of rules, and a rule is a pair of arbitrary terms. PLEASE do not stick to the definition in Baader/Nipkow and the like. This makes rewrite systems much nicer mathematical objects; e. g., the inverse of a rewrite system is again a rewrite system. So as a left hand side, we should allow an empty string for SRS, similarly a single variable for TRS. Also for relative termination, this makes relevant statements possible in the first place (example: a a -> a b a is terminating relative to epsilon -> b).

For TRS also extra variables in right hand sides should be possible, for the same reason (nicer mathematical objects). (Question: What is the induced rewrite relation? Answer: Instantiate variables by arbitrary terms.) This was allowed before (e. g., in Transformed_CSR_04/PEANO_nosorts-noand_L), so please keep it this way.

Quoting Büchi (1989): "You will ask, why include the monsters? I give you three reasons: 1) A nice theorem may go through for [the] general [definition]; monsters share some important properties with the good boys. 2) Monsters are useful as counterexamples to happy conjectures; they serve to sharpen one's idea about the real things. 3) What looks like a monster to one person may be a useful member of society to the other. The other (he may be you at a later date) may have deeper thoughts on the matter, and may be right!"

Originally posted by @DieterHofbauer in #87 (reply in thread)

[DieterHofbauer]

Just to avoid misunderstandings: This issue no longer appears to be controversial, referring to more recent papers. Quoting Aart: "A rewrite rule is a pair of terms (\ell, r). We do not impose the common variable conditions, i.e., the restriction that \ell is not a variable and all variables in r are contained in \ell." The only point is that the future format shouldn't spoil it.

[jwaldmann]

yesyesyes fully agree.

[AkihisaYamada]

I also agree.

(Question: What is the induced rewrite relation? Answer: Instantiate variables by arbitrary terms.)

I would even say it doesn't matter the format. It's up to competition categories, e.g. a "TRS call-by-value" category would fully make sense of extra variables.

A problem is that the format tag invoke different indications to different people...

[ffrohn]

Everybody seems to agree --> closed.