A polynomial algorithm for minimal interval representation - Archive ouverte HAL Access content directly
Journal Articles Journal of Algorithms in Cognition, Informatics and Logic Year : 1992

A polynomial algorithm for minimal interval representation

(1) , ,
1
Itzhak Gilboa
  • Function : Author
  • PersonId : 867909
Anat Fischer
  • Function : Author
Moshe Shpitalni
  • Function : Author

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.

Dates and versions

hal-00481389 , version 1 (06-05-2010)

Identifiers

Cite

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⟩

Collections

HEC
130 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More