Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-01-08T09:16:01.411Z Has data issue: false hasContentIssue false
  • English
  • Français

A duality between proof systems for cyclic term graphs

Published online by Cambridge University Press:  01 June 2007

CLEMENS GRABMAYER
CLEMENS GRABMAYER*
Affiliation:
Department of Computer Science, Vrije Universiteit Amsterdam, de Boelelaan 1081a, 081 HV Amsterdam, the Netherlands Email: [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a proof-theoretic observation about two kinds of proof systems for bisimilarity between cyclic term graphs.

First we consider proof systems for demonstrating that μ term specifications of cyclic term graphs have the same tree unwinding. We establish a close connection between adaptations for μ terms over a general first-order signature of the coinductive axiomatisation of recursive type equivalence by Brandt and Henglein (Brandt and Henglein 1998) and of a proof system by Ariola and Klop (Ariola and Klop 1995) for consistency checking. We show that there exists a simple duality by mirroring between derivations in the former system and formalised consistency checks, which are called ‘consistency unfoldings', in the latter. This result sheds additional light on the axiomatisation of Brandt and Henglein: it provides an alternative soundness proof for the adaptation considered here.

We then outline an analogous duality result that holds for a pair of similar proof systems for proving that equational specifications of cyclic term graphs are bisimilar.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 17 , Issue 3 , June 2007 , pp. 439 - 484
Copyright
Copyright © Cambridge University Press 2007

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.)

References

Amadio, R. M. and Cardelli, L. (1993) Subtyping recursive types. ACM Transactions on Programming Languages and Systems 15 (4)575–631.CrossRefGoogle Scholar
Ariola, Z. M. and Klop, J. W. (1995) Equational term graph rewriting. Technical Report IR-391, Vrije Universiteit Amsterdam. (This is an extension of Ariola and Klop (1996).)Google Scholar
Ariola, Z. M. and Klop, J. W. (1996) Equational term graph rewriting. Fundamenta Informaticae 26 (3-4)207–240.CrossRefGoogle Scholar
Blom, S. (2001) Term Graph Rewriting, Syntax and Sematics, Ph.D. thesis, Vrije Universiteit Amsterdam.Google Scholar
Brandt, M. and Henglein, F. (1998) Coinductive axiomatization of recursive type equality and subtyping. Fundamenta Informaticae 33 1–30.CrossRefGoogle Scholar
Grabmayer, C. (2002a) A duality in proof systems for recursive type equality and bisimulation equivalence on cyclic term graphs. In: Plump, D. (ed.) Proceedings of TERMGRAPH 2002. Electronic Notes in Computer Science 72 (1).CrossRefGoogle Scholar
Grabmayer, C. (2002b) A duality in proof systems for recursive type equality and bisimulation equivalence on cyclic term graphs. Technical Report IR-499, Dept. of Math. and Comp. Sci., Vrije Universiteit Amsterdam. (Available from the authors's home page.)Google Scholar
Grabmayer, C. (2005) Relating Proof Systems for Recursive Types, Ph.D. thesis, Vrije Universiteit Amsterdam.Google Scholar
Hurkens, A. J. C., McArthur, M., Moschovakis, Y., Moss, L. S. and Whitney, G. (1998) The logic of recursive equations. Journal of Symbolic Logic 63 (2)451–478.CrossRefGoogle Scholar
Hüttel, H. and Stirling, C. (1991) Actions speak louder than words: Proving bisimilarity for context-free processes. In: Proceedings of LICS'91, IEEE Computer Society Press 376–386.Google Scholar
Klop, J. W. (2000) Proof systems for cyclic term graphs. Lecture at the Winter Workshop on Logics, Types and Rewriting, February 1-3 2000, Heriot-Watt University, Edinburgh. (Available at: http://www.cs.vu.nl/jwk/ctg1-41.pdf.)Google Scholar
Milner, R. (1984) A complete inference system for a class of regular behaviours. Journal of Computer and System Sciences 28 439–466.CrossRefGoogle Scholar
Moss, L. S. (2003) Recursion and corecursion have the same equational logic. Theoretical Computer Science 294 (1-2)233–267.CrossRefGoogle Scholar
Rosu, G. and Goguen, J. (2001) Circular coinduction. In: Proceedings of IJCAR'01, Siena, Italy.Google Scholar
Salomaa, A. (1966) Two complete axiom systems for the algebra of regular events. Journal of the ACM 13 (13)158–169.CrossRefGoogle Scholar
Sangiorgi, D. (1998) On the bisimulation proof method. Mathematical Structures in Computer Science 8 (5)447–479.CrossRefGoogle Scholar
Troelstra, A. and Schwichtenberg, H. (2000) Basic Proof Theory, Cambridge University Press.CrossRefGoogle Scholar