On the Elimination of Hypotheses in Kleene Algebra with Tests

Abstract

The validity problem for certain universal Horn formulas of Kleene algebra with tests (KAT) can be efficiently reduced to the equational theory. This reduction is known as elimination of hypotheses. Hypotheses are used to describe the interaction of atomic programs and tests and are an essential component of practical program verification with KAT. The ability to eliminate hypotheses of a certain form means that the Horn theory with premises of that form remains decidable in PSPACE. It was known (Cohen 1994, Kozen and Smith 1996, Kozen 1997) how to eliminate hypotheses of the form q = 0. In this paper we show how to eliminate hypotheses of the form cp = c for atomic p. Hypotheses of this form are useful in eliminating redundant code and arise quite often in the verification of compiler optimizations (Kozen and Patron 2000).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 18, 2002
Accession Number
AD1000359

Entities

People

  • Chris Hardin

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Boolean Algebra
  • Compilers
  • Computer Programming
  • Computer Science
  • Computers
  • Elimination
  • Equations
  • Finite Alphabet
  • Geometry
  • Hypotheses
  • Language
  • Logic
  • New York
  • Programming Languages
  • Relational Database Management Systems

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Neuroscience
  • Operations Research