new categories for probabilistic term rewriting

[ffrohn]

We plan to introduce new categories for termination of probabilistic term rewriting. Please let us know what you think about the following proposal by the termCOMP SC.

Rewrite Strategy

The idea is to have two categories, one for innermost and one for full rewriting.

Valid Results

The tools can give the following answers:

1. MAYBE
2. AST
3. PAST
4. SAST
5. YES (meaning certain termination)

This reflects the current state of the art, since no tool can currently disprove (P/S)AST. We can allow other results in the future, if needed.

The reason for distinguishing PAST and SAST is that there are examples that are PAST and not SAST, and probably there will be techniques by next summer which prove PAST without proving SAST.

Scoring

The scoring should be as in the complexity categories: If k tools participate, then the tool with the best result gets k points, the tool with the second best result gets k-1 points, etc. Here, the order is:

MAYBE < AST < PAST < SAST < YES

Tools with the result MAYBE do not get any points.

Format

The format should be a variant of the ARI format (which should also be used for the other TRS categories in the future):

 PTRS ::= ( format PTRS ) fun* prule*
  fun ::= ( fun identifier number )
wterm ::= ( num term )
 dist ::= ( wterm+ )
prule ::= ( prule term dist )

Here is an example:

(format PTRS)
(fun 0 0)
(fun s 1)
(fun f 1)
(prule (f (s x))
       ((1 (f x))
        (1 (f (s (s x))))))

[J-C-Kassing]

A slightly belated response, but I'm looking forward to the introduction of probabilistic categories into the termination competition!
The introduction of two separate categories for innermost and full rewriting is a good idea in my opinion,
and the scoring is also fine overall, but I have the following two suggestions:

1. I think we should also award additional information on the asymptotic (expected) complexity. So giving a bound on the (expected) derivational complexity like O(n^2) should be better than just saying that there exists some bound (SAST)

2. Now the problem arises, that a given bound like O(n^2) and the output YES for certain termination is incomparable, and we have no linear order anymore. I propose that we should not award YES anything at all, since certain termination is independent of the probabilistic structure of the program, so that a tool with a good termination analysis for ordinary TRSs would always find the best result for such examples without analyzing probabilistic programs itself. This would also make the entry somewhat easier for new tools.

All in all, I propose the following scoring:

MAYBE < AST < PAST < SAST < POLY < O(n^Nat) < O(1)

where POLY, O(n^Nat), and O(1) is as in the complexity category and denotes the expected derivational complexity.

[ffrohn]

I'd like to uphold consistency with the non-probabilistic categories, where complexity and termination are separated.

Apart from that, I think that having one category for both, termination and complexity, makes it harder for new participants and tools with fewer developers / resources. Consider the (hypothetical) scenario that we had a joined category for (non-probabilistic) termination and derivational complexity. Then to catch up with the leading tools, competitors would have to be competitive for both termination and DC, but both require quite different techniques.

Would it make sense to have one category for AST only (which, like classical termination, is not about runtime at all), and a second one for expected runtime, where (in addition to the valid answers from the existing complexity categories) PAST and SAST are valid answers?

[J-C-Kassing]

Separating AST from a category for expected runtime would also be fine for me. However, I don't think that we should introduce too many new categories at once.

Then, I would rather stick with the simple scoring (MAYBE < AST < PAST < SAST < YES) and introduce more categories in the future.

[ffrohn]

Fine with me, but if we introduce a joined category for AST/PAST/SAST, I'm skeptical whether we can easily 'undo' this decision later. If team A is good at proving PAST/SAST and team B develops new techniques for proving polynomial bounds, then team A is likely to fight against a new complexity category that includes PAST/SAST (where it's bound to fail).

[AkihisaYamada]

How about holding that benchmarks are

• not (known to be) surely terminating for probabilistic termination, and
• (not known to be not) SAST in probabilistic complexity?

Then YES in probabilistic termination category doesn't count, and AST/PAST/SAST doesn't count in probabilistic complexity.

This is actually what I thought about (non-probabilistic) complexity categories, which contain nonterminating benchmarks. According to @DieterHofbauer at WST, a similar thing is happening in SRS Relative.

[juergengiesl]

Some comments on the questions discussed above:

• Separate categories for AST and for PAST/SAST are not a good idea in my opinion. The reason is that then tools that specialize in PAST would probably not compete in the AST-category and tools that specialize in AST cannot compete in the PAST/SAST-category. We should try to define categories which attract as many tools as possible.

