A polynomial algorithm for minimal interval representation

Itzhak Gilboa (1) , Anat Fischer , Moshe Shpitalni

1 Northwestern University [Evanston]

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

Keywords: Code Gray; Fonction commutation; Analyse algorithme; Temps polynomial; Représentation tridimensionnelle; Modèle géométrique; Géométrie solide; Système informatique

Domains: Economy and decision science

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