Un-kleene boolean equation solving
AuthorHerlihy, B; Schachte, P; Sondergaard, H
Source TitleINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
PublisherWORLD SCIENTIFIC PUBL CO PTE LTD
AffiliationComputer Science and Software Engineering
Document TypeJournal Article
CitationsHerlihy, B., Schachte, P. & Sondergaard, H. (2007). Un-kleene boolean equation solving. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 18 (2), pp.227-250. https://doi.org/10.1142/S0129054107004668.
Access StatusThis item is currently not available from this repository
<jats:p> We present a new method for finding closed forms of recursive Boolean function definitions. Traditionally, these closed forms are found by Kleene iteration: iterative approximation until a fixed point is reached. Conceptually, our new method replaces each k-ary function by 2<jats:sup>k</jats:sup> Boolean constants defined by mutual recursion. The introduction of an exponential number of constants is mitigated by the simplicity of their definitions and by the use of a novel variant of ROBDDs to avoid repeated computation. Experiments suggest that this approach is significantly faster than Kleene iteration for examples that require many Kleene iteration steps. </jats:p>
KeywordsArtificial Intelligence and Image Processing
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References