• If we introduce a category with both AST and PAST/SAST now (but without O(n^k)), then there is no reason why we have to undo that when introducing an additional "complexity" category later on which has POLY and O(n^k). One would then simply keep on having a "termination" category (with AST, PAST, SAST) and an additional "complexity" category (with POLY and O(n^k).

• I think we could try to remove all examples that are surely terminating from the probabilistic categories. Then there is no need for a YES answer anymore.

[ffrohn]

Okay, so the original proposal, but without points for YES, seems to be okay for everybody, and we should try to keep surely terminating PTRSs out of the TPDB. Closed.

[ffrohn]

I'm currently looking at the code that computes the scoring.

The scoring should be as in the complexity categories: If k tools participate, then the tool with the best result gets k points, the tool with the second best result gets k-1 points, etc.

As far as I can tell, that's not the scoring that has been used in the past. That can also easily be seen from the fact that the scores weren't integral (see, e.g., here at the bottom of the page). Instead, the following scoring scheme has been used:

• 1+0.5^k points for O(n^k), i.e.,
  • 2 points for O(1)
  • 1.5 points for O(n)
  • 1.25 points for O(n^2)
  • ...
• 1-0.5^k points for Omega(n^k), i.e.,
  • 0 points for Omega(1)
  • 0.5 points for Omega(1)
  • 0.75 points for Omega(2)
  • ...
• 1 point for the lower bound NON_POLY

Presumably, all complexity categories are going to be demo categories anyway, and we'll have to re-implement everything next year as StarExec gets discontinued, so I'm not going to change that. However, that means that the score of one solver is currently independent of the scores of all others, and changing that would require major changes of the StarExec presenter. Hence, I'd like to propose a different scoring scheme:

AST: 1 point
PAST: 2 points
SAST: 3 points

Or, alternatively:

AST: 1 point
PAST: 1+c points
SAST: 1+2c points

for some positive constant c. Would that be okay for everyone? What should be the value of c?

[juergengiesl]

I think Akihisa means: If tool A and B both prove AST for a certain example in 2024, then they get 2 points. If they then both prove SAST for the same example in 2025, they again get 2 points. So the tools improve, but the score remains unchanged.

Yes, ok, if both tools improve in the same way, then nothing changes in the score. But why is that a problem? The score is meant to measure the tools against each other. If they are equally good, they should get equal score, but the exact number of this score is not very important, I think.

If we want, we can in the end increase the score of all tools by the same number which reflects the overall quality of the results of all tools, to measure the overall increase in quality.

Hmm, wouldn't the best possible result be "AST & not SAST" (I'll ignore PAST for now)? Then we could have:

• SAST: 1+c points
• not AST: 1+c points
• AST: 1 point
• not SAST: c points

So every example is worth 1+c points.

No tool can currently disprove AST or disprove SAST. As long as this doesn't change, I don't think that it makes sense to award points for disproving something. Thus, this suggestion would boil down to 1+c for SAST and 1 for AST, which has the drawbacks mentioned before.

[ffrohn]

No tool can currently disprove AST or disprove SAST. Therefore, I don't think that it makes sense to award points for disproving something.

But it doesn't hurt either, and by considering "not (S)AST" in the scoring scheme now, we avoid having the same discussion again in 2 or 3 years.

Thus, this suggestion would boil down to 1+c for SAST and 1 for AST, which has the drawbacks mentioned before.

Yes, but in my opinion, considering both sides of the problem (proving and disproving (S)AST) makes apparent that these drawbacks are in fact shortcomings of the tools, not the scoring scheme: The goal is to figure out whether a PTRS is (S)AST or not. For examples that are AST, but not SAST, the tools cannot give a comprehensive answer to that question. Hence, they cannot reach the maximal score.

[juergengiesl]

Disproving AST or SAST requires completely different techniques than proving AST or SAST. For that reason, no tool can disprove these properties up to now for PTRSs. This is similar to complexity analysis where finding lower bounds requires completely different techniques than finding upper bounds. I think that it was a bad idea to count these measures together in complexity analysis, as it makes it very hard to compete for tools that can only analyze one of these questions. This is one of the reasons why the complexity categories have almost no participants anymore.

We shouldn't do the same mistake again. So for that reason, I'm not in favor of counting these measures together for probabilistic termination. If one day there is a tool that can disprove one of these properties, it should still be attractive to participate for tools that can only prove (but not disprove) these properties. Therefore, I think that the scoring for proving probabilistic termination properties should be independent from the scoring for disproving them.

[ffrohn]

Disproving AST or SAST requires completely different techniques than proving AST or SAST.

That's true for non-probabilistic termination as well, but there the combined scoring appears to be okay for everyone.

I think that it was a bad idea to count these measures together in complexity analysis, as it makes it very hard to compete for tools that can only analyze one of these questions. This is one of the reasons why the complexity categories have almost no participants anymore.

Then we should change the scoring for complexity, and try to attract new (and old) participants again.

Anyways, as the PTRS categories are going to be demo categories this year, we don't have to fix a scoring scheme at all. I shouldn't have brought it up, but I didn't expect it to be that controversial.

[AkihisaYamada]

Actually what I meant is when there is only "tool A". With my scoring you could have shown that you improve here
The old scoring would have made only a few points difference (for those which was previously MAYBE).

[ffrohn]

The current format for PTRSs is slightly different from the proposal above. The reason is that @J-C-Kassing and I agreed that specifying the probabilities with :prob k instead of just a number is more readable, and consistent with other categories (where we have, e.g., :cost, :guard, etc.). However, now @AkihisaYamada pointed out that

(t :prob k)

corresponds to passing an argument called prob with value k to t in LISP, which is not what we want to express. What about

prule ::= ( prule term dist cost? )
cost ::= :cost number
dist ::= ( ( pterm term prob? )* )
prob ::= :prob number

so that we'd have (pterm t :prob k) instead?

[AkihisaYamada]

(partly repost) In the original proposal, one could say that the second argument of prule is a list of pairs.
(Making prule variadic: (prule l (p_1 r_1) ... (p_n r_n)) would be very fine.)

[AkihisaYamada]

To me, prule is enough to tell that a distribution is expected. So :prob looks redundant.

It would be great if one could encode a prule as rule with annotations, but I cannot think of a sensible solution in this direction.