Difference between revisions of "Complexity:Old"
Georg.moser (talk | contribs) |
Georg.moser (talk | contribs) |
||
| Line 4: | Line 4: | ||
(Discussion should take place on the termtools mailing list.) | (Discussion should take place on the termtools mailing list.) | ||
| − | == | + | == 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 == | == Questions == | ||
Revision as of 12:18, 20 October 2008
This page is to record the current status of discussion on the proposed Complexity Category of the Termination Competition.
(Discussion should take place on the termtools mailing list.)
Contents
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)
