Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T18:14:43.535Z Has data issue: false hasContentIssue false

On global induction mechanisms in a μ-calculus with explicitapproximations

Published online by Cambridge University Press:  15 January 2004

Christoph Sprenger
Affiliation:
INRIA Sophia Antipolis, 2004, route des Lucioles, BP 93, 06902 Sophia Antipolis, France; sprenger@sophia.inria.fr.
Mads Dam
Affiliation:
Dept. of Microelectronics and Information Technology, Royal Institute of Technology, KTH, Forum 105, 164 40 Kista, Sweden; mfd@imit.kth.se.
Get access

Abstract

We investigate a Gentzen-style proof system for the first-order μ-calculusbased on cyclic proofs, produced by unfolding fixed point formulasand detecting repeated proof goals. Our system uses explicit ordinalvariables and approximations to support a simple semantic inductiondischarge condition which ensures the well-foundedness of inductivereasoning. As the main result of this paper we propose a new syntacticdischarge condition based on traces and establish its equivalencewith the semantic condition. We give an automata-theoretic reformulationof this condition which is more suitable for practical proofs. Fora detailed comparison with previous work we consider two simpler syntacticconditions and show that they are more restrictive than our new condition.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable