Non-Standard Semantics for Program Slicing

In this paper we generalize the notion of compositional semantics to cope with transfinite reductions of a transition system. Standard denotational and predicate transformer semantics, even though compositional, provide inadequate models for some known program manipulation techniques. We are interested in the systematic design of extended compositional semantics, observing possible transfinite computations, i.e. computations that may occur after a given number of infinite loops. This generalization is necessary to deal with program manipulation techniques modifying the termination status of programs, such as program slicing. We include the transfinite generalization of semantics in the hierarchy developed in 1997 by P. Cousot, where semantics at different levels of abstraction are related with each other by abstract interpretation. We prove that a specular hierarchy of non-standard semantics modeling transfinite computations of programs can be specifiedin such a way that the standard hierarchy can be derived by abstract interpretation. We prove that non-standard transfinite denotational and predicate transformer semantics can be both systematically derived as solutions of simple abstract domain equations involving the basic operation of reduced power of abstract domains. This allows us to prove the optimality of these semantics, i.e. they are the most abstract semantics in the hierarchy which are compositional and observe respectively the terminating and initial states of transfinite computations, providing an adequate mathematical model for program manipulation.     

Modal Languages for Coalgebras in a Topological Setting

It is well know that the solution Z of a recursive domain equation, given by an endofunctor T, is the final T-coalgebra. This suggests a coalgebraic approach to obtain a logical representation of the observable properties of Z. The paper considers fibrations of frames and (modal) logics, arising through a set of predicate liftings. We discuss conditions, which ensure expressiveness of the resulting language (denotations of formulas determine a base of the frame over the final coalgebra). The framework is then instantiated with categories of domains, and we establish these conditions for a large class of locally continuous endofunctors. This can be seen as abs1.texa first step towards a final perspective on Abramsky's domain theory in logical form.     

Conformal mapping for the efficient MFS solution of Dirichlet boundary value problems

In this work, we use conformal mapping to transform harmonic Dirichlet problems of Laplace’s equation which are defined in simply-connected domains into harmonic Dirichlet problems that are defined in the unit disk. We then solve the resulting harmonic Dirichlet problems efficiently using the method of fundamental solutions (MFS) in conjunction with fast fourier transforms (FFTs). This technique is extended to harmonic Dirichlet problems in doubly-connected domains which are now mapped onto annular domains. The solution of the resulting harmonic Dirichlet problems can be carried out equally efficiently using the MFS with FFTs. Several numerical examples are presented.      

The numerical solution of a generalized Burgers–Huxley equation through a conditionally bounded and symmetry-preserving method

In this article, we propose a non-standard, finite-difference scheme to approximate the solutions of a generalized Burgers–Huxley equation from fluid dynamics. Our numerical method preserves the skew-symmetry of the partial differential equation under study and, under some analytical constraints of the model constants and the computational parameters involved, it is capable of preserving the boundedness and the positivity of the solutions. In the linear regime, the scheme is consistent to first order in time (due partially to the inclusion of a tuning parameter in the approximation of a temporal derivative), and to second order in space. We compare the results of our computational technique against the exact solutions of some particular initial-boundary-value problems. Our simulations indicate that the method presented in this work approximates well the theoretical solutions and, moreover, that the method preserves the boundedness of solutions within the analytical constraints derived here. In the problem of approximating solitary-wave solutions of the model under consideration, we present numerical evidence on the existence of an optimum value of the tuning parameter of our technique, for which a minimum relative error is achieved. Finally, we linearly perturb a steady-state solution of the partial differential equation under investigation, and show that our simulations still converge to the same constant solution, establishing thus robustness of our method in this sense.     

A Finite Difference Method and Analysis for 2D Nonlinear Poisson–Boltzmann Equations

