Difference between revisions of "Termination Competition"
From Termination-Portal.org
Jump to navigationJump to search (→History of Termination Competitions: new url for 2018 competition) |
(Improved the categorization of all competition categories) |
||
| (25 intermediate revisions by 5 users not shown) | |||
| Line 8: | Line 8: | ||
the community then decided to install an annual termination competition, and to collect benchmarks, | 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. | ||
| + | |||
| + | == 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 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 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 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 on, the organizer is | + | From 2018 to 2023, the organizer was Akihisa Yamada. |
| + | From 2024 on, the organizer is Florian Frohn. | ||
| + | |||
| + | == 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 ouput 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 === |
| + | |||
| + | <div style="column-count:3; column-gap:2em;"> | ||
| + | * [[Term Rewriting#TRS Standard|TRS Standard]] | ||
| + | * [[Term Rewriting#TRS Relative|TRS Relative]] | ||
| + | * [[Term Rewriting#TRS Contextsensitive|TRS Contextsensitive]] | ||
| + | * [[Term Rewriting#TRS Equational|TRS Equational]] | ||
| + | * [[Term Rewriting#TRS Innermost|TRS Innermost]] | ||
| + | * [[Term Rewriting#TRS Outermost|TRS Outermost]] | ||
| + | * [[Term Rewriting#TRS Conditional|TRS Conditional]] | ||
| + | * [[Term Rewriting#TRS Conditional - Operational Termination|TRS Conditional - Operational Termination]] | ||
| + | * [[Term Rewriting#SRS Standard|SRS Standard]] | ||
| + | * [[Term Rewriting#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 === | ||
| − | * [[ | + | <div style="column-count:3; column-gap:2em;"> |
| + | * [[Probabilistic Rewriting#PTRS Standard|PTRS Standard]] (since 2024) | ||
| + | * [[Probabilistic Rewriting#PTRS Innermost|PTRS Innermost]] (since 2024) | ||
| + | </div> | ||
| − | == | + | === Termination of Programs === |
| − | + | <div style="column-count:3; column-gap:2em;"> | |
| − | |||
* [[Logic_Programming|termination of logic programs]] | * [[Logic_Programming|termination of logic programs]] | ||
| − | |||
* [[Functional_Programming|termination of functional programs]] (since 2007) | * [[Functional_Programming|termination of functional programs]] (since 2007) | ||
| − | |||
* [[Java_Bytecode|termination of Java Bytecode programs]] (since 2009) | * [[Java_Bytecode|termination of Java Bytecode programs]] (since 2009) | ||
| − | |||
* [[C_Programs|termination of C programs]] (since 2014) | * [[C_Programs|termination of C programs]] (since 2014) | ||
| − | + | </div> | |
| − | + | ||
| − | + | === Complexity of Rewriting === | |
| − | |||
| + | <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 === | |
| − | + | ||
| − | + | <div style="column-count:3; column-gap:2em;"> | |
| − | * [ | + | * [[C_Complexity|Complexity of C programs]] |
| − | + | </div> | |
| − | |||
| − | |||
== Termination Problems Data Base == | == Termination Problems Data Base == | ||
| Line 53: | Line 98: | ||
The following competitions have taken place: | The following competitions have taken place: | ||
| + | * [[Termination Competition 2025]] affiliated with [https://www.imn.htwk-leipzig.de/WST2025/ WST 2025], [https://termcomp.github.io/Y2025/ Results]. | ||
| + | * [[Termination Competition 2024]] affiliated with [https://merz.gitlabpages.inria.fr/2024-ijcar/ IJCAR 2024], [https://termcomp.github.io/Y2024/ Results]. | ||
| + | * [[Termination Competition 2023]] affiliated with [[WST2023]], [https://termcomp.github.io/Y2023/ Results]. | ||
| + | * [[Termination Competition 2022]] affiliated with [https://easychair.org/smart-program/FLoC2022/IJCAR-index.html IJCAR 2022], [https://termcomp.github.io/Y2022/ Results]. | ||
| + | * [[Termination Competition 2021]] affiliated with [http://www.cs.cmu.edu/~mheule/CADE28/ CADE 2021], [https://termcomp.github.io/Y2021/ Results]. | ||
| + | * [[Termination Competition 2020]] affiliated with [https://ijcar2020.org/ IJCAR 2020], [https://termcomp.github.io/Y2020/ Results]. | ||
* [[Termination Competition 2019]] affiliated with [https://tacas.info/toolympics.php Toolympics at TACAS 2019], [https://termcomp.github.io/Y2019/ Results]. | * [[Termination Competition 2019]] affiliated with [https://tacas.info/toolympics.php Toolympics at TACAS 2019], [https://termcomp.github.io/Y2019/ Results]. | ||
* [[Termination Competition 2018]] affiliated with FLoC 2018, Oxford, UK, July 13, 2018, [https://termcomp.github.io/Y2018/ Results]. | * [[Termination Competition 2018]] affiliated with FLoC 2018, Oxford, UK, July 13, 2018, [https://termcomp.github.io/Y2018/ Results]. | ||
| Line 85: | Line 136: | ||
could solve it, they shouted "solved". | could solve it, they shouted "solved". | ||
| − | == | + | == Results == |
| − | + | The results of (almost) all competitions are available [https://termcomp.github.io/ here] | |
Latest revision as of 15:10, 24 February 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.
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.
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 ouput 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
Termination of Probabilistic Rewriting
- PTRS Standard (since 2024)
- PTRS Innermost (since 2024)
Termination of Programs
- 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
- TRS Runtime Complexity
- TRS Innermost Runtime Complexity
- TRS Derivational Complexity
- TRS Innermost Derivational Complexity
- TRS Parallel Innermost Derivational Complexity
- ITS Complexity
Complexity Analysis
Termination Problems Data Base
The Termination Problems Data Base collects all the problems used in the competitions.
We welcome problem submissions from non-participants.
History of Termination Competitions
The following competitions have taken place:
- Termination Competition 2025 affiliated with WST 2025, Results.
- Termination Competition 2024 affiliated with IJCAR 2024, Results.
- Termination Competition 2023 affiliated with WST2023, Results.
- Termination Competition 2022 affiliated with IJCAR 2022, Results.
- Termination Competition 2021 affiliated with CADE 2021, Results.
- Termination Competition 2020 affiliated with IJCAR 2020, Results.
- Termination Competition 2019 affiliated with Toolympics at TACAS 2019, Results.
- Termination Competition 2018 affiliated with FLoC 2018, Oxford, UK, July 13, 2018, Results.
- Termination Competition 2017 affiliated with FSCD, Results of Competition, Results of demonstration.
- Termination Competition 2016 affiliated with WST (Workshop on Termination), Results of Competition. Presentation at WST
- Termination Competition 2009 Results, Announcement
- Termination Competition 2008, Results, Report
- Termination Competition 2007, Report
- Termination Competition 2006, Report
- Termination Competition 2005, Report
- Termination Competition 2004, Report
At the "tool demonstration" in 2003, participating provers (including AProVe, Torpa, Matchbox) were run on the laptop computers of their developers in the room. Termination problems were announced on the spot by participants, then written on the blackboard, then typed in by everyone, and when a team's program could solve it, they shouted "solved".
Results
The results of (almost) all competitions are available here
