In this paper we develop a variant, regenerative randomization with Laplace transform inversion, of a previously proposed method (the regenerative randomization method) for the transient analysis of rewarded continuou...
详细信息
In this paper we develop a variant, regenerative randomization with Laplace transform inversion, of a previously proposed method (the regenerative randomization method) for the transient analysis of rewarded continuous time Markov models. Those models find applications in dependability and performability analysis of computer and telecommunication systems. The variant differs from regenerative randomization in that the truncated transformed model obtained in that method is solved using a Laplace transform inversion algorithm instead of standard randomization. As regenerative randomization, the variant requires the selection of a regenerative state on which the performance of the method depends. For a class of models, class C', including typical failure/repair models, a natural selection for the regenerative state exists and, with that selection, theoretical results are available assessing the performance of the method in terms of 'visible' characteristics. Using dependability class C' models of moderate size of a RAID 5 architecture we compare the performance of the variant with those of regenerative randomization and randomization with steady-state detection for irreducible models, and with those of regenerative randomization and standard randomization for models with absorbing states. For irreducible models, the new variant seems to be about as fast as randomization with steady-state detection for models which are not too small when the initial probability distribution is concentrated in the regenerative state, and significantly faster than regenerative randomization when the model is stiff and not very large. For stiff models with absorbing states, the new variant is much faster than standard randomization and significantly faster than regenerative randomization when the model is not very large. In addition, the variant seems to be able to achieve stringent accuracy levels safely.
Program analyses are often presented as one of two brands: forwards or backwards. In this paper we explore the significance of the direction of analysis, and show how arbitrary abstract interpretations may be reversed.
Program analyses are often presented as one of two brands: forwards or backwards. In this paper we explore the significance of the direction of analysis, and show how arbitrary abstract interpretations may be reversed.
It is shown that regular relations, which arise in a number of areas of programming theory, can be characterised in a variety of ways as pullbacks in Jet;and up to isomorphism, as bicartesian squares in Jet.
It is shown that regular relations, which arise in a number of areas of programming theory, can be characterised in a variety of ways as pullbacks in Jet;and up to isomorphism, as bicartesian squares in Jet.
In this paper we propose a calculus for reasoning about concurrent programs inspired by the wp calculus for reasoning about sequential programs. The calculus uses a small set of familiar rules for dealing with safety,...
详细信息
In this paper we propose a calculus for reasoning about concurrent programs inspired by the wp calculus for reasoning about sequential programs. The calculus uses a small set of familiar rules for dealing with safety, progress and parallel composition. A contribution of this paper is to demonstrate how predicate calculus in general, and predicate transformers in particular, can be used to reason about concurrent programs in which fairness plays a critical role.
The paper provides an introduction to a natural-deduction-based set theory, NaDSet, and illustrates its use in programming semantics. The need for such a set theory for the development of programming semantics is moti...
详细信息
The paper provides an introduction to a natural-deduction-based set theory, NaDSet, and illustrates its use in programming semantics. The need for such a set theory for the development of programming semantics is motivated by contrasting the presentation of recursive definitions within first-order logic with their presentation within NaDSet. Within first-order logic such definitions are always incomplete in a very simple sense: Induction axioms must be added to the given definitions and extended with every new recursive definition. Within a set theory such as NaDSet. recursive definitions of sets are represented as terms in the theory and are complete, in the sense that all properties of the set can be derived from its definition. Such definitions not only have this advantage of completeness, but they also permit recursively defined sets to be members of the universe of discourse of the logic and thereby be shown to be members of other defined sets. The presentation of the semantics within NaDSet is not only fully formal, in contrast to the simply mathematical presentation of denotational semantics. but because NaDSet is formalized as a natural-deduction logic, computer-assisted proof constructions are plausible. A consistency proof for NaDSet is provided elsewhere. The resolution of the paradoxes provided by NaDSet is dependent upon replacing the naive comprehension axiom scheme of an inconsistent first-order set theory with natural-deduction rules for the introduction of abstraction terms into arguments. The abstraction terms admitted are a generalization of the abstraction terms usually admitted into set theory. In order to avoid a confusion of use and mention, the nominalist interpretation of the atomic formulas of the logic forces NaDSet to be second-order, although only a single kind of quantifier and variable is required.
The categorical semantics of (an abstract version of) the general term graph rewriting language DACTL is investigated. The operational semantics is reformulated in order to reveal its universal properties. The technic...
详细信息
The categorical semantics of (an abstract version of) the general term graph rewriting language DACTL is investigated. The operational semantics is reformulated in order to reveal its universal properties. The technical dissonance between the matchings of left-hand sides of rules to redexes, and the properties of rewrite rules themselves, is taken as the impetus for expressing the core of the model as a Grothendieck opfibration of a category of general rewrites over a base of general rewrite rules. Garbage collection is examined in this framework in order to reconcile the treatment with earlier approaches. It is shown that term rewriting has particularly good garbage-theoretic properties that do not generalise to all cases of graph rewriting and that this has been a stumbling block for aspects of some earlier models for graph rewriting.
Given a term-rewriting system R, a term t is ground-reducible by R if every ground instance tsigma of it is R-reducible. A pair (t, s) of terms is ground-co--reducible by R if every ground instance (tsigma, ssigma] of...
详细信息
Given a term-rewriting system R, a term t is ground-reducible by R if every ground instance tsigma of it is R-reducible. A pair (t, s) of terms is ground-co--reducible by R if every ground instance (tsigma, ssigma] of it for which tsigma and ssigma are distinct is R-reducible, Ground (co-)reducibility has been proved to be the fundamental tool for mechanizing inductive proofs, together with the Knuth-Bendix completion procedure presented by Jouannaud and Kounalis (1986, 1989). Jouannaud and Kounalis (1986. 1989) also presented an algorithm for testing ground reducibility which is tractable in practical cases but restricted to left-linear term-rewriting systems. The solution of the ground (co-)reducibility problem, for the general case, turned out to be surprisingly complicated. Decidability of ground reducibility for arbitrary term-rewriting systems has been first proved by Plaisted (1985) and independently by Kapur et al. (1987). However, the algorithms of Plaisted and Kapur et al. amount to intractable computation, even in very simple cases. We present here a new algorithm for the general case which outperforms the algorithms of Plaisted and Kapur et al. and even our previous algorithm in case of left-linear term-rewriting systems. We then show how to adapt it to check for ground co-reducibility.
Given a collection of points in the plane, one may draw a cell around each point in such a way that each point's cell is the portion of the plane consisting of all locations closer to that point than to any of the...
详细信息
Given a collection of points in the plane, one may draw a cell around each point in such a way that each point's cell is the portion of the plane consisting of all locations closer to that point than to any of the other points. The resulting geometric figure is called a Dirichlet tessellation. An algorithm for obtaining the boundaries of the cells given the points was derived by Green and Sibson in 1978. Here, methods are described for obtaining the locations of the points, given only the cell boundaries.
Given a specification that includes a number of user requirements, we wish to focus on the requirements in turn, and derive a partly defined program for each;then combine all the partly defined programs into a single ...
详细信息
Given a specification that includes a number of user requirements, we wish to focus on the requirements in turn, and derive a partly defined program for each;then combine all the partly defined programs into a single program that satisfies all the requirements simultaneously. In this paper we introduce a mathematical basis for solving this problem, and we illustrate it by means of a simple example.
We describe a programming methodology for computational science based on programming paradigms for multicomputers. Each paradigm is a class of algorithms that have the same control structure. For every paradigm, a gen...
详细信息
We describe a programming methodology for computational science based on programming paradigms for multicomputers. Each paradigm is a class of algorithms that have the same control structure. For every paradigm, a general parallel program is developed. The general program is then used to derive two or more model programs, which solve specific problems in science and engineering. These programs have been tested on a Computing Surface and published with every detail open to scrutiny. We explain the steps involved in developing model programs and conclude that the study of programming paradigms provides an architectural vision of parallel scientific computing.
暂无评论