Feasibly Reducing KAT Equations to KA Equations

Details Feasibly Reducing KAT Equations to KA Equations Feasibly Reducing KAT Equations to KA Equations

2008-01-15

arxiv.org/abs/0801.2368v1

Mathematics

Logic

Scientific paper

Kleene algebra (KA) is the algebra of regular events. Familiar examples of Kleene algebras include regular sets, relational algebras, and trace algebras. A Kleene algebra with tests (KAT) is a Kleene algebra with an embedded Boolean subalgebra. The addition of tests allows one to encode {\tt while} programs as KAT terms, thus the equational theory of KAT can express (propositional) program equivalence. More complicated statements about programs can be expressed in the Hoare theory of KAT, which suffices to encode Propositional Hoare Logic. That the equational theory of KAT reduces to the equational theory of KA has been shown by Cohen et al. Unfortunately, their reduction involves an exponential blowup in the size of the terms involved. Here we give an alternate feasible reduction.

Affiliated with

Also associated with

No associations

Rating

Feasibly Reducing KAT Equations to KA Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Feasibly Reducing KAT Equations to KA Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feasibly Reducing KAT Equations to KA Equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-151512