Skip to Main content Skip to Navigation
Journal articles

A polynomial algorithm for minimal interval representation

Itzhak Gilboa 1 Anat Fischer Moshe Shpitalni 
1 Northwestern University [Evanston]
Abstract : The following problem arises in the context of object representation: given two endpoints of an interval in a Gray code table, find a Boolean function in DNF that represents this interval, with as few prime implicants as possible. This paper shows that there is a unique minimal representation and presents a polynomial algorithm that finds it.
Keywords : Gray code Switching function Algorithm analysis Polynomial time Three dimensional representation Geometrical model Solid geometry Computer system
Document type :
Journal articles
Complete list of metadata
https://hal-hec.archives-ouvertes.fr/hal-00481389
Contributor : Antoine Haldemann Connect in order to contact the contributor
Submitted on : Thursday, May 6, 2010 - 3:23:35 PM
Last modification on : Saturday, June 25, 2022 - 10:50:46 AM

Links full text

istex

Identifiers

Collections

HEC

Citation

Itzhak Gilboa, Anat Fischer, Moshe Shpitalni. A polynomial algorithm for minimal interval representation. Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 1992, Vol.13, n°4, pp. 546-563. ⟨10.1016/0196-6774(92)90055-H⟩. ⟨hal-00481389⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

127