An abstract business process contains a description the protocol that a business process engages in without revealing the internal computation of the process. This description provides the information necessary to compose the process with other Web services. BPEL supports this by providing distinct dialects for specifying abstract and executable processes. Unfortunately, BPEL does not prevent complex computations from being included in an abstract process. This complicates the protocol description, unnecessarily reveals implementation details, and makes it difficult to analyze correctness. We propose some restrictions on the data manipulation constructs that can be used in an abstract BPEL process. The restrictions permit a full description of a protocol while hiding computation. A restricted abstract process can easily be converted into an abstract BPEL process or expanded into an executable BPEL process. Based on these restrictions we propose a formal model for a business process and use it as the basis of an algorithm for demonstrating the process. We then sketch an algorithm for synthesizing a protocol based on a formal specification of its outcome and the tasks available for its construction.

We introduce a logic model to formally specify the semantics of workflows and their composite tasks described as BPEL4WS abstract processes. Based on the model, we present a set of inference rules to deduce the strongest postcondition and weakest precondition of a workflow and demonstrate that automatic workflow verification is possible due to the restrictions on data manipulation in an abstract process. We then sketch an algorithm that automatically synthesizes a workflow given its specification and a task library.

Many transaction processing applications execute at isolation levels lower than SERIALIZABLE in order to increase throughput and reduce response time. However, the resulting schedules might not be serializable and, hence, not necessarily correct. The semantics of a particular application determines whether that application will run correctly at a lower level and, in practice, it appears that many applications do. The decision to choose an isolation level at which to run an application and the analysis of the correctness of the resulting execution is usually done informally. We develop a formal technique to analyze and reason about the correctness of the execution of an application at isolation levels other than SERIALIZABLE. We use a new notion of correctness, semantic correctness, a criterion weaker than serializability, to investigate correctness. In particular, for each isolation level, we prove a condition under which the execution of transactions at that level will be semantically correct. In addition to the ANSI/ISO isolation levels of READ UNCOMMITTED, READ COMMITTED, and REPEATABLE READ, we also prove a condition for correct execution at the READ-COMMITTED with first-committer-wins and at SNAPSHOT isolation. We assume that different transactions in the same application can be executing at different levels, but that each transaction is executing at least at READ UNCOMMITTED.

Many transaction processing applications execute at isolation levels lower than serializable in order to increase throughput and reduce response time. The problem is that non-serializable schedules are not guaranteed to be correct for all applications. The semantics of a particular application determines whether that application will run correctly at a lower isolation level, and in practice it appears that many applications do. Unfortunately, we know of an analysis technique that has been developed to test an application for its correctness at a particular level. Apparently decisions of this nature are made on an informal basis. In this paper we describe such a technique in a formal way. We use a new definition of correctness, semantic correctness, which is weaker than serializability, to investigate the correctness of such executions. For each isolation level, we prove a condition under which transactions that execute at that level will be semantically correct. In addition to the ANSI/ISO isolation levels of read uncommitted, read committed, and repeatable read, we also prove a condition for correct execution at the read committed with first-committer-wins (a variation of read committed) and at the snapshot isolation level. We assume that different transactions can be executing at different isolation levels, but that each transaction is executing at least at the read uncommitted level.

Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. Serializable execution is generally implemented using a two phase locking algorithm that locks items in the database to delay transactions that care in danger of performing in a nonserializable fashion. Such delays are unacceptable in high performance database systems and in systems supporting long running transactions. A number of models have been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. A shortcoming of much of this work is that little guidance is provided as to how transactions should be decomposed and what interleavings preserve correct execution. We previously proposed a new correctness criterion, weaker than serializability, that guarantees that each transaction satisfies its specification (A. Bernstein and P. Lewis, 1996). Based on that correctness criterion, we have designed and implemented a new concurrency control. Experiments using the new concurrency control demonstrate significant improvement in performance when lock contention is high.

The main results of this paper show that serialization is both necessary and sufficient for consistency in concurrent database systems. This is true for both the final database and the views of the database seen by individual transactions. The model of a transaction includes both read and write operations which may be performed in any order (except an entity must be read before being written). The main results are presented in terms of an information flow model describing the source of each value read and the use of each value written. Since the model does not involve any concept of the “time” a value was read or written, it models any concurrency system producing information flow among transactions. There is a section discussing the effect of changing the model to include write operations without preceding reads, and a section discussing the restriction to straight-line programs.

Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any $n\geqq 8$, there are traveling salesman problems with n nodes having tours which cannot be improved by making $n/4$ edge changes, but for which the ratio is $2(1-1/n)$.

The two volumes in this set belong in every library on compiler design. Together they achieve a level of rigor and completeness not attained by any other book on the subject.

