Dear Carsten,
thank you for the detail.
The benchmark set will be "Runtime_Complexity_Innermost_Rewriting".
Here, I would propose using only a subset of the existing benchmark set "Runtime_Complexity_Innermost_Rewriting".
This is due to a (rather strong) request of the TPDB organizer (me) to avoid clones.
In near future, TPDB and COPS (https://cops.uibk.ac.at/) might get a unified back-end. Then we should be able to tell what categories each benchmark is for. Please wait until then.
Best, Akihisa
This property can be checked syntactically. In version 11.2 of the TPDB, for 369 out of 663 TRSs, innermost and parallel-innermost rewriting from basic terms define the same relation. Thus, it is the remaining 294 TRSs where an analysis of parallel-innermost runtime complexity would be of specific interest.
The following paper describes specific techniques to approximate the runtime complexity function for parallel-innermost rewriting, both by lower bounds and by potentially tighter upper bounds than those given by innermost runtime complexity:
Thaïs Baudon, Carsten Fuhs, Laure Gonnord Analysing Parallel Complexity of Term Rewriting In Proc. LOPSTR 2022. To appear.
The final version of the paper is currently in preparation. An overview of the results is available in the following slide deck presented at the TeReSe workshop in Nijmegen on 8 June 2022:
https://jpn01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdeividrval...
This slide deck includes (on slide 10) also the syntactic check (and its proof idea) to detect TRSs where innermost and parallel-innermost rewriting from basic terms coincide.
I will also give a presentation about this proposal for a new category (and why it is interesting!) at the Workshop on Termination on 11/12 August 2022.
Best regards,
Carsten
On 20/06/2022 07:31, YAMADA, Akihisa wrote:
Dear all,
Salvador proposed a new category "TRS Conditional (Termination)" (previous "TRS Conditional" will be called "TRS Conditional (Operational Termination)"). The benchmark set will be the same "TRS_Conditional".
Carsten proposed "Runtime Complexity: TRS Parallel Innermost". The benchmark set will be "Runtime_Complexity_Innermost_Rewriting".
Thanks for the proposals!
... but in general, please post proposals to this list, so that potential future participants can know.
Best, Akihisa
On 6/17/2022 12:01 PM, YAMADA, Akihisa wrote:
Dear all,
the GitHub repository is ready for termCOMP 2022 registration: https://jpn01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com...
I hope the instruction there is clear enough. Please post questions on this list otherwise.
You can monitor the status of registration and run at https://jpn01.safelinks.protection.outlook.com/?url=http%3A%2F%2Ftermcomp.gi...
Best, Akihisa
Termtools mailing list -- termtools@lists.rwth-aachen.de To unsubscribe send an email to termtools-leave@lists.rwth-aachen.de
WARNING: This email originated from outside of Birkbeck. Do not click links or open attachments unless you recognise the sender. Under testing so any comments sg@dcs.bbk.ac.uk