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/7253
Title: The Complexity of Kleene Algebra with Tests
Authors: Cohen, Ernie
Kozen, Dexter
Smith, Frederick
Keywords: computer science
technical report
Issue Date: Jul-1996
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR96-1598
Abstract: Kleene algebras with tests provide a natural framework for equational specification and verification. Kleene algebras with tests and related systems have been used successfully in basic safety analysis, source-to-source program transformation, and concurrency control. The equational theory of Kleene algebras with tests has been shown to be decidable in at most exponential time by an efficient reduction to Propositional Dynamic Logic. In this paper we prove that the theory is PSPACE-complete.
URI: http://hdl.handle.net/1813/7253
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
96-1598.pdf285.84 kBAdobe PDFView/Open
96-1598.ps358.91 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us