A fast finite difference method based on the monotone iterative method and the fast Poisson solver on irregular domains for a 2D nonlinear Poisson–Boltzmann equation is proposed and analyzed in this paper. Each iteration of the monotone method involves the solution of a linear equation in an exterior domain with an arbitrary interior boundary. A fast immersed interface method for generalized Helmholtz equations on exterior irregular domains is used to solve the linear equation. The monotone iterative method leads to a sequence which converges monotonically from either above or below to a unique solution of the problem. This monotone convergence guarantees the existence and uniqueness of a solution as well as the convergence of the finite difference solution to the continuous solution. A comparison of the numerical results against the exact solution in an example indicates that our method is second order accurate. We also compare our results with available data in the literature to validate the numerical method. Our method is efficient in terms of accuracy, speed, and flexibility in dealing with the geometry of the domain     

A robust ant colony optimization for continuous functions

Ant colony optimization (ACO) for continuous functions has been widely applied in recent years in different areas of expert and intelligent systems, such as steganography in medical systems, modelling signal strength distribution in communication systems, and water resources management systems. For these problems that have been addressed previously, the optimal solutions were known a priori and contained in the pre-specified initial domains. However, for practical problems in expert and intelligent systems, the optimal solutions are often not known beforehand. In this paper, we propose a robust ant colony optimization for continuous functions (RACO), which is robust to domains of variables. RACO applies self-adaptive approaches in terms of domain adjustment, pheromone increment, domain division, and ant size without any major conceptual change to ACO's framework. These new characteristics make the search of ants not limited to the given initial domain, but extended to a completely different domain. In the case of initial domains without the optimal solution, RACO can still obtain the correct result no matter how the initial domains vary. In the case of initial domains with the optimal solution, we also show that RACO is a competitive algorithm. With the assistance of RACO, there is no need to estimate proper initial domains for practical continuous optimization problems in expert and intelligent systems.     

Numerical Blow-up of Semilinear Parabolic PDEs on Unbounded Domains in ℝ<Superscript>2</Superscript>

We study the numerical solution of semilinear parabolic PDEs on unbounded spatial domains Ω in ℝ² whose solutions blow up in finite time. Of particular interest are the cases where Ω=ℝ² or Ω is a sectorial domain in ℝ². We derive the nonlinear absorbing boundary conditions for corresponding, suitably chosen computational domains and then employ a simple adaptive time-stepping scheme to compute the solution of the resulting system of semilinear ODEs. The theoretical results are illustrated by a broad range of numerical examples.     

Counter-example generation in symbolic abstract model-checking

The boundaries of model-checking have been extended through the use of abstraction. These techniques are conservative, in the following sense: when the verification succeeds, the verified property is guaranteed to hold; but when it fails, it may result either from the non satisfaction of the property, or from a too rough abstraction. In case of failure, it is, in general, undecidable whether an abstract trace corresponding to a counter-example has any concrete counterparts. For debugging purposes, one usually desires to go further than giving a “yes/no” answer (actually, a “yes/don’t know” answer!), and look for such concrete counter-examples. We propose a solution in which we apply standard test-pattern generation technology to search for concrete instances of abstract traces.     

Hybrid Solution Method for Dynamic Programming Equations for MDOF Stochastic Systems

An optimal control problem is considered for a multi-degree-of-freedom (MDOF) system, excited by a white-noise random force. The problem is to minimize the expected response energy by a given time instantT by applying a vector control force with given bounds on magnitudes of its components. This problem is governed by the Hamilton-Jacobi-Bellman, or HJB, partial differential equation. This equation has been studied previously [1] for the case of a single-degree-of-freedom system by developing a hybrid solution. Specifically, an exact analitycal solution has been obtained within a certain outer domain of the phase plane, which provides necessary boundary conditions for numerical solution within a bounded in velocity inner domain, thereby alleviating problem of numerical analysis for an unbounded domain. This hybrid approach is extended here to MDOF systems using common transformation to modal coordinates. The multidimensional HJB equation is solved explicitly for the corresponding outer domain, thereby reducing the problem to a set of numerical solutions within bounded inner domains. Thus, the problem of bounded optimal control is solved completely as long as the necessary modal control forces can be implemented in the actuators. If, however, the control forces can be applied to the original generalized coordinates only, the resulting optimal control law may become unfeasible. The reason is the nonlinearity in maximization operation for modal control forces, which may lead to violation of some constraints after inverse transformation to original coordinates. A semioptimal control law is illustrated for this case, based on projecting boundary points of the domain of the admissible transformed control forces onto boundaries of the domain of the original control forces. Case of a single control force is considered also, and similar solution to the HJB equation is derived.     

