Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7041
Title: Rabin Measures and Their Applications to Fairness and Automata Theory
Authors: Klarlund, Nils
Kozen, Dexter
Keywords: computer science
technical report
Issue Date: Apr-1991
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1201
Abstract: Rabin conditions are general class of properties of infinite sequences that emcompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper we show how to determine whether a program satisfies a Rabin condition by reasoning about single transitions instead of infinite computations. We introduce a concept, called a Rabin measure, which in a precise sense expresses progress for each transition toward satisfaction of the Rabin condition. When applied to termination problems under fairness constraints, Rabin measures constitute a simpler verification method than previous approaches, which often are syntax-dependent and require recursive applications of proof rules to syntactically transformed programs. Rabin measures also generalize earlier automata-theoretic verification methods. Combined with a result by Safra, our result gives a method for proving that a program satisfies a nondeterministic Buchi automaton specification.
URI: http://hdl.handle.net/1813/7041
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
91-1201.pdf1.36 MBAdobe PDFView/Open
91-1201.ps319.03 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us