playbooks

home / skills / a5c-ai / babysitter / termination-analyzer

termination-analyzer skill

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/termination-analyzer

This skill helps prove termination of algorithms by automatically identifying ranking functions, well-founded orderings, and generating formal termination

npx playbooks add skill a5c-ai/babysitter --skill termination-analyzer

Review the files below or copy the command above to add this skill to your agents.

Files (1)
SKILL.md
1.1 KB
---
name: termination-analyzer
description: Prove termination of algorithms and programs using ranking functions and well-founded orderings
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: algorithm-analysis
  phase: 6
---

# Termination Analyzer

## Purpose

Provides expert guidance on proving termination of algorithms through ranking functions, well-founded orderings, and automated analysis.

## Capabilities

- Identify ranking/variant functions automatically
- Prove well-founded orderings
- Handle mutual recursion
- Detect potential non-termination
- Generate termination certificates
- Analyze complex control flow

## Usage Guidelines

1. **Structure Analysis**: Identify recursive calls and loop structures
2. **Ranking Function**: Find or construct appropriate ranking function
3. **Ordering Proof**: Prove well-foundedness of the ordering
4. **Certificate Generation**: Generate formal termination proof
5. **Non-termination Detection**: Flag potential infinite loops

## Tools/Libraries

- AProVE
- T2
- Ultimate Automizer
- SMT solvers

Overview

This skill proves termination of algorithms and programs by synthesizing ranking functions and establishing well-founded orderings. It combines automated analysis with human-guided inspection to detect non-termination, handle mutual recursion, and produce formal termination certificates. The focus is on practical, checkable proofs that integrate with SMT solvers and termination tools.

How this skill works

The analyzer inspects control flow to identify loops, recursive calls, and mutual recursion patterns. It attempts to synthesize ranking (variant) functions or lexicographic combinations that strictly decrease along every call or iteration, and then proves well-foundedness of the induced ordering. When synthesis succeeds, it can emit a machine-checkable termination certificate; when it fails, it highlights counterexamples and potential infinite traces.

When to use it

  • You need a formal termination proof for a loop, recursive function, or mutual recursion.
  • You suspect subtle non-termination or want to rule out infinite executions.
  • Preparing correctness proofs or safety certificates that require termination guarantees.
  • Integrating termination checks into CI/CD or automated code review pipelines.
  • Analyzing algorithms with complex control flow or mixed numeric and data-structure measures.

Best practices

  • Start by isolating the loop or recursive component and simplify preconditions.
  • Provide candidate measures (e.g., sizes, depths, norms) to guide synthesis when automatic inference struggles.
  • Prefer lexicographic ranking functions for multi-dimensional progress.
  • Use SMT-friendly encodings and bounded unwinding to produce counterexamples quickly.
  • Combine automated tools (AProVE, T2, Ultimate) with manual proofs for edge cases.

Example use cases

  • Proving termination of a recursive graph traversal that decreases a custom measure on visited sets.
  • Generating a termination certificate for a sorting routine that relies on a lexicographic pair (remaining length, inversion count).
  • Detecting and explaining potential non-termination in a scheduler loop with complex state transitions.
  • Verifying mutual recursion among parser functions using well-founded orderings on input position and recursion depth.
  • Integrating termination checks into CI to block merges that introduce potential infinite loops.

FAQ

What kinds of ranking functions are supported?

Supports linear, polynomial, norm-based, and lexicographic ranking functions, plus user-provided measures to guide synthesis.

Can it produce machine-checkable certificates?

Yes. When a proof is found, the skill can generate a certificate compatible with SMT solvers and common termination checkers.

How does it handle mutual recursion?

It constructs a global well-founded ordering or tuple-based measures that jointly decrease across the mutually recursive calls.