We consider the problem of maintaining a set of n integers in the range 0..2~#omega# -1 under the operations of insertion, deletion, predecessor queries, minimum queries and maximum queries on a unit cost RAM with word size w bits. Let f(n) be an arbitrary nondecreasing smooth function satisfying loglog n <= f(n) <= log n~(1/2). A data structure is predecessor queries in worst case O ((log n)/f(n)) time and minimum and maximum queries in worst case constant time. The required space is O (n2~#epsilon##elies on the definition of adequate unifying model structures, which must be powerful enough to capture the interference potential between the different description methods, while remaining simple enough to support (automatic) verification, the key for formal methods to enter industrial practice.#p.1-20#
展开▼
