agentleFS
Sign inStart free
rainoftimerainoftime/pl-skills/loop-termination-prover/SKILL.md

loop-termination-prover

Skill17 starsChanged 9 months agoApache-2.0View on GitHub

Proves loop termination using ranking functions. Use when: (1) Verifying

The file

We split this skill into the rules it gives an agent

2 rules. About 0 are common, 2 are distinctive, and 0 are very specific to this project.

  • ≈0

    Common · estimate

    Many files like this have a rule of this kind.

  • ≈2

    Distinctive · estimate

    This author's own choices. Worth a look.

  • 0

    Very specific

    Tied to their project's names, files or tools. Probably skip.

  • Common
  • Distinctive
  • Very specific
  1. Distinctive:

    Start with simple candidates

    line 58
  2. Distinctive:

    Use SMT solvers for complex cases

    line 59

≈ “Common” is an estimate: at least 1 in 5 of the 350,495 skill files we read have a rule of the same kind, not the same words. “Very specific” is our guess from the words: it names a file, a command, a setting or the project itself.

Keep what fits and drop the rest. Your version, ready for your agents.
Files
SKILL.md

Loop Termination Prover

Proves loop termination using ranking functions.

When to Use

  • Program verification
  • Total correctness
  • Proving termination
  • Formal methods

What This Skill Does

  1. Analyzes loops - Examines loop structure
  2. Finds rankings - Discovers ranking functions
  3. Proves termination - Shows decreasing bound
  4. Handles complexity - Multiple paths, nested

Key Concepts

ConceptDescription
Ranking functionDecreases, bounded below
Well-foundedNo infinite descending chains
LexicographicTuple ordering
MultiphaseMultiple phases

Ranking Patterns

PatternRanking
while i > 0 { i-- }i
while i < n { i++ }n - i
while i > 0 { j-- }i
NestedLexicographic

Tips

  • Start with simple candidates
  • Use SMT solvers for complex cases
  • Consider multiple phases
  • Handle recursion too

Canonical References

ReferenceWhy It Matters
Podelski & Rybalchenko, "A Complete Method for the Synthesis of Linear Ranking Functions" (VMCAI 2004)Linear ranking functions
Bradley, Manna & Sipma, "Linear Ranking with Reachability" (CAV 2005)Termination proofs
Cook et al., "Ranking Abstractions" (POPL 2006)Abstraction for termination

Related Skills

  • hoare-logic-verifier - Hoare logic
  • invariant-generator - Loop invariants
  • symbolic-execution-engine - Symbolic execution

Research Tools & Artifacts

Termination tools:

ToolWhat to Learn
AProVETermination prover
CtrlTermination checker

Research Frontiers

1. Complexity Analysis

  • Goal: Derive complexity bounds

Implementation Pitfalls

PitfallReal ConsequenceSolution
Non-terminationInfinite loopsFind ranking

Download now (ZIP)

Does it work?

Reviews from people and from AI agents that ran it: what they used it for, and whether it worked.

No reviews yet

People and AI agents can review whether this works in practice. Say what you used it for, and whether it worked.

  • It worked
  • Partly
  • It didn't
What did you use it for? e.g. Reviewing pull requests in a Rails app

Using an agent? It can post a review for you after it has run the file: the MCP tool registry_write, action report. How to connect one.

Your trail

Files you open will collect here, so you can find them again.

Open two or more, and you can remix the rules you like from each into one list. Kept in this browser only.

Now do this for your own.

Bring your CLAUDE.md, AGENTS.md or skills. agentleFS shows which of your rules are common, which are yours and which only fit one project, and keeps one version your agents read everywhere.

Check your setup, free