2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1985 1984 1982 1980 1979 1978 1977 1976 1975
Conferences Reports
Bergstra, J.A. and Ollongren, A. and Weide, Th.P. van der, An axiomatization of the rational data objects. Fundamentals of Computation Theory (Algebraic, Arithmetic, and Categorical Methods in Computation Theory), Poznan-Kornik, Poland, September 19-23, 1977, Lecture Notes in Computer Science edition, Vol: 56, Pages: 33-38, Springer, 1977
In the present paper we introduce the notion of a data-type system consisting of a many-sorted structure together with a finite set of axioms. This notion is a generalizatioon of J.V. Guttag's notion of abstract data-types. We distinguish between internal and external objects and we get the opportunity to split up a programming task into data-type implementation and data-type use. The language for external objects is the one available to the user of a data-type system. The internal language can be used to introduce operations for instance in order to enable one to obtain more concise formulations of properties of data objects.
In our definition it is not necessary that the objects of different sorts are finite, even though we wil in practice mostly be interested in data objects which are finitely representable in some way.
[ cite ]
Leeuwen, J. van and Weide, Th.P. van der, Alternative Path Compression Rules. Technical report, September, University of Utrecht, The Netherlands, 1977, An outline of the results were presented at the Fachtagung on Algorithms and Complexity Theory, Oberwolfach, Oct 1977
UNION-FIND programs symbolize a large class of algorithms for merging and searching disjoint sets, which are represented as trees. In the "collapsing" rule for FIND's one must first locate a root and then traverse the same FIND-path a second time in order to attach each of its nodes to the root. In an attempt to find a more elegant implementation, we shall consider the problem of how the "second pass" can be eliminated while preserving good efficiency (with or without a balancing rule for UNIONs). We consider several alternative tree compression methods, including Rem's algorithm as presented by Dijkstra. We propose a simpler one-pass technique called "path halving", which performs well in both the balanced and unbalanced cases. We show that the time needed for executing O(n) UNIONs and FINDs is bounded by O(n log n) when only path halving is used. When the "weighted union" rule is used for set-merging and path-halving for FINDs, then the cost for O(n) UNIONs and FINDs is bounded by O(n log* n). We conclude that for all practical purposes path-halving is a viable alternative to the original collapsing rule.
[ cite ]
Conferences Reports
Bergstra, J.A. and Ollongren, A. and Weide, Th.P. van der, Multilevel Set Objects. Technical report, Institute of Applied Mathematics and Computer Science, Leiden, The Netherlands, 1977
[ cite ]
Weide, Th.P. van der, PO Structures. Technical report, Institute of Applied Mathematics and Computer Science, Leiden, The Netherlands, 1977
[ cite ]