Go to ScienceDirect® Home Skip Main Navigation Links
 Register or Login:   Password:      
HomeSearchBrowse JournalsBrowse Abstract DatabasesBrowse Reference WorksMy AlertsMy ProfileHelp (Opens new window)
 Quick Search:  within Quick Search searches abstracts, titles, and keywords. Click for more information. 
Theoretical Computer Science
Volume 308, Issues 1-3 , 3 November 2003, Pages 1-53

This Document
Abstract
Abstract + References
PDF (820 K)

Actions
Cited By
Save as Citation Alert
E-mail Article
Export Citation

doi:10.1016/S0304-3975(02)00895-2    How to cite or link using doi (opens new window) Cite or link using doi  
Copyright © 2002 Elsevier B.V. All rights reserved.

Fundamental Study

Behavioural differential equations: a coinductive calculus of streams, automata, and power series*1

J. J. M. M. RuttenE-mail The Corresponding Author, E-mail The Corresponding Author

CWI, P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands

Received 25 October 2000;  revised 11 November 2002;  accepted 14 November 2002; Communicated by D. Sannella  Available online 19 December 2002.


Abstract

We present a theory of streams (infinite sequences), automata and languages, and formal power series, in terms of the notions of homomorphism and bisimulation, which are the cornerstones of the theory of (universal) coalgebra. This coalgebraic perspective leads to a unified theory, in which the observation that each of the aforementioned sets carries a so-called final automaton structure, plays a central role. Finality forms the basis for both definitions and proofs by coinduction, the coalgebraic counterpart of induction. Coinductive definitions take the shape of what we have called behavioural differential equations, after Brzozowski's notion of input derivative. A calculus is developed for coinductive reasoning about all of the aforementioned structures, closely resembling calculus from classical analysis.

Author Keywords: Coalgebra; Automaton; Homomorphism; Bisimulation; Finality; Coinduction; Stream; Formal language; Formal power series; Differential equation; Input derivative

Mathematical subject codes: 68Q10; 68Q55; 68Q85


*1 This paper is a revised version of Technical Report SEN-R0023, CWI, Amsterdam, 2000.



This Document
Abstract
Abstract + References
PDF (820 K)

Actions
Cited By
Save as Citation Alert
E-mail Article
Export Citation
Theoretical Computer Science
Volume 308, Issues 1-3 , 3 November 2003 , Pages 1-53


 
HomeSearchBrowse JournalsBrowse Abstract DatabasesBrowse Reference WorksMy AlertsMy ProfileHelp (Opens new window)

Send feedback to ScienceDirect
Software and compilation © 2003 ScienceDirect. All rights reserved.
ScienceDirect® is an Elsevier Science B.V. registered trademark.


Your use of this service is governed by Terms and Conditions. Please review our Privacy Policy for details on how we protect information that you supply.