The category-theoretic solution of recursive metric-space equations

It is well known that one can use an adaptation of the inverse-limit construction to solve recursive equations in the category of complete ultrametric spaces. We show that this construction generalizes to a large class of categories with metric-space structure on each set of morphisms: the exact nature of the objects is less important. In particular, the construction immediately applies to categories where the objects are ultrametric spaces with ‘extra structure’, and where the morphisms preserve this extra structure. The generalization is inspired by classical domain-theoretic work by Smyth and Plotkin.For many of the categories we consider, there is a natural subcategory in which each set of morphisms is required to be a compact metric space. Our setting allows for a proof that such a subcategory always inherits solutions of recursive equations from the full category.As another application, we present a construction that relates solutions of generalized domain equations in the sense of Smyth and Plotkin to solutions of equations in our class of categories.Our primary motivation for solving generalized recursive metric-space equations comes from recent and ongoing work on Kripke-style models in which the sets of worlds must be recursively defined. We show a series of examples motivated by this line of work.     

Nonmonotonic consequences in default domain theory

Default domain theory is a framework for representing and reasoning about commonsense knowledge. Although this theory is motivated by ideas in Reiter’s work on default logic, it is in some sense a dual framework. We make Reiter’s default extension operator into a constructive method of building models, not theories. Domain theory, which is a well established tool for representing partial information in the semantics of programming languages, is adopted as the basis for constructing partial models. This paper considers some of the laws of nonmonotonic consequence, due to Gabbay and to Kraus, Lehmann, and Magidor, in the light of default domain theory. We remark that in some cases Gabbay’s law of cautious monotony is open to question. We consider an axiomatization of the nonmonotonic consequence relation on prime open sets in the Scott topology – the natural logic – of a domain, which omits this law. We prove a representation theorem showing that such relations are in one to one correspondence with the consequence relations determined by extensions in Scott domains augmented with default sets. This means that defaults are very expressive: they can, in a sense, represent any reasonable nonmonotonic entailment. Results about what kind of defaults determine cautious monotony are also discussed. In particular, we show that the property of unique extensions guarantees cautious monotony, and we give several classes of default structures which determine unique extensions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Numerical Inversion Methods for Computing Approximate p-Values

The paper considers the problem of computing p-values of non-standard distributions for which the characteristic function is available in closed form. When the characteristic function is a multivalued complex function, the standard numerical inversion method needs to be used with care as the integrand may become discontinous due to branch cuts. An alternative inversion method based on the Gaver-Wynn-Rho algorithm is shown to be a general and effective solution to the discontinuity problem as it works with real-valued functions. The method is illustrated with two well-known time series tests with non-standard distributions. JEL classification: C40; C12 An erratum to this article can be found at     

Supporting user views

Any emerging standard for object-oriented database systems must include a rich view support mechanism. A user view is a customized window into an application domain. It may be thought of as a simplifying abstraction which hides information that is not accessible to, needed or wanted by a particular user. Because they limit the information available from a given perspective, most views allow read-only access to a database. In this paper it is asserted that by generalizing object identity to include attributes and views - many view updates are made possible. An extended object structure and several categories of view transformation are also presented which allow all user views to be modeled within a single polymorphic database schema.     

From Term Models to Domains

Let B be the closed term model of the λ-calculus in which terms with the same Böhm tree are identified. We investigate which partial equivalence relations (PERs) on B can be regarded as predomains or domains. Inside the realizability topos on B, such PERs can be regarded simply as sets in a particular model of constructive set theory. No well-behaved partial order has been identified for any class of PERs; but it is still possible to isolate those PERs which have "suprema of chains" in a certain sense, and all maps between such PERs in the model preserve such suprema of chains. One can also define what it means for such a PER to have a "bottom"; partial function spaces provide an example. For these PERs, fixed points of arbitrary endofunctions exist and are computed by the fixed point combinator y. The categories of predomains are closed under the formation of total and partial function spaces, polymorphic types, and convex powerdomains. They in fact form reflective subcategories of the realizability topos; and in this set-theoretic context, these constructions are very simple to describe. We illustrate the theory by discussing an interpretation of PCF, and proving a computational adequacy theorem. None of the usual counterexamples to full abstraction are applicable to our model.     

