We investigate a Gentzen-style proof system for the first-order -calculus based on cyclic proofs, produced by unfolding fixed point formulas and detecting repeated proof goals. Our system uses explicit ordinal variables and approximations to support a simple semantic induction discharge condition which ensures the well-foundedness of inductive reasoning. As the main result of this paper we propose a new syntactic discharge condition based on traces and establish its equivalence with the semantic condition. We give an automata-theoretic reformulation of this condition which is more suitable for practical proofs. For a detailed comparison with previous work we consider two simpler syntactic conditions and show that they are more restrictive than our new condition.
Mots-clés : inductive reasoning, circular proofs, well-foundedness, global consistency condition, $\mu $-calculus, approximants
@article{ITA_2003__37_4_365_0,
author = {Sprenger, Christoph and Dam, Mads},
title = {On global induction mechanisms in a $\mu $-calculus with explicit approximations},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {365--391},
publisher = {EDP-Sciences},
volume = {37},
number = {4},
year = {2003},
doi = {10.1051/ita:2003024},
mrnumber = {2053032},
zbl = {1111.68518},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita:2003024/}
}
TY - JOUR AU - Sprenger, Christoph AU - Dam, Mads TI - On global induction mechanisms in a $\mu $-calculus with explicit approximations JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 365 EP - 391 VL - 37 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2003024/ DO - 10.1051/ita:2003024 LA - en ID - ITA_2003__37_4_365_0 ER -
%0 Journal Article %A Sprenger, Christoph %A Dam, Mads %T On global induction mechanisms in a $\mu $-calculus with explicit approximations %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 365-391 %V 37 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2003024/ %R 10.1051/ita:2003024 %G en %F ITA_2003__37_4_365_0
Sprenger, Christoph; Dam, Mads. On global induction mechanisms in a $\mu $-calculus with explicit approximations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 4, pp. 365-391. doi : 10.1051/ita:2003024. http://archive.numdam.org/articles/10.1051/ita:2003024/
[1] ,, and, System description: Verification of distributed Erlang programs. Lecture Notes in Artificial Intelligence 1421 (1998) 38-41.
[2] and, Local model checking for infinite state spaces. Theor. Comput. Sci. 96 (1992) 157-174. | MR | Zbl
[3] , Proving properties of dynamic process networks. Inf. Comput. 140 (1998) 95-114. | MR | Zbl
[4] and, -calculus with explicit points and approximations. J. Logic Comput. 12 (2002) 43-57. Previously appeared in Fixed Points in Computer Science, FICS (2000). | MR | Zbl
[5] and, Modalities for model checking: branching time strikes back. Sci. Comput. Program. 8 (1987) 275-306. | MR | Zbl
[6] , A Framework for Reasoning about Erlang Code. Ph.D. thesis, Royal Institute of Technology, Stockholm, Sweden (2001).
[7] , Results on the propositional -calculus. Theor. Comput. Sci. 27 (1983) 333-354. | MR | Zbl
[8] and, Games for the -calculus. Theor. Comput. Sci. 163 (1997) 99-116. | Zbl
[9] , Finiteness is mu-ineffable. Theor. Comput. Sci. 3 (1976) 173-181. | MR | Zbl
[10] , On the complexity of -automata, in 29th IEEE Symposium on Foundations of Computer Science (1988) 319-327.
[11] , Formal verification of processes. Master's thesis, University of Edinburgh (2001)
[12] and, Verifying temporal properties using explicit approximants: Completeness for context-free processes, in Foundations of Software Science and Computational Structures (FoSSaCS 02), Grenoble, France. Springer, Lecture Notes in Comput. Sci. 2303 (2002) 372-386. | MR | Zbl
[13] and, On the structure of inductive reasoning: Circular and tree-shaped proofs in the -calculus, Foundations of Software Science and Computational Structures (FoSSaCS 03), Warsaw, Poland, April 7-11 2003. A. Gordon, Springer, Lecture Notes in Comput. Sci. 2620 (2003) 425-440. | Zbl
[14] and, Local model checking in the modal -calculus. Theor. Comput. Sci. 89 (1991) 161-177. | MR | Zbl
[15] , Automata on infinite objects. J. van Leeuwen, Elsevier Science Publishers, Amsterdam, Handb. Theor. Comput. Sci. B (1990) 133-191. | MR | Zbl
Cité par Sources :
