Abstract: We present a new interface for Object-Oriented Database Management Systems (OODBMSs). The GOODIES system (an acronym for Graphical Object Oriented Database Interface with Extended Synchronism) combines and expands the functions of many existing interface systems, introducing some new concepts for improved browsing in an OODBMS. The implementation of GOODIES proposes a new approach to database interfaces development: instead of being strongly dependent of the underlying DBMS, GOODIES is based on the main features of the object-oriented data model. The system design is based on an internal model and on an external model. The internal model defines the relationships that bind the interface to the DBMS. The external model determines the possible interaction between the user and the interface system. This paper describes the concepts of the external model of the GOODIES system.

Abstract: This paper describes a software development environment which transforms specifications defined in terms of statecharts into functionally equivalent programs in C. The environment encourages the user to maintain developed systems at the highest supported abstraction level, i.e. at the statechart specification level. This process is aided by a concurrent animation of the statechart specification with the execution of the corresponding functionally equivalent program. The events which drive the execution of the program are handed over to a statechart simulator either in real time or are registered in a log file and later submitted to the simulator. At the latter alternative, the user controls the firing of events which are used to animate the program's statechart at an appropriate pace. Those facilities may be used to validate developed systems as well as to pin-point design errors such as, for instance, infinite loops or deadlocks.

Abstract: Correctness of several tree traversing algorithms is proved in an informal but quite rigorous way by using induction and a convenient graphical representation for the state of computation. These proofs are much simpler than their formal counterparts and provide an intuitive insight for the ideas behind the algorithms.

Abstract: A graph is clique-complete if no two of its maximal cliques are disjoint. A vertex is universal if it is adjacent to all other vertices in the graph. We prove that every clique-complete graph either contains a universal vertex or an induced subgraph in an indexed family , defined in the text. We show that this is precisely the family of minimal graphs which are clique-complete but have no universal vertices. The minimality used here refers to induced subgraphs.

For , we show that is neither perfect nor planar. It follows that every planar clique-complete graph without a universal vertex contains an induced subgraph isomorphic to . A similar result holds for perfect clique-complete graphs without universal vertices. We also specialize the latter result for certain classes of perfect graphs.

Abstract: This paper analyzes the problem of maintaining application-dependent integrity constraints in databases for design environments. Such environments are characterized by the need to support different types of interaction between integrity maintenance and version maintenance mechanisms. The paper describes these problems, and proposes a framework in which they can be treated homogeneously. We thus bridge the gap existing between research on constraint maintenance and on version control, which has so far posed several problems to researchers in these two areas.

Abstract: We present experimental results for 3 bipartite matching algorithms on 3 classes of sparse graphs. The push-relabel maximum flow algorithm, specialized for unweighted bipartite graphs, came out as the most robust algorithm, being the fastest by a significant margin in two of the classes and competitive in the other one. The other two algorithms implemented are Hopcroft and Karp's and Alt, Blum, Mehlhorn, and Paul's, and it is noteworthy that both have better worst-case bounds than the push-relabel algorithm. The input classes used are variations of random bipartite graphs. We also show that speed-ups of up to 3.2 with respect to the sequential implementation can be obtained by parallelizing the push-relabel algorithm on a shared-memory multiprocessor using up to 12 processors.

Abstract: This paper presents an integrity maintenance system that has been developed for maintaining static constraints in databases, using the active database paradigm. This system has been added to the O2 object oriented database system, and is fully functional. Constraints are specified by the user in a first order logic language, and transformed in production rules, which are stored in the database. The rules are then used to maintain the corresponding set of constraints, for all applications that use the database, and which no longer need to worry about integrity control. We extend previous work on constraint maintenance in two ways: our system can be used as a constraint maintenance layer on top of object-oriented, relational and nested relational databases; in the case of object-oriented systems, we provide constraint support not only in the case of object composition, but also consider inheritance and methods.

An -transversal theorem for bipartite graphs.

Abstract: Continuing the work begun by Philip Hall in 1935, we here give necessary and sufficient conditions for the existence, in a bipartite graph, of a set of edges satisfying specified lower and upper bounds. Here the graph is directed bipartite; lower and upper bounds are specified by integer-valued functions, and , on the collection of all directed sets of vertices, or perhaps on some subcollection, such as the collection of singletons. We require these functions to be super- and sub-modular, respectively. An -transversal is a set of edges that satisfies these bounds. A second restriction, , for edge sets and , is also permitted.

One might hope to give necessary and sufficient conditions for the existence of a general -transversal. In this paper, this is done for the special case in which the domain of one of the functions, say , is restricted to singletons. Graph contains an -transversal such that if and only if for each in and each subset of , . This function , when applied to a set of vertices of , is the number of edges of directed away from minus the number of edges of directed toward .

This work is motivated by the Woodall Conjecture, which states: in any directed graph, a largest packing of transversals of directed coboundaries is equal in size to a smallest directed cut. We observe that the domain of this Conjecture can be reduced to directed bipartite graphs. For such graphs, the partial -theory developed here is used to show that the edge set of any directed bipartite graph can be partitioned into two subsets, one a transversal of directed coboundaries, the other a -transversal of the vertex coboundaries. In this application we require the supermodularity of the size of a maximum partition of a directed coboundary into directed cuts.

Abstract: We note that a few modifications to the Guibas and Stolfi's algorithm for Nearest-Neighbor Delaunay Triangulation produce an algorithm for the Farthest-Neighbor Delaunay Triangulation (a triangulation of the convex hull of the set of points) that, like the original, runs in optimal time and linear space.

Abstract: Given an undirected graph and four distinct special vertices , the Two Disjoint Paths Problem consists in determining whether there are two disjoint paths connecting to and to , respectively.

There is an analogous version of the problem for acyclic directed graphs, in which it is required that the two paths be directed, as well.

The known characterizations for the nonexistence of solutions in both problems are, in some sense, the same, which indicates that under some weak conditions the edge orientations in the directed version are irrelevant.

We present the first direct proof of the irrelevance of edge orientations.

Point set pattern matching in -dimensions.

Abstract: In this paper, we apply computational geometry techniques to obtain an efficient algorithm for the following point set pattern matching problem. Given a set of points and a set of points in the -dimensional Euclidean space, determine whether matches any -subset of , where a match can be any similarity, i.e., the set is allowed to undergo translation, rotation, reflection and global scaling. Motivated by the need to traverse the sets in an orderly fashion to shun exponential complexity, we circumvent the lack of a total order for points in high dimensional spaces by presenting an extension of one-dimensional sorting to higher dimensions (called circular sorting). This mechanism, which is of interest in its own right, enables us to achieve the orderly traversal we sought. An optimal algorithm (in time and space) is described for performing circular sorting in arbitrary dimensions. The time complexity of the resulting algorithm for point set pattern matching is for dimension one and for dimension .

Abstract: The construction of minimal acyclic deterministic partial finite automata to represent large natural language vocabularies is described. Applications of such automata include: spelling checkers and advisers, multilanguage dictionaries, thesauri, minimal perfect hashing and text compression.