A Rewriting Logic Approach to Operational Semantics (Extended Abstract)

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, and continuation-based semantics. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

A rewriting logic approach to operational semantics

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, continuation-based semantics, and the chemical abstract machine. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

Using logic to solve the submodule construction problem

Submodule construction is the problem of finding a new submodule which, together with a given submodule, provides a behavior that conforms to a given desired global behavior. A new formulation of this problem and its solution in first-order logic is presented, and it is shown how the known solutions to this problem in the context of various communication paradigms and specification formalisms can be derived. Communication paradigms are: synchronous rendezvous at several interfaces; interleaved rendezvous; input/output automata with complete or partial behavior specifications and with synchronous or interleaved communication. A new algorithm for deriving a progressive solution is also presented.     

On the design and specification of message oriented programs

Processes are building blocks for the modeling of environments in which parallel and distributed processing occurs. In parallel programming they play the role of standard units (as do subroutines or procedures in sequential programming). Process communication and synchronization can be achieved either through shared variables (common address space) or by message transmission. It has been shown that the message transmission mechanism leads to a more general computational structure. In this paper we develop the beginnings of a methodology to deal with what we call message oriented programming. We note in passing that the methodology for programming with shared variables is well developed and shows a development leading from operational (automata oriented) constructs (semaphores) to high level programming constructs (critical regions and then monitors). Recent mathematical theories of message oriented programming deal with the subject from an operational point of view. However, the models are too far removed from the control and data structures of programs to guide the designer in constructing a process. To be able to bridge this gap between program specification and program implementation (expressed in the high level language that we use), we resort to a definitional specification technique based on the concept of abstract data type. The specification technique is used in conjunction with some useful design principles to illustrate our ideas via solutions to well-known problems. The two main principles we discuss are: differences (and needs) for definitions of process and message structures in a given application and the concepts of module strength and module coupling as put forward by Myers. Finally, we illustrate how the high level definitional technique leads us to a straightforward method for studying some properties of message oriented programs. We give an example of proving the deadlock freeness of a solution to the consumer and producer problem.This work was supported by a research grant (to C. J. Lucena) from the J. S. Guggenheim Memorial Foundation and also by the Natural Sciences and Engineering Research Council of Canada.     

A new operational matrix for solving fractional-order differential equations

Fractional calculus has been used to model physical and engineering processes that are found to be best described by fractional differential equations. For that reason we need a reliable and efficient technique for the solution of fractional differential equations. This paper deals with the numerical solution of a class of fractional differential equations. The fractional derivatives are described in the Caputo sense. Our main aim is to generalize the Legendre operational matrix to the fractional calculus. In this approach, a truncated Legendre series together with the Legendre operational matrix of fractional derivatives are used for numerical integration of fractional differential equations. The main characteristic behind the approach using this technique is that it reduces such problems to those of solving a system of algebraic equations thus greatly simplifying the problem. The method is applied to solve two types of fractional differential equations, linear and nonlinear. Illustrative examples are included to demonstrate the validity and applicability of the presented technique.     

Hybrid Legendre polynomials and Block-Pulse functions approach for nonlinear Volterra–Fredholm integro-differential equations

This paper introduces an approach for obtaining the numerical solution of the nonlinear Volterra–Fredholm integro-differential (NVFID) equations using hybrid Legendre polynomials and Block-Pulse functions. These hybrid functions and their operational matrices are used for representing matrix form of these equations. The main characteristic of this approach is that it reduces NVFID equations to a system of algebraic equations, which greatly simplifying the problem. Numerical examples illustrate the validity and applicability of the proposed method.     

Economically optimal batch diafiltration via analytical multi-objective optimal control

This paper studies the problem of economically oriented optimal operation of batch membrane diafiltration processes that are designed to concentrate the valuable components of the solution and to purge the impurities from it. We consider a complex economical objective that accounts for the total operational costs comprising a cost of consumed diluant, costs related to duration of processing, and a cost of product loss. The optimization problem is formulated as a multi-objective optimal control problem in order to investigate the impact of operational cost factors on optimal operation policy. This is achieved thanks to the use of the analytical approach that exploits Pontryagin's minimum principle. We show that the economically optimal control strategy is to carry out an operation involving saturated (bang-bang or constraint-tracking) control modes and a singular arc. For the most common cases of diafiltration problems, it turns out that the switching of the consecutive control modes can be realized in the state feedback fashion, i.e. the entire optimal operation is defined analytically in the space of process states. We demonstrate the applicability of the presented approach and we illustrate achievable benefits, over traditional control methods for the batch diafiltration processes, on two case studies taken from the literature.     

