Difference between revisions of "Termination Competition"
(Added links to some defined categories) |
|||
| (78 intermediate revisions by 9 users not shown) | |||
| Line 2: | Line 2: | ||
During the 90's a number of new, powerful termination methods | During the 90's a number of new, powerful termination methods | ||
| − | was developed. Thus, at | + | was developed. Thus, at the beginning of the millennium |
many research groups started to develop [[:Category:Tools | tools for fully-automated termination analysis]]. | many research groups started to develop [[:Category:Tools | tools for fully-automated termination analysis]]. | ||
| − | After a tool demonstration at the 2003 | + | After a tool demonstration at the Termination Workshop 2003 (Valencia), |
| − | the community decided to install an annual termination competition | + | the community then decided to install an annual termination competition, and to collect benchmarks, |
to spur the development of tools and new termination techniques. | to spur the development of tools and new termination techniques. | ||
| − | + | == Upcoming Competitions == | |
| − | + | ||
| + | * The [[Termination Competition 2025]] will be held during [https://www.imn.htwk-leipzig.de/WST2025/ WST 2025], September 3-4, Leipzig, Germany. | ||
| + | |||
| + | == Competition Categories == | ||
| + | |||
| + | Currently, the competition features the following categories. Since 2007 some of the categories also have [[Certified_Termination|certified categories]], where an additional certifier checks the output of the tools. Categories that were used in the past but not included in the three most recent competitions are marked with an <span style="color:red;">✖</span>. | ||
| + | |||
| + | === Termination of Rewriting === | ||
| − | == | + | These categories consider the termination of <b>rewrite systems</b>, a foundational computational model used to represent symbolic computation and program transformations. |
| + | The goal is to automatically prove that no infinite rewrite sequences are possible for the given system. | ||
| + | Different categories capture variations of rewriting such as relative rewriting, context-sensitive rewriting, conditional rules, or restrictions on the rewriting strategy (e.g., innermost or outermost rewriting). | ||
| + | |||
| + | <div style="column-count:3; column-gap:2em;"> | ||
| + | * [[TRS Standard|TRS Standard]] | ||
| + | * [[TRS Relative|TRS Relative]] | ||
| + | * [[Term Rewriting#TRS Contextsensitive|TRS Contextsensitive]] | ||
| + | * [[Term Rewriting#TRS Equational|TRS Equational]] | ||
| + | * [[TRS Innermost|TRS Innermost]] | ||
| + | * [[TRS Outermost|TRS Outermost]] | ||
| + | * [[Term Rewriting#TRS Conditional|TRS Conditional]] | ||
| + | * [[Term Rewriting#TRS Conditional - Operational Termination|TRS Conditional - Operational Termination]] | ||
| + | * [[SRS Standard|SRS Standard]] | ||
| + | * [[SRS Relative|SRS Relative]] | ||
| + | * [[Cycle_Rewriting|Cycle Rewriting]] <span style="color:red;">✖</span> | ||
| + | * [[Higher_Order|Higher Order Rewriting]] (since 2010) | ||
| + | * [[ITRS|ITRS Innermost]] (since 2014) | ||
| + | * [[Term Rewriting#Integer Transition Systems|ITS]] (since 2014) | ||
| + | </div> | ||
| + | |||
| + | === Termination of Probabilistic Rewriting === | ||
| + | |||
| + | These categories address <b> probabilistic rewrite systems </b>, where rewrite rules are applied according to probability distributions. | ||
| + | Instead of classical termination, the goal is to prove almost-sure termination, i.e., that infinite executions occur with probability zero, | ||
| + | or strong almost-sure termination, i.e., that the expected runtime is finite. | ||
| + | This lifts termination analysis to models that capture randomized algorithms or stochastic behavior. | ||
| + | |||
| + | <div style="column-count:3; column-gap:2em;"> | ||
| + | * [[PTRS Standard|PTRS Standard]] | ||
| + | * [[PTRS Innermost|PTRS Innermost]] | ||
| + | </div> | ||
| + | |||
| + | Currently, there are only categories regarding probabilistic rewrite systems, | ||
| + | but an extension to probabilistic imperative programs may be possible in future competitions. | ||
| + | |||
| + | === Termination of Programs === | ||
| + | |||
| + | These categories focus on proving termination of <b> actual programming languages </b> used in industry. | ||
| + | The categories differ by the source programming language or program model. | ||
| + | |||
| + | <div style="column-count:3; column-gap:2em;"> | ||
| + | * [[Logic_Programming|Termination of logic programs]] | ||
| + | * [[Functional_Programming|Termination of functional programs]] (since 2007) | ||
| + | * [[Java_Bytecode|Termination of Java Bytecode programs]] (since 2009) | ||
| + | * [[C_Programs|Termination of C programs]] (since 2014) | ||
| + | </div> | ||
| + | |||
| + | === Complexity of Rewriting === | ||
| − | + | These categories evaluate tools that automatically analyze the <b> asymptotic complexity of rewrite systems </b>. | |
| + | Instead of only proving termination, the goal is to derive upper bounds on the length of rewrite sequences, | ||
| + | typically expressed as functions of the input size. | ||
| + | Different categories measure difference runtime complexities under various rewriting strategies and different restrictions on the initial start term. | ||
| − | + | <div style="column-count:3; column-gap:2em;"> | |
| + | * [[Term Rewriting#Runtime Complexity|TRS Runtime Complexity]] | ||
| + | * [[Term Rewriting#Runtime Complexity|TRS Innermost Runtime Complexity]] | ||
| + | * [[Term Rewriting#Runtime Complexity|TRS Derivational Complexity]] | ||
| + | * [[Term Rewriting#Runtime Complexity|TRS Innermost Derivational Complexity]] | ||
| + | * TRS Parallel Innermost Derivational Complexity | ||
| + | * [[Term Rewriting#Integer Transition Systems|ITS Complexity]] | ||
| + | </div> | ||
| − | == | + | === Complexity Analysis === |
| − | + | These categories focus on automatically determining <b> time complexity bounds for programs written in concrete programming languages </b>. | |
| − | + | Tools analyze the program’s control flow, data dependencies, and loops to derive asymptotic upper bounds on runtime with respect to the input size. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | <div style="column-count:3; column-gap:2em;"> | |
| − | + | * [[C_Complexity|Complexity of C programs]] | |
| + | </div> | ||
| − | == | + | == Competition Benchmarks == |
The [[TPDB|Termination Problems Data Base]] collects all the problems used in the competitions. | The [[TPDB|Termination Problems Data Base]] collects all the problems used in the competitions. | ||
| Line 40: | Line 98: | ||
We welcome problem submissions from non-participants. | We welcome problem submissions from non-participants. | ||
| − | == | + | == Organization == |
| − | + | Questions and suggestions regarding the competition | |
| + | should go to [[Termtools|the termtools mailing list]]. | ||
| + | Discussion is open and happens primarily on the list. | ||
| + | Decisions will be made by votes among the [[Termination Competition Steering Committee]], with current members | ||
| + | * [https://ffrohn.github.io Florian Frohn] (Chair), RWTH Aachen | ||
| + | * [https://verify.rwth-aachen.de/giesl/ Jürgen Giesl], RWTH Aachen | ||
| + | * [http://cl-informatik.uibk.ac.at/users/georg/ Georg Moser], University of Innsbruck | ||
| + | * [http://lim.univ-reunion.fr/staff/epayet/ Étienne Payet], Université de La Réunion | ||
| + | * [https://group-mmm.org/~ayamada/ Akihisa Yamada], AIST Tokyo Waterfront | ||
| + | * Dieter Hofbauer, ASW Saarland | ||
| − | + | From 2004 till 2007, the competition organizer was Claude Marché, [http://www.lri.fr/~marche/termination-competition/ Paris]. | |
| + | From 2008 to 2013 the competition was run by René Thiemann, [http://termcomp.uibk.ac.at Innsbruck]. | ||
| + | From 2014 to 2017, the competition organizer was Johannes Waldmann. Jobs were run on the [https://www.starexec.org/ Star Exec] platform at U Iowa. | ||
| + | From 2018 to 2023, the organizer was Akihisa Yamada. | ||
| + | From 2024 on, the organizer is Florian Frohn. | ||
| − | + | == History of Termination Competitions == | |
| − | + | A list of all competitions that have been taken place can be found [[Termination Competition History|here]]. | |
| − | + | ==== Results ==== | |
| − | + | The results of (almost) all competitions are available [https://termcomp.github.io/ here] | |
| − | |||
| − | |||
| − | |||
| − | |||
Latest revision as of 10:03, 11 March 2026
Contents
Annual International Termination Competition
During the 90's a number of new, powerful termination methods was developed. Thus, at the beginning of the millennium many research groups started to develop tools for fully-automated termination analysis.
After a tool demonstration at the Termination Workshop 2003 (Valencia), the community then decided to install an annual termination competition, and to collect benchmarks, to spur the development of tools and new termination techniques.
Upcoming Competitions
- The Termination Competition 2025 will be held during WST 2025, September 3-4, Leipzig, Germany.
Competition Categories
Currently, the competition features the following categories. Since 2007 some of the categories also have certified categories, where an additional certifier checks the output of the tools. Categories that were used in the past but not included in the three most recent competitions are marked with an ✖.
Termination of Rewriting
These categories consider the termination of rewrite systems, a foundational computational model used to represent symbolic computation and program transformations. The goal is to automatically prove that no infinite rewrite sequences are possible for the given system. Different categories capture variations of rewriting such as relative rewriting, context-sensitive rewriting, conditional rules, or restrictions on the rewriting strategy (e.g., innermost or outermost rewriting).
Termination of Probabilistic Rewriting
These categories address probabilistic rewrite systems , where rewrite rules are applied according to probability distributions. Instead of classical termination, the goal is to prove almost-sure termination, i.e., that infinite executions occur with probability zero, or strong almost-sure termination, i.e., that the expected runtime is finite. This lifts termination analysis to models that capture randomized algorithms or stochastic behavior.
Currently, there are only categories regarding probabilistic rewrite systems, but an extension to probabilistic imperative programs may be possible in future competitions.
Termination of Programs
These categories focus on proving termination of actual programming languages used in industry. The categories differ by the source programming language or program model.
- Termination of logic programs
- Termination of functional programs (since 2007)
- Termination of Java Bytecode programs (since 2009)
- Termination of C programs (since 2014)
Complexity of Rewriting
These categories evaluate tools that automatically analyze the asymptotic complexity of rewrite systems . Instead of only proving termination, the goal is to derive upper bounds on the length of rewrite sequences, typically expressed as functions of the input size. Different categories measure difference runtime complexities under various rewriting strategies and different restrictions on the initial start term.
- TRS Runtime Complexity
- TRS Innermost Runtime Complexity
- TRS Derivational Complexity
- TRS Innermost Derivational Complexity
- TRS Parallel Innermost Derivational Complexity
- ITS Complexity
Complexity Analysis
These categories focus on automatically determining time complexity bounds for programs written in concrete programming languages . Tools analyze the program’s control flow, data dependencies, and loops to derive asymptotic upper bounds on runtime with respect to the input size.
Competition Benchmarks
The Termination Problems Data Base collects all the problems used in the competitions.
We welcome problem submissions from non-participants.
Organization
Questions and suggestions regarding the competition should go to the termtools mailing list. Discussion is open and happens primarily on the list. Decisions will be made by votes among the Termination Competition Steering Committee, with current members
- Florian Frohn (Chair), RWTH Aachen
- Jürgen Giesl, RWTH Aachen
- Georg Moser, University of Innsbruck
- Étienne Payet, Université de La Réunion
- Akihisa Yamada, AIST Tokyo Waterfront
- Dieter Hofbauer, ASW Saarland
From 2004 till 2007, the competition organizer was Claude Marché, Paris. From 2008 to 2013 the competition was run by René Thiemann, Innsbruck. From 2014 to 2017, the competition organizer was Johannes Waldmann. Jobs were run on the Star Exec platform at U Iowa. From 2018 to 2023, the organizer was Akihisa Yamada. From 2024 on, the organizer is Florian Frohn.
History of Termination Competitions
A list of all competitions that have been taken place can be found here.
Results
The results of (almost) all competitions are available here
