An algebraic theory of object-oriented systems

The paper presents an algebraic specification of net objects. By net objects we mean those that are defined in object-oriented paradigms and those defined with nested relations in complex database models. An algebraic specification is set up that involves structures of net objects, accesses of net objects, and some features of object-oriented programming, such as multiple inheritance and polymorphism. Objects and their relationships are then characterized formally in the modeling, which utilizes the hierarchical approach in the algebraic theory of abstract data types, and is further developed by adding mechanisms from existing object systems. Categories of net objects are presented with the properties of accesses among them     

A framework for knowledge-based temporal abstraction

A new domain-independent knowledge-based inference structure is presented, specific to the task of abstracting higher-level concepts from time-stamped data. The framework includes a model of time, parameters, events and contexts. A formal specification of a domain's temporal abstraction knowledge supports acquisition, maintenance, reuse and sharing of that knowledge.

The knowledge-based temporal abstraction method decomposes the temporal abstraction task into five subtasks. These subtasks are solved by five domain-independent temporal abstraction mechanisms. The temporal abstraction mechanisms depend on four domain-specific knowledge types: structural, classification (functional), temporal semantic (logical) and temporal dynamic (probabilistic) knowledge. Domain values for all knowledge types are specified when a temporal abstraction system is developed.

The knowledge-based temporal abstraction method has been implemented in the RÉSUMÉ system and has been evaluated in several clinical domains (protocol-based care, monitoring of children's growth and therapy of diabetes) and in an engineering domain (monitoring of traffic control), with encouraging results.     

A theory-based representation for object-oriented domain models

Formal software specification has long been touted as a way to increase the quality and reliability of software; however, it remains an intricate, manually intensive activity. An alternative to using formal specifications directly is to translate graphically based, semiformal specifications into formal specifications. However, before this translation can take place, a formal definition of basic object oriented concepts must be found. The paper presents an algebraic model of object orientation that defines how object oriented concepts can be represented algebraically using an object oriented algebraic specification language O-SLANG. O-SLANG combines basic algebraic specification constructs with category theory operations to capture internal object class structure, as well as relationships between classes     

A Coalgebraic presentation of structured transition systems

This paper relates labelled transition systems and coalgebras with the motivation of comparing and combining their complementary contributions to the theory of concurrent systems. The well-known mismatch between these two notions concerning the morphisms is resolved by extending the coalgebraic framework by lax cohomomorphisms.

Enriching both labelled transition systems and coalgebras with algebraic structure for an algebraic specification, the correspondence is lost again. This motivates the introduction of lax coalgebras, where the coalgebra structure is given by a lax homomorphism. The resulting category of lax coalgebras and lax cohomomorphisms for a suitable endofunctor is shown to be isomorphic to the category of structured transition systems, where both states and transitions form algebras.

The framework is also presented on a more abstract categorical level using monads and comonads, extending the bialgebraic approach introduced by Turi and Plotkin.     

面向对象数据库系统的代数模型

区别于传统的关系数据库，面向对象的数据库系统需要全新的理论及方法上的基础。我们希望能够并面向对象的数据库系统与软件工程中的形式化方法，尤其是抽象数据类型、系统的代数规范等结合起来。类似于代数数据类型理论，本文提出了对象、对象类型及抽象对象类型的代数模型。     

Automatic surface generation in computer aided design

A technique for smoothly blending algebraic surfaces and a language for syntactic specification of objects are developed. Their use in automated design is illustrated by a gate valve example in which all fillets, edge roundings and joining surfaces are automatically constructed. The resulting object has an internal representation that is particularly amenable to interactive editing.     

分布式多媒体系统中对象表示模型及变换方法研究

在设计一个分布式多媒体系统时，具有挑战性的问题之一是如何在系统的不同层次为各模式设计合适的规格描述模型，并提供不同模型的变换方法的集成与同步策略，在本文中，我们给出了几种多媒体对象的表示模型和变换算法，它们把高层的多媒体对象变换成可以用来支持多媒体对象展示和通信的实用模式，在该模式中能较好地保持多媒体对象的集成与同步特性。     

Construction of Interactive Programs in Computer Graphics

In interactive computer graphics, one often finds a gap between sophisticated algorithms, using very high level data structures, and poor methods of program and object construction. Particular programming languages are too readily adopted for solving problems, before a precise specification of the problem to be solved has been formulated.
This paper shows that progress can be made by using modern engineering methods to specify and develop graphical software. Two programming techniques are studied here: the algebraic specification of data types and a functional static modular method of problem statement.
The paper also discusses these proposals in the context of other modes of computer graphics specification and programming.     

Intersection type assignment systems with higher-order algebraic rewriting

General computational models obtained by integrating different specific models have recently become a stimulating and promising research subject. In particular, extensions of various λ-calculi with algebraic rewriting, either typed or untyped, have been deeply investigated. In the present paper this subject is addressed from the point of view of type assignment. A powerful type assignment system, the one based on intersection types, is extended with first- and higher-order algebraic rewriting, and relevant properties, like strong normalization and completeness, are proved.     

Automatic surface generation in computer aided design

A technique for smoothly blending algebraic surfaces and a language for syntactic specification of objects are developed. Their use in automated design is illustrated by a gate valve example in which all fillets, edge roundings and joining surfaces are automatically constructed. The resulting object has an internal representation that is particularly amenable to interactive editing.This work was supported in part by the National Science Foundation under grant ECS 83-12096 and MCS 82-17996     

Sensor Placement for Fault Diagnosis

An algorithm is developed for computing which sensors to add to meet a diagnosis requirement specification concerning fault detectability and fault isolability. The method is based only on the structural information in a model, which means that possibly large and nonlinear differential–algebraic models can be handled in an efficient manner. The approach is exemplified on a model of an industrial valve where the benefits and properties of the method are clearly shown.      

Design of a real-time AND/OR assembly scheduler on an optimization neural network

The problem of finding an AND/OR precedence-constraint assembly schedule using optimization neural computation is presented. The precedence relationships of assembly operation result from the geometric constraints of subtasks. Because of the existence of geometric constraints among assembly subtasks, the assembly operation involves AND/OR precedence relationships; that is, the order of assembly crucially determines whether the desired task can be achieved. A feasible assembly schedule is a schedule that satisfies these AND/OR precedence constraints.It has been shown that all the feasible assembly schedules can be generated by transforming geometric constraints of subtasks to the pattern-matching operation. Using the question-answer pattern and pattern-matching operation, the assembly scheduling problem can be transformed into an AND/OR precedence-constrained traveling salesman problem (TSP). Two precedence-constrained TSPs, cost-constrained TSP (CCTSP) and state-constrained TSP (SCTSP), are discussed. The CCTSP artificially sets the cost of the prohibited moves to a very large value which ensures that the constraints are satisfied, while the SCTSP restricts the movement of next assembly subtasks. The advantage of the SCTSP over CCTSP in the generation of the assembly schedule will be illustrated.A novel method proposed here is to obtain the best AND/OR precedence-constraint assembly schedule using neural network computation. The geometric constraints of an assembled object are transformed into the elements of the connection matrix which specifies the connection strength among neurons. A modified Hopfield network is used to tackle the AND/OR precedence-constraints assembly scheduling problem. Multirobot assembly sequences generation is also discussed. The designed algorithm can accommodate various constraints and applications. Detailed algorithms, examples and experiments are presented.     

A practical example of the specification of abstract data types

The algebra of quotient relations, a relationally complete set of operations for data base applications, is formally defined in terms of the algebraic specification technique. The process of constructing an algebraic specification for a data type is described in order that future formal definitions are more easily derived. Several improvements to current algebraic presentation techniques are also introduced.     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of “crypt-equivalence” is introduced and studied w.r.t. two “loose” approaches to the semantics of an algebraic specificationT: the class of all first-order models ofT and the class of all term-generated models ofT. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of “first-order crypt-equivalence” if this holds for all first-order models, and of “inductive crypt-equivalence” if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that firstorder crypt-equivalence is equivalent to the existence of explicit definitions and that in case of “positive definability” two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than “abstract semantic equivalence” and that inductive crypt-equivalence is strictly finer than “inductive simulation equivalence” and “implementation equivalence”.     

Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.