print · source · login   

WST 2022 - 18th International Workshop on Termination


The Workshop on Termination (WST) traditionally brings together, in an informal setting, researchers interested in all aspects of termination, whether this interest be practical or theoretical, primary or derived. The workshop also provides a ground for cross-fertilization of ideas from the different communities interested in termination (e.g., working on computational mechanisms, programming languages, software engineering, constraint solving, etc.). The friendly atmosphere enables fruitful exchanges leading to joint research and subsequent publications.

The 18th International Workshop on Termination continues the successful workshops held in St. Andrews (1993), La Bresse (1995), Ede (1997), Dagstuhl (1999), Utrecht (2001), Valencia (2003), Aachen (2004), Seattle (2006), Paris (2007), Leipzig (2009), Edinburgh (2010), Obergurgl (2012), Bertinoro (2013), Vienna (2014), Obergurgl (2016), Oxford (2018) and virtually (2021).

Important Dates

  • submission deadline: May 10, 2022
  • notification: June 15, 2022
  • final version due: July 11, 2022
  • workshop: August 11-12, 2022

Workshop Topics

The 18th International Workshop on Termination welcomes contributions on all aspects of termination. In particular, papers investigating applications of termination (for example in complexity analysis, program analysis and transformation, theorem proving, program correctness, modeling computational systems, etc.) are very welcome.

Topics of interest include (but are not limited to):

  • termination analysis in any domain (lambda calculus, declarative programming, rewriting, transition systems, probabilistic programs, etc.)
  • complexity analysis in any domain
  • abstraction methods in termination analysis
  • certification of termination and complexity proofs
  • challenging termination problems
  • comparison and classification of termination methods
  • implementation of termination and complexity methods
  • non-termination analysis and loop detection
  • normalization and infinitary normalization
  • operational termination of logic-based systems
  • ordinal notation and subrecursive hierarchies
  • SAT, SMT, and constraint solving for (non-)termination analysis
  • scalability and modularity of termination methods
  • well-founded relations and well-quasi-orders


Submissions are short papers/extended abstracts which should not exceed 5 pages. There will be no formal reviewing. In particular, we welcome short versions of recently published articles and papers submitted elsewhere. The program committee checks relevance and provides additional feedback for each submission. The accepted papers will be made available electronically before the workshop.

Papers should be submitted electronically via the submission page:

Please, use LaTeX and the LIPIcs style file to prepare your submission.

Invited Speakers

René Thiemann: CeTA — Efficient Certification of Termination Proofs

We present recent developments in CeTA w.r.t. the efficient certification of termination proofs. Here, efficiency is seen under various aspects. First, we present a case study on minimizing the formalization effort, namely when trying to verify the classical path orders by viewing them as instances of the weighted path order. Second, we argue that the efficient generation of certificates within termination tools requires more powerful certifiers, in particular when considering the usage of SAT- or SMT-solvers. Third, we present recent developments which aim at improving the execution time of CeTA.


Thursday 11 August:

  • Session 1: 09:00-10:30
    • 09:00-09:30 Cynthia Kop and Deivid Vale: Tuple Interpretations and Applications to Higher-Order Runtime Complexity
    • 09:30-10:00 Liye Guo and Cynthia Kop: A transitive HORPO for curried systems
    • 10:00-10:30 Alfons Geser, Dieter Hofbauer and Johannes Waldmann: Approximating Relative RFC-Match-Bounds
  • Session 2: 11:00-12:30
    • 11:00-12:00 René Thiemann: CeTA — Efficient Certification of Termination Proofs (invited talk)
    • 12:00-12:30 Nao Hirokawa and Aart Middeldorp: Hydra Battles and AC Termination
  • Session 3: 14:00-15:30
    • 14:00-14:30 Florian Frohn and Carsten Fuhs: A Calculus for Modular Non-Termination Proofs by Loop Acceleration
    • 14:30-15:00 Marcel Hark, Florian Frohn and Jürgen Giesl: Deciding Termination of Uniform Loops with Polynomial Parameterized Complexity
    • 15:00-15:30 Jürgen Giesl, Nils Lommen, Marcel Hark and Fabian Meyer: Improved Automatic Complexity Analysis of Integer Programs
  • Session 4: 16:00-17:00
    • Business Meeting

Friday 12 August

  • Session 1: 09:00-10:30
    • The termination competition: overview of results
  • Session 2: 11:00-12:30 (tools session)
    • 11:00-11:20 Florian Frohn and Jürgen Giesl: LoAT: The Loop Acceleration Tool
    • 11:20-11:40 Nils Lommen, Fabian Meyer, Marcel Hark and Jürgen Giesl: Automatic Complexity Analysis of (Probabilistic) Integer Programs via KoAT
    • 11:40-12:00 Jürgen Giesl, Daniel Cloerkes, Stefan Dollase, Florian Frohn, Carsten Fuhs, Jera Hensel, David Keller, Nils Lommen and Fabian Meyer: AProVE 2022
    • 12:00-12:20 Makoto Hamana and Keigo Imai: The System SOL version 2022
    • 12:20-12:30 Cynthia Kop: Things WANDA cannot do
  • Session 3: 14:00-15:30 (tools and categories session)
    • 14:00-14:20 Christina Kohl and René Thiemann: CeTA – A certifier for termCOMP 2022
    • 14:20-14:40 Johannes Waldmann: Certified Matchbox
    • 14:40-15:00 Dieter Hofbauer: MultumNonMulta at termCOMP 2022
    • 15:00-15:20 Carsten Fuhs: Runtime complexity of parallel-innermost term rewriting at TermComp 2022
    • 15:20-15:35 Fabian Mitterwallner and Aart Middeldorp: DEPP

Program Committee