CASE-BASED REASONING IN ENVIRONMENTAL MONITORING APPLICATIONS

Environmental monitoring is usually based on large volumes of data, while in general, environmental decision making is a complex problem, has a high degree of uncertainty, and involves diverse areas of expertise. Environmental decision-support systems are therefore good candidates for application of artificial intelligence (AI) techniques. In this paper it is argued that a suitable approach for building these systems is the use of case-based reasoning or analogical reasoning techniques, which offer more adaptability and better explanation facilities than other AI paradigms. As an example, the development stages, the architecture, and the operational characteristics of the expert system Air Quality Predictor (AIRQUAP), developed to predict air pollution levels in Athens, Greece, are described. AIRQUAP helps users retrieve historical data intelligently and can predict air pollution levels, useful for management of air pollution episodes. The performance of the system is also compared with other techniques used in this class of applications.     

Efficiency of local models ensembles for time series prediction

Many current technological challenges require the capacity of forecasting future measurements of a phenomenon. This, in most cases, leads directly to solve a time series prediction problem. Statistical models are the classical approaches for tackling this problem. More recently, neural approaches such as Backpropagation, Radial Basis Functions and recurrent networks have been proposed as an alternative. Most neural-based predictors have chosen a global modelling approach, which tries to approximate a goal function adjusting a unique model. This philosophy of design could present problems when data is extracted from a phenomenon that continuously changes its operational regime or represents distinct operational regimes in a unbalanced manner. In this paper, two alternative neural-based local modelling approaches are proposed. Both follow the divide and conquer principle, splitting the original prediction problem into several subproblems, adjusting a local model for each one. In order to check their adequacy, these methods are compared with other global and local modelling classical approaches using three benchmark time series and different sizes (medium and high) of training data sets. As it is shown, both models demonstrate to be useful pragmatic paradigms to improve forecasting accuracy, with the advantages of a relatively low computational time and scalability to data set size.     

改良填充法实现和解决迷宫问题

与传统的“回溯“法相比,用填充法解决迷宫问题具有节约空间、提高效率的优点.本文探讨了填充法实现过程中的若干操作层面的问题,例如:如何快速扫描所有死路,如何解决单一出口的环路问题,如何填充稀疏空地等,提出了改良填充法,最后给出了用改良填充法解决迷宫问题的C程序.     

改良填充法实现和解决迷宫问题

与传统的“回溯”法相比,用填充法解决迷宫问题具有节约空间、提高效率的优点。本文探讨了填充法实现过程中的若干操作层面的问题,例如：如何快速扫描所有死路,如何解决单一出口的环路问题,如何填充稀疏空地等,提出了改良填充法,最后给出了用改良填充法解决迷宫问题的C程序。     

A decentralized model for flow shop production with flexible transportation system

The recent advances in technology sectors often clash with traditional organizational paradigms which can limit or make difficult an efficient implementation in the real world. In this paper we show how it is possible to exploit the advantages of innovative technologies in manufacturing when these are supported by new and efficient methods for production management. More in details, we face a flow shop scheduling problem in a shoe manufacturing system in which overtaking of jobs is allowed thanks to an innovative transportation system. Overtaking means that a job can be put in waiting state and another job can surpass it, allowing the change of the scheduling sequence. Preemption is not allowed. The objective function of the problem is the minimization of the maximum lateness. We propose a decentralized model, based on multi-agent system theory, to represent the production cells of the plant and to include the potentiality offered by overtaking of jobs at decisional level. The adoption of a decentralized approach increases the system flexibility since each machine is able to solve its local scheduling problem. Adding or removing machines to the plant will not imply a change in the scheduling algorithms. The outcomes of this work are reached firstly through a formulation of the problem with three flow shop scheduling models, secondly through a comparison of the models with respect to different performance indicators. The results highlight as the decentralized approach is able to reach comparable performances with the centralized one for a relevant number of instances. Moreover sensitivity analysis shows as in the decentralized model the computational time required to solve bigger instances increases less quickly than in the case of centralized ones. Finally, simulations of the decentralized approach clarify as the correlation of the local solution procedure is effected by the number of machines of the flow shop and the coordination mechanism is effected by the number of the jobs to be scheduled.     