Attributed translations are a means of specifying the input-output relation of a language processing device, such as for example the lexical or syntax box of a compiler. Considered as a mathematical object, an attributed translation is a mapping of certain strings of attributed “input symbols” into strings of attributed “action symbols”. Under the interpretation that action symbols represent the act of emitting an attributed output or the performing of some other “semantic actions”, and the attributes represent “semantic” information associated with the symbols, the model can be applied in depth to practical compiling problems. Theorems are proved giving conditions under which an attributed translation can be performed by an augmented pushdown machine while it is parsing top down or bottom up.

A transduction is a mapping from one set of sequences to another. A syntax-directed transduction is a particular type of transduction which is defined on the grammar of a context-free language and which is meant to be a model of part of the translation process used in many compilers. The transduction is considered from an automata theory viewpoint as specifying the input-output relation of a machine. Special consideration is given to machines called translators which both transduce and recognize. In particular, some special conditions are investigated under which syntax-directed translations can be performed on (deterministic) pushdown machines. In addition, some time bounds for translations on Turing machines are derived.

The adaptive single threshold gate realization procedure, originally proposed by Rosenblatt, has been rather extensively studied, and several upper bounds on the number of corrections required for its convergence have been derived. In this note a lower bound on the number of required corrections is determnined, and shown to differ from the upper bound by a factor of about n2where n is the number of binary variables. This new bound then implies the existence of classes of linearly separable functions for which the number of required corrections increases exponentially with n.

During the past few years there has been a considerable amount of literature concerned with the realization of threshold logic. However, there are a number of questions concerning such factors as sensitivity and component savings which cannot be completely answered by such theoretical studies. DONUT (Digitally Operated Network Using Thresholds) is a small general purpose digital computer which was designed and constructed to evaluate the feasibility of using threshold gates as the basic logical element. Exclusive of memory the computer consists of about 500 threshold gates. The design was carried out for five different values of component tolerances and the tightest tolerance version was constructed. Component savings for the constructed machine are about a factor of four compared with the loosest tolerance NOR gate realization. Experiments were made to verify that the power supply and logical voltages were within tolerances in the system environment.

One engineering parameter of importance in the realization of threshold gate networks is the tolerance which must be placed on the coefficients and threshold of the individual components. A previous paper gives a realization procedure which allows this tolerance to be controlled. The present paper gives an alternate realization procedure which also allows the tolerance to be controlled, but which is somewhat different in its application. The new procedure can be considered to be a generalization of an earlier procedure for the single-element realization problem. The function is first decomposed using a generalization of the function tree and then reconstructed using a generalization of the range theorem plus some additional simplification theorems.

In the realization of a logical function by a network of threshold components, one important engineering parameter is the tolerances which must be placed on the coefficients and threshold of the individual components. For threshold gates in which the logical ``zero'' corresponds to a constant signal of zero value and in which the coefficients are all positive or all negative, these tolerances are functions only of the gap boundaries of the map realized by the component. A set of theorems is presented that define ``algebraic-like'' operations which provide a means for performing a sequence of symbolic operations on the desired logical function whereby the latter is transformed into a description of a network of threshold components which is its realization. Using these theorems a procedure is given for realizing an arbitrary logical function as a network of threshold components with specified sensitivity.

A previous paper gives a procedure for the testing and realization of linearly-separable switching functions, i.e., functions which can be realized by a single threshold component. That procedure can be considerably simplified, particularly when the given function is symmetric in sets of two or more variables. The simplifications arise due to a reduction of the number of functions in the function tree in view of the coefficient ordering. Although this procedure was derived with the aim of reducing the amount of computation below that required for straightforward solution of the simultaneous inequalities that define the problem, the resulting method has some interesting relationships to that due to Winder.

Design of pattern recognition systems usually involves a number of uncertainties which can be resolved only by experiment. In statistical recognition systems, pattern information is stored in the machine in the form of pattern characteristics with statistics relating the characteristics to the patterns. If the number of characteristics a system can process is limited, and if the system designer, while able to conceive of a large number of relevant characteristics, does not know which are the most important, then an experimental selection of these characteristics is required. As tools, the designer may have at his disposal a large computer, a large sample of the patterns to be recognized, and a set of programs to measure the characteristics. Thus, he can compare certain statistics relating the patterns to the characteristics. The problem is: what statistics should he calculate in order to select the best characteristics? Assuming the characteristics to be independent in their effect on the decision, this paper examines the notion of a single number statistic for each characteristic which would have certain desirable properties related to the "goodness" of the characteristic. It is shown that, in general, no such statistic exists. However, a statistic is proposed which, while not having these properties in general, at least has them in a wide range of situations. An experimental study of the validity of this choice is reported together with the design of a letter recognition system. Using a sample of 15 complete 62 symbol alphabets, 13 characteristics were selected. The resulting system recognized correctly 81.9% of the letters presented to it.