UML has become a standard language for designing software systems. To help software developers design a correct UML model for a software system has become an important goal for many UML CASE tools. We propose a new UML virtual machine based on abstract state machines. We combine the UML meta-model, UML model and user objects model into one under the ASM virtual machine for UML. Since the ASM virtual machine for UML supports OCL, software developers can precisely design a software model and then find some errors such as inconsistency in the model with the help of the ASM virtual machine.

We present combinatorial methods for computing the third support weight enumerators of the five doubly-even, self-dual [32,16,8] codes. The methods exploit relationships that exist between support weight enumerators and complete coset weight enumerators of a self-dual code.

The Unified Modeling Language has become widely accepted as a standard in software development. Several tools have been produced to support UML model validation. However most of them support either static or dynamic model checking; and no tools support to check both static and dynamic aspects of a UML model. But a UML model should include the static and dynamic aspects of a software system. Furthermore, these UML tools translate a UML model into a validation language such as PROMELA. But they have some shortcomings: there is no proof of correctness (with respect to the UML semantics) for these tools. In order to overcome these shortcomings, we present a toolset which can validate both static and dynamic aspects of a model; and this toolset is based on the semantic model using Abstract State Machines. Since the toolset is derived from the semantic model, the toolset is correct with respect to the semantic model.

The Unified Modeling Language has become widely accepted as a standard in software development. Several tools have been produced to support UML model validation. These tools translate a UML model into a validation language such as PROMELA. However they have some shortcomings: there is no proof of correctness (with respect to the UML semantics) for these tools; and there is no tool that supports validation for both the static and dynamic aspects of a UML model. In order to overcome these shortcomings, we present a toolset which is based on the semantic model using abstract state machines. Since the toolset is derived from the semantic model, the toolset is correct with respect to the semantic model. In addition, this toolset can be used to validate both the static and dynamic aspects of a model.

We consider multiprocessing systems where processes make independent, Poisson distributed resource requests with mean arrival time 1. We assume that resources are not released. It is shown that the expected deadlock time is never less than 1, no matter how many processes and resources are in the system. Also, the expected number of processes blocked by deadlock time is one-half more than half the number of initially active processes. We obtain expressions for system statistics such as expected deadlock time, expected total processing time, and system efficiency, in terms of Abel sums. We derive asymptotic expressions for these statistics in the case of systems with many processes and the case of systems with a fixed number of processes. In the latter, generalizations of the Ramanujan Q -function arise. we use singularity analysis to obtain asymptotics of coefficients of generalized Q -functions.

Existential least fixpoint logic (ELFP) is a logic with a least fixpoint operator but only existential quantification. It arises in many areas of computer science including logic programming, database theory, program verification, complexity theory, and recursion theory on abstract structures. A sequent calculus (Gentzen-style deductive system) for this logic is presented and proved to be complete. Basic model theoretic facts about ELFP are derived from the completeness theorem and the construction used in its proof. The relationship of these model theoretic facts to logic programming and database queries is explored.

The optimization of a large class of queries is explored, using a powerful normal form recently proven. The queries include the fixpoint and while queries, and an extension of while with arithmetic. The optimization method is evaluated using a probabilistic analysis. In particular, the average complexity of fixpoint and while is considered and some surprising results are obtained. They suggest that the worst-case complexity is sometimes overly pessimistic for such queries, whose average complexity is often much more reasonable than the provably rare worst case. Some computational properties of queries are also investigated. A probabilistic notion of boundedness is defined, and it is shown that all programs in the class considered are bounded almost everywhere. An effective way of using this fact is provided.

An algebra and a logic characterizing the complexity class NC/sup 1/, which consists of functions computed by uniform sequences of polynomial-size, log depth circuits, are presented. In both characterizations, NC/sup 1/ functions are regarded as functions from one class of finite relational structures to another. In the algebraic characterization, upward and downward tree recursion are applied to a class of simple functions. In the logical characterization, first-order logic is augmented by an operator for defining relations by primitive recursion. It is assumed that every structure has an underlying relation giving the binary representations of integers.>

Problems of computing probabilities of statements about large, finite structures have become an important subject area of finite combinatorics. Within the last two decades many researchers have turned their attention to such problems and have developed a variety of methods for dealing with them. Applications of these ideas include nonconstructive existence proofs for graphs with certain properties by showing the properties occur with nonzero probabilities (for examples see Erdös and Spencer [ES] and Bollobás [Bo]), and determination of average running times for sorting algorithms by computing asymptotic probabilities of statements about permutations (see Knuth [Kn]). Two types of techniques recur in solutions to such problems: probabilistic techniques, such as those used by Erdös and Spencer [ES], and classical assymptotic techniques, such as those surveyed by Bender [Be] and de Bruijn [Br]. Studying this body of techniques, one notices that characteristics of these problems suggest certain methods of solution, in much the same way that the form of an integrand may suggest certain substitutions. The question arises, then, as to whether there is a systematic way to approach these problems: is there an algorithm for computing asymptotic probabilities? I will show that the answer is “no”—for any reasonable formulation, the problem of computing asymptotic probabilities is undecidable. The main theorem of the paper is Theorem 1.6, which says that there is a finitely axiomatizable class in which every first order sentence has an asymptotic probability of 0 or 1—i.e., is almost always true or almost always false in finite structures—but for which the problem of deciding whether a sentence has asymptotic probability 0 or 1 is undecidable. Heretofore, classes known to have such a 0-1 law have had decidable asymptotic probability problems (see Lynch [Ly] for examples and a discussion of previous work in the area).

The study of preservation theorems for first order logic was the focus of much research by model theorists in the 1960's. These theorems, which came to form the foundation for classical model theory, characterize first order sentences and theories that are preserved under operations such as the taking of unions or submodels (see Chang and Keisler [5] for a discussion of preservation theorems for first order logic). In current model theoretic research, logics richer than first order logic and applications of logic to other parts of mathematics have assumed the central position. In the former area, preservation theorems are not so important; in the latter, especially in applications to algebra, many of the techniques developed for proving these theorems have been useful. In this paper I prove several preservation theorems for first order logic which I discovered while investigating the asymptotic growth of classes of finite combinatorial structures. The significance of these theorems lies in their applications to problems in finite combinatorics. Since the applications require combinatorial and analytical techniques that are not pertinent to logical questions discussed here, I shall present them in another paper [7].