Search

An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equal lengths denoted by 1. Compared to parallel machines, uniform machines are more difficult to deal with because they have different processing speeds. There are two types of machines in our model. The lower bound on the competitive ratio is characterized by some complicated algebraic equations. And a best possible on-line algorithm matching the lower bound is constructed and proved in this paper. [ABSTRACT FROM AUTHOR]

Let D be a Scott-domain and [ D → c D ] (resp., [ D → s D ] ) its conditionally multiplicative (CM for short) (resp., stable) function space. Zhang (1996) [19] mentioned that if [ D → c D ] is bounded complete, D should be distributive. In the first part of this paper, we prove that if [ D → c D ] or [ D → s D ] is bounded complete, then D is distributive, which confirms that his conjecture is true. Amadio (1991) [3] and Curien (1998) [4] raised the question of whether the category of stable bifinite domains ( SB for short) in sense of Amadio–Droste is the largest Cartesian closed full subcategory of the category of ω -algebraic meet-cpos with CM functions ( ω - SAM for short). In the second part of this paper, we prove that for any ω -algebraic meet-cpo D and certain non-distributive finite poset M ˜ , if [ D → c M ˜ ] , [ [ D → c M ˜ ] → c [ D → c M ˜ ] ] and [ [ [ D → c M ˜ ] → c M ˜ ] → c [ [ D → c M ˜ ] → c M ˜ ] ] are ω -algebraic, then we have that (1) D is finitary; (2) if D is not stable bifinite, then [ [ D → c M ˜ ] → c [ D → c M ˜ ] ] is not finitary. So, the category SB is a maximal Cartesian closed full subcategory of ω - SAM , which gives a partial solution to the problem posed by Amadio and Curien. [ABSTRACT FROM AUTHOR]

Research involving artificial neural networks has tended to be driven towards efficient computation, especially in the domain of pattern recognition, or towards elucidating biological processes in the brain. Models have become more detailed as our understanding of the biology of the brain has increased, incorporating real-time behaviour of individual neurons interacting within complex system structures and dynamics. There are few examples of abstract and fully formal models of biologically plausible neural networks: in the neural networks literature models are often presented as a mixture of mathematical equations and natural language, supported by simulation code and associated experimental results. The informality often hides or obscures important aspects of a particular model, and leaves a large conceptual gap between the model descriptions and the usually low-level programming code used to simulate them. The main contribution of this paper is formally modelling and analysing a biologically plausible neural network model from the literature that exhibits complex neuron-level behaviour and network-level structure. To achieve this a modelling language ‘Pann’ is developed, based on the process algebras CSP and Hybrid χ . It is designed to be convenient for mixing the behaviour of discrete events (such as a neuron spike) with mutable continuous and discrete variables (representing chemical properties of a neuron, for instance). Its behaviour is defined using an operational semantics, from which a set of general properties of the language is proved. The groundwork for the biological model is laid by first formalising some well-known concepts from the artificial neural networks domain, such as feedforward behaviour, backpropagation, and recurrent neural networks. The Pann model of a feedforward network, comprising a set of communicating processes representing individual neurons, is proved equivalent to the standard one-line calculation of feedforward behaviour. [ABSTRACT FROM AUTHOR]

In a recent work, Gandhi, Khoussainov, and Liu [7] introduced and studied a generalized model of finite automata able to work over arbitrary structures. As one relevant area of research for this model the authors identify studying such automata over particular structures such as real and algebraically closed fields. In this paper we start investigations into this direction. We prove several structural results about sets accepted by such automata, and analyze decidability as well as complexity of several classical questions about automata in the new framework. Our results show quite a diverse picture when compared to the well known results for finite automata over finite alphabets. [ABSTRACT FROM AUTHOR]

Abstract: With many applications in engineering and scientific fields, quantifier elimination (QE) has received increasing attention. Cylindrical algebraic decomposition (CAD) is used as a basis for a general QE algorithm. In this paper we present an effective symbolic–numeric cylindrical algebraic decomposition (SNCAD) algorithm for QE incorporating several new devices, which we call “quick tests”. The simple quick tests are run beforehand to detect an unnecessary procedure that might be skipped without violating the correctness of results and they thus considerably reduce the computing time. The effectiveness of the SNCAD algorithm is examined in a number of experiments including practical engineering problems, which also reveal the quality of the implementation. Experimental results show that our implementation has significantly improved efficiency compared with our previous work. [Copyright &y& Elsevier]