Rotational quotient procedure: A tracking control continuation method for PDEs on radially symmetric domains

Continuation methods are capable of finding multiform solutions by tracking solution curves. However, these methods may fail to track some desired solution curves due to the interference of the rotational equivalent solutions on a radially symmetric domain. We propose a rotational quotient procedure that applies extra constraints to standard continuation which overcomes this difficulty. We solve a time-independent nonlinear Schrödinger equation on a disk domain to demonstrate the functionality of the proposed method.     

Fokker–Planck approximation of the master equation in molecular biology

The master equation of chemical reactions is solved by first approximating it by the Fokker–Planck equation. Then this equation is discretized in the state space and time by a finite volume method. The difference between the solution of the master equation and the discretized Fokker–Planck equation is analyzed. The solution of the Fokker–Planck equation is compared to the solution of the master equation obtained with Gillespie’s Stochastic Simulation Algorithm (SSA) for problems of interest in the regulation of cell processes. The time dependent and steady state solutions are computed and for equal accuracy in the solutions, the Fokker–Planck approach is more efficient than SSA for low dimensional problems and high accuracy.     

A pattern language for designing e-business architecture

The pattern language for e-business provides a holistic support for developing software architectures for the e-business domain. The pattern language contains four related pattern categories: Business Patterns, Integration Patterns, Application Patterns, and Runtime Patterns. These pattern categories organise an e-business architecture into three layers—business interaction, application infrastructure and middleware infrastructure—and provide reusable design solutions to these layers in a top-down decomposition fashion. Business and Integration Patterns partition the business interaction layer into a set of subsystems; Application Patterns provide a high-level application infrastructure for these subsystems and separate business abstractions from their software solutions; Runtime Patterns then define a middleware infrastructure for the subsystems and shield design solutions from their implementations. The paper describes, demonstrates and evaluates this pattern language.     

Toward Automation for Model-Checking Requirements Specifications with Numeric Constraints

Model-checking techniques have not been effective in important classes of software systems – systems characterised by large (or infinite) input domains with interrelated linear and non-linear constraints over the system variables. Various model abstraction techniques have been proposed to address this problem, but their effectiveness in practice is limited by two factors: first, the abstraction process is manual and requires a great deal of ingenuity; and, second, the abstraction may be coarse and introduce too many spurious behaviours to provide meaningful analysis results. In this paper, we wish to propose domain reduction abstraction based on data equivalence and trajectory reduction as an alternative and complement to other abstraction tech niques. Our technique applies the abstraction to the input domain (environment) instead of the model and is applicable to constraint free and deterministic constrained data transition systems. Our technique is automatable with some minor restrictions. We provide formal proofs for the theoretical soundness of the technique, algorithms for automation, and an illustration of the approach with examples. Correspondence and offprint requests to: Mats P. E. Heimdahl, Department of Computer Science and Engineering, University of Minnesota, 200 Union Street SE, 4-192 Minneapolis, MN 55455, USA. E-mail: heimdahl@cs.umn.edu     

Numerical solution of the two-dimensional Helmholtz equation with variable coefficients by the radial integration boundary integral and integro-differential equation methods

This paper presents new formulations of the boundary–domain integral equation (BDIE) and the boundary–domain integro-differential equation (BDIDE) methods for the numerical solution of the two-dimensional Helmholtz equation with variable coefficients. When the material parameters are variable (with constant or variable wave number), a parametrix is adopted to reduce the Helmholtz equation to a BDIE or BDIDE. However, when material parameters are constant (with variable wave number), the standard fundamental solution for the Laplace equation is used in the formulation. The radial integration method is then employed to convert the domain integrals arising in both BDIE and BDIDE methods into equivalent boundary integrals. The resulting formulations lead to pure boundary integral and integro-differential equations with no domain integrals. Numerical examples are presented for several simple problems, for which exact solutions are available, to demonstrate the efficiency of the proposed methods.