Search

In this paper a steady-state rolling problem with nonlinear friction, for rigid-plastic, rate sensitive and slightly compressible materials is considered. Its variational formulation is given and existence and uniqueness results, obtained with the help of successive iteration methods are presented. Considering the slight material compressibility as a method of penalisation, it is further shown, that when the compressibility parameter tends to zero the solution of the rolling problem for incompressible materials is approached. [ABSTRACT FROM AUTHOR]

We study the complexity of the Accretive Graph Assembly Problem (AGAP). An instance of AGAP consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if there is a sequence of vertex additions which constructs G starting from the seed. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. Our first result is that AGAP is NP-complete even on degree 3 planar graphs when edges have only two different types of weights. This resolves the complexity of AGAP in the sense that the problem is polytime solvable when either the degree is bounded by 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of AGAP on degree 3 bounded graphs with two distinct weights: wp, wn. We give a simple system of linear constraints on wp, wn, and τ that determines whether the problem is NP-complete or is polytime solvable. In the process of establishing this dichotomy, we give the first polytime algorithm to solve a non-trivial class of AGAP Finally, we consider the optimization version of AGAP where the goal is to realize a largest-possible subgraph of the given input graph. We show that even on constructible graphs of degree at most 3, it is NP-hard to realize a (1/n1-ε)-fraction of the input graph for any ε> 0; here n denotes the number of vertices in G. [ABSTRACT FROM AUTHOR]

The widespread use of embedded systems mandates the development of industrial software design methods based on formal models (frameworks) and prefabricated components. This paper presents a formal specification of the COMDES framework, focusing on the main architectural issues and the specific line of reasoning that was followed while developing a hierarchy of executable models describing relevant aspects of system structure and behaviour. The above framework has been used to systematically define a hierarchy of reusable and reconfigurable components - simple and composite function blocks, reconfigurable state machines and function units - implementing the executable models presented in the paper. [ABSTRACT FROM AUTHOR]

Poly-Si thin films were fabricated by Aluminium Induced Crystallization (AIC) of a-Si on ZnO:Al/Al coated glass substrates. ZnO:Al, Al and a-Si layers were deposited by rf magnetron sputtering. We have investigated the influence of different annealing atmospheres on the structural properties of the poly-Si films. The resulting polycrystalline Si films were analysed by microprobe Raman spectroscopy, optical microscopy and X-ray diffraction. [ABSTRACT FROM AUTHOR]

The paper presents advanced task management techniques featuring Boolean vectors and bitwise vector operations on kernel data structures in the context of the HARTEXTM hard real-time kernel. These techniques have been consistently applied to all aspects of task management and interaction. Hence, the execution time of system functions no longer depends on the number of tasks involved, resulting in predictable, jitter-free kernel operation. This approach has been further extended to time management resulting in a new type of kernel component, which can be used to implement timed multitasking - a novel technique providing for jitter-free execution of hard real-time tasks. [ABSTRACT FROM AUTHOR]

The widespread use of embedded systems mandates a rigorous engineering approach towards embedded software development, i.e. model-based design of embedded software. The paper presents design models of reusable and reconfigurable state machines that have been conceived in the context of the COMDES framework and in particular - the State Logic Controller and the Hybrid State Logic Controller, whose principles of operation are presented in the paper. The latter has been instrumental in developing a reconfigurable executable component, i.e. a function block of class State Machine, which can be used to implement a broad range of embedded applications such as sequential, continuous and hybrid control systems, as well as complex systems specified with hierarchical and concurrent state machines. [ABSTRACT FROM AUTHOR]

We study dynamic routing in store-and-forward packet networks where each network link has bounded buffer capacity for receiving incoming packets and is capable of transmitting a fixed number of packets per unit of time. At any moment in time, packets are injected at various network nodes with each packet specifying its destination node. The goal is to maximize the throughput, defined as the number of packets delivered to their destinations. In this paper, we make some progress in understanding what is achievable on various network topologies. For line networks, Nearest-to-Go (NTG), a natural greedy algorithm, was shown to be O(n2/3)-competitive by Aiello et al [1]. We show that NTG is $\tilde{O}(\sqrt{n})$-competitive, essentially matching an identical lower bound known on the performance of any greedy algorithm shown in [1]. We show that if we allow the online routing algorithm to make centralized decisions, there is indeed a randomized polylog(n)-competitive algorithm for line networks as well as rooted tree networks, where each packet is destined for the root of the tree. For grid graphs, we show that NTG has a performance ratio of $\tilde{\Theta}(n^{2/3})$ while no greedy algorithm can achieve a ratio better than $\Omega(\sqrt{n})$. Finally, for an arbitrary network with m edges, we show that NTG is $\tilde{\Theta}(m)$-competitive, improving upon an earlier bound of O(mn) [1]. [ABSTRACT FROM AUTHOR]

We consider the problem of finding pairs of short patterns such that, in a given input sequence of length n, the distance between each pair's patterns is at least α. The problem was introduced in [1]and is motivated by the optimization of multiplexed nested PCR. We study algorithms for the following two cases; the special case when the two patterns in the pair are required to have the same length, and the more general case when the patterns can have different lengths. For the first case we present an O(αn log log n) time and O(n) space algorithm, and for the general case we give an O(αn log n) time and O(n) space algorithm. The algorithms work for any alphabet size and use asymptotically less space than the algorithms presented in [1]. For alphabets of constant size we also give an time algorithm for the general case. We demonstrate that the algorithms perform well in practice and present our findings for the human genome. In addition, we study an extended version of the problem where patterns in the pair occur at certain positions at a distance at most α, but do not occur α-close anywhere else, in the input sequence. [ABSTRACT FROM AUTHOR]

Widespread use of embedded systems mandates the use of industrial production methods featuring model-based design and repositories of prefabricated software components. The main problem that has to be addressed in this context is to systematically develop a software architecture (framework) for embedded applications, taking into account the true nature of embedded systems, which are predominantly real-time control and monitoring systems. There are a great number of design issues and unresolved problems with existing architectures, which have to be carefully analyzed in order to develop a viable component-based design method for embedded applications. Such an analysis is presented in this paper, which focuses on a number of key issues: specification of system structure; specification of system behaviour; component scheduling and execution; program generation vs. system configuration. The analysis has been used to formulate the guidelines used to develop COMDES - a software framework for distributed embedded applications. [ABSTRACT FROM AUTHOR]

The paper presents a new real-time kernel architecture featuring component-based design, as well as advanced algorithms based on Boolean vectors and bitwise vector processing of kernel data structures. These have been consistently applied to all aspects of task management, as well as task synchronization and communication. Hence, the execution time of system functions no longer depends on the number of tasks involved, resulting in predictable, jitter-free operation of kernel subsystems. This approach has been further extended to time management resulting in a new type of kernel component, which can be used to implement Distributed Timed Multitasking - a novel computational model providing for predictable jitter-free execution of hard real-time tasks as well as distributed transactions in a dynamic scheduling environment. [ABSTRACT FROM AUTHOR]

Protein-nucleic acid complexes play a crucial role in the events involved in gene expression and regulation. Direct and powerful approaches in studying this regulation are footprinting and protein-DNA crosslinking. Protein-DNA crosslinking detects the presence of a protein on a given DNA sequence, and footprinting allows one to judge the mechanism and details of protein-DNA interactions. [ABSTRACT FROM AUTHOR]