Adapting the ARI format for relative rewriting & complexity

[ffrohn]

Since we want to use the ARI format in the future, we have to extend it for relative rewriting. The idea is to use the format for multiple TRSs, with the restriction that there have to be precisely two TRSs. Then the goal is to prove termination of TRS 1 relative to TRS 2.

What do you think?

Edit (24/01/16): Taking the discussion into account, the following proposal seems to be better:

RTRS ::= ( format RTRS ) fun* rule*
 fun ::= ( fun identifier number )
rule ::= ( rule term term cost? )
cost ::= ( :cost number )

Note that number only allows for non-negative numbers in ARI. For termination, it only matters whether the costs are zero or not. For complexity, the costs only matter for concrete (non-asymptotic) bounds.

I'm not sure if RTRS (relative TRS) is a good name, though. We could also go for, e.g., WTRS (weighted TRS).

[stefandollase]

I think this is a good suggestion when only considering the cost 0 and 1. However, I would be interested in having a format that uses an arithmetic term as the cost (and also a condition). In this way, relative TRSs, ITSs and ITRSs can use the same format. Of course one could do it in a separate format, but then again one would run into the situation that was already described here, i.e., if the ITRS is incidentally a relative TRS, then one has to encode the ITRS in a specialized relative rewriting format, so it can be understood by tools that can only handle relative rewriting but no ITRSs.

[ffrohn]

If several people are interested in cost-annotations, why not? But now we're only talking about the complexity categories, not about termination of relative rewriting, right? And we're only talking about non-negative costs, correct?

[AkihisaYamada]

Ah, I was speaking about termination. Do relative rules appear already in complexity categories? Then I think cost-annotation is clearer for them. And I'd use the same format both for termination and complexity.

[ffrohn]

Yes, relative rules are allowed in the complexity categories. But what's the purpose of cost-annotations for termination?

[stefandollase]

Indeed, I am only interested in non-negative costs.

But now we're only talking about the complexity categories, not about termination of relative rewriting, right?

I don't understand the question. Shouldn't the language to describe a rewrite system be independent of the analysis goal, especially if we separate these two parts to reuse rewrite systems with different analysis goals? One could also analyze an ITRS with non-constant cost terms for termination, where not only a normal form, but also an infinite sequence with only a finite number of non-0-cost steps is considered terminating.

[ffrohn]

Yes, we should have a uniform format. I'm just trying to understand where the motivation for cost-annotations is coming from.

[AkihisaYamada]

But what's the purpose of cost-annotations for termination?

No, for termination, only :cost 0 make difference.

[stefandollase]

Couldn't the 0 also be the result of evaluating a cost-term?

[ffrohn]

I think we are discussing two different things here:

Stefan is mainly interested in complexity of ITRSs with non-constant cost-expressions.

Akihisa is interested in relative TRSs with constant cost-annotations.

@stefandollase I understand your motivation -- you want to have a format for relative TRSs which is a special case of ITRSs. However, there are two problems that need to be resolved first, in my opinion:

• there is no proposal for an ARI format for ITRSs
• there is no complexity category for ITRSs

@AkihisaYamada I don't fully understand your motivation yet, as you said that

1. you're "very interested in cost-annotated rewriting",
2. you're "speaking about termination", and
3. "for termination, only :cost 0 make difference."

For me, the last statement implies that cost-annotations are not very relevant for termination, but the first two seem to imply that you are very interested in termination of cost-annotated rewriting. What am I getting wrong?

[stefandollase]

However, there are two problems that need to be resolved first, in my opinion:

• there is no proposal for an ARI format for ITRSs
• there is no complexity category for ITRSs

Indeed, these are still open issues. However, I want to ensure that in the future it will be possible to define an ARI ITRS format that is a generalization of the relative TRS format, i.e., that allows for cost terms. Having two separate TRSs for relative TRSs would not be helpful for that.

[stefandollase]

Would it be important to specify the ITRS format now?

[ffrohn]

I don't think so, it has been a demo category for a while and, as far as I'm aware, nobody is actively working on termination tools for ITRSs. So I think we can postpone that until there are new tools / techniques.

[cfuhs]

ITRSs are de facto a special case of LCTRSs, for which ARI has a dedicated format. To avoid a proliferation of different formats, it could be good to use this LCTRS format also for ITRSs. Termination analysis of LCTRSs is supported, e.g., by the tool Ctrl, and there is active work on the tools Cora and Crisys2.

[ffrohn]

Let's move this to a separate discussion.

[ffrohn]

I updated the proposal to take the discussion into account.

[stefandollase]

Thanks! I like the new suggestion. In the future for ITRSs, we could then allow cost-terms instead of just constant numbers for the cost.

[ffrohn]

Everybody seems to be happy with the updated proposal --> closed.