Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Applications of Metric Coinduction

Applications of Metric Coinduction

File(s)
TR2007-2080.pdf (225.1 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7874
Collections
Computing and Information Science Technical Reports
Author
Kozen, Dexter
Ruozzi, Nicholas
Abstract

Metric coinduction is a form of coinduction that can be used to establish properties of objects constructed as a limit of finite approximations. One proves a coinduction step showing that some property is preserved by one step of the approximation process, then automatically infers by the coinduction principle that the property holds of the limit object. This can often be used to avoid complicated analytic arguments involving limits and convergence, replacing them with simpler algebraic arguments. This paper examines the application of this principle in a variety of areas, including infinite streams, Markov chains, Markov decision processes, and non-well-founded sets. These results point to the usefulness of coinduction as a general proof technique.

Date Issued
2007-05-16
Publisher
Cornell University
Keywords
computer information science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2007-2080
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance