|
|
| (92 intermediate revisions by 8 users not shown) |
| Line 1: |
Line 1: |
| This page is to record the current status of discussion | | <pre> |
| on the proposed Complexity Category of the Termination Competition.
| | This page is no longer maintained. |
| | </pre> |
|
| |
|
| (Discussion should take place on the termtools mailing list.)
| | The entry point to the complexity category is here: [http://cl-informatik.uibk.ac.at/users/georg/cbr/competition/ complexity competition]. |
| | |
| == Overview of the Event ==
| |
| | |
| It is a challenging topic to automatically determine upper bounds on
| |
| the complexity of rewrite systems. By complexity of a TRS, we mean | |
| the maximal length of derivations, where either no restrictions on the
| |
| initial terms are present ("derivational complexity") or only
| |
| constructor based terms are considered ("runtime complexity"). See
| |
| (Hirokawa, Moser, 2008) for further reading on the notion of runtime
| |
| complexity. Additionally one distinguishes between complexities
| |
| induced by full rewriting as opposed to complexities induced by
| |
| specific strategies, as for example innermost rewriting.
| |
| | |
| | |
| == Syntax/Semantics for Input/Output ==
| |
| | |
| (to be extended)
| |
| | |
| == Scoring ==
| |
| | |
| (to be extended)
| |
| | |
| == Problem selection ==
| |
| | |
| (to be extended)
| |
| | |
| == Participation ==
| |
| | |
| (to be extended)
| |
| | |
| == Wishlist ==
| |
| | |
| (to be extended)
| |
| | |
| == Questions ==
| |
| | |
| issues with the rules proposal that need to be clarified, or voted upon.
| |
| | |
| == Participants ==
| |
| | |
| insert your name here if you intend to participate
| |
| | |
| *
| |
| * Johannes Waldmann (Matchbox), but will need more time (December 2008)
| |
| * M. Avanzini, G. Moser, A. Schnabl (TCT)
| |
This page is no longer maintained.
The entry point to the complexity category is here: complexity competition.