Exploiting design information to derive object distribution models

Object-orientation and distributed systems are quickly becoming norms for new system development, generating renewed interest in distribution schemes traditionally directed at relational databases. Though a number of facilitating technologies, such as EJB, COM, or CORBA, are available, pragmatic, and rigorous approaches for effective distribution are still lacking. In this paper, we develop an approach for deriving object distribution models by exploiting design information. The approach exploits information realistically available during the design stage, without requiring guesstimates of operational parameters. It spans multiple layers, mappings across which may be adjusted depending upon changes in assumptions and operational conditions to create specific models. We demonstrate the approach by operationalizing it to create a model for object distribution in closely coupled client/server configurations. The detailed model we demonstrate, therefore, represents one specific instantiation of our approach. The model is accompanied by a decision support procedure that assists the designer in the search for a satisficing solution in the resulting combinatorial multiple criteria problem. We briefly describe a research prototype that served as proof-of-concept and demonstrate usefulness based on an analysis of results obtained for distribution of a real-world object-oriented application.     

算法框架:算法重定位的一种可操作的方法

算法框架是实现算法重定位的一种可操作的方法.文章给出了算法重定位的定义,讨论了如何通过选择操作和组合操作来设计算法框架.然后给出了定义选择操作和组合操作的一种方法.由文章所定义的算法框架得到求解某一问题的算法模式,从该算法模式就可以生成求解该问题的算法.文章最后讨论了算法框架和算法模式以及模块化算法之间的关系.研究算法重定位及其可操作的方法对软件自动化和机器学习有着重要的意义.     

Quantity of material handling equipment—A queuing theory based approach

In this paper, we discuss the development of a two step analytical approach to determine the quantity of material handling equipment (MHE) required for effective handling of products among facilities. In the first step, a preliminary solution is obtained by considering the time required for loading and unloading of products, loaded travelling, empty travelling and breakdown of MHE. A detailed model, which integrates both operational and cost performance factors such as utilisation of MHE, work-in-process at the MHS and life-cycle cost, is then utilised to rank alternatives that are generated from the preliminary solution. The stochastic nature of a manufacturing system, which is not adequately addressed in the literature, is best modelled using queuing theory. An illustrative problem is given, and it is shown that for all the considered problems our approach outperforms the existing methods. The influence of various other factors including the operational characteristics of processing facilities, layout design, maintenance function, MHE speed and batch size in selection of the quantity of MHE is also demonstrated. Thus we show the significance of our proposed approach and its capability to support an integrated decision making process.     

Hybrid

Combining higher-order abstract syntax and (co)-induction in a logical framework is well known to be problematic. We describe the theory and the practice of a tool called Hybrid, within Isabelle/HOL and Coq, which aims to address many of these difficulties. It allows object logics to be represented using higher-order abstract syntax, and reasoned about using tactical theorem proving and principles of (co)induction. Moreover, it is definitional, which guarantees consistency within a classical type theory. The idea is to have a de Bruijn representation of λ-terms providing a definitional layer that allows the user to represent object languages using higher-order abstract syntax, while offering tools for reasoning about them at the higher level. In this paper we describe how to use Hybrid in a multi-level reasoning fashion, similar in spirit to other systems such as Twelf and Abella. By explicitly referencing provability in a middle layer called a specification logic, we solve the problem of reasoning by (co)induction in the presence of non-stratifiable hypothetical judgments, which allow very elegant and succinct specifications of object logic inference rules. We first demonstrate the method on a simple example, formally proving type soundness (subject reduction) for a fragment of a pure functional language, using a minimal intuitionistic logic as the specification logic. We then prove an analogous result for a continuation-machine presentation of the operational semantics of the same language, encoded this time in an ordered linear logic that serves as the specification layer. This example demonstrates the ease with which we can incorporate new specification logics, and also illustrates a significantly more complex object logic whose encoding is elegantly expressed using features of the new specification logic.