The intersection problem for K_4-e designs

A G-design of order n is a pair (P,B) where P is the vertex set of the complete graph K-n and B is an edge-disjoint decomposition of K-n into copies of the simple graph G. Following design terminology, we call these copies ''blocks''. Here K-4 - e denotes the complete graph K-4 with one edge removed. It is well-known that a K-4 - e design of order n exists if and only if n = 0 or 1 (mod 5), n greater than or equal to 6. The intersection problem here asks for which k is it possible to find two K-4 - e designs (P,B-1) and (P,B-2) of order n, with \B-1 boolean AND B-2\ = k, that is, with precisely k common blocks. Here we completely solve this intersection problem for K-4 - e designs.

Integer matrix diagonalization

We consider algorithms for computing the Smith normal form of integer matrices. A variety of different strategies have been proposed, primarily aimed at avoiding the major obstacle that occurs in such computations-explosive growth in size of intermediate entries. We present a new algorithm with excellent performance. We investigate the complexity of such computations, indicating relationships with NP-complete problems. We also describe new heuristics which perform well in practice. Wie present experimental evidence which shows our algorithm outperforming previous methods. (C) 1997 Academic Press Limited.

A generalised dynamic model for char particle gasification with structure evolution and peripheral fragmentation

A generalised model for the prediction of single char particle gasification dynamics, accounting for multi-component mass transfer with chemical reaction, heat transfer, as well as structure evolution and peripheral fragmentation is developed in this paper. Maxwell-Stefan analysis is uniquely applied to both micro and macropores within the framework of the dusty-gas model to account for the bidisperse nature of the char, which differs significantly from the conventional models that are based on a single pore type. The peripheral fragmentation and random-pore correlation incorporated into the model enable prediction of structure/reactivity relationships. The occurrence of chemical reaction within the boundary layer reported by Biggs and Agarwal (Chem. Eng. Sci. 52 (1997) 941) has been confirmed through an analysis of CO/CO2 product ratio obtained from model simulations. However, it is also quantitatively observed that the significance of boundary layer reaction reduces notably with the reduction of oxygen concentration in the flue gas, operational pressure and film thickness. Computations have also shown that in the presence of diffusional gradients peripheral fragmentation occurs in the early stages on the surface, after which conversion quickens significantly due to small particle size. Results of the early commencement of peripheral fragmentation at relatively low overall conversion obtained from a large number of simulations agree well with experimental observations reported by Feng and Bhatia (Energy & Fuels 14 (2000) 297). Comprehensive analysis of simulation results is carried out based on well accepted physical principles to rationalise model prediction. (C) 2001 Elsevier Science Ltd. AH rights reserved.

Computation of the linear elastic properties of random porous materials with a wide variety of microstructure

A finite-element method is used to study the elastic properties of random three-dimensional porous materials with highly interconnected pores. We show that Young's modulus, E, is practically independent of Poisson's ratio of the solid phase, nu(s), over the entire solid fraction range, and Poisson's ratio, nu, becomes independent of nu(s) as the percolation threshold is approached. We represent this behaviour of nu in a flow diagram. This interesting but approximate behaviour is very similar to the exactly known behaviour in two-dimensional porous materials. In addition, the behaviour of nu versus nu(s) appears to imply that information in the dilute porosity limit can affect behaviour in the percolation threshold limit. We summarize the finite-element results in terms of simple structure-property relations, instead of tables of data, to make it easier to apply the computational results. Without using accurate numerical computations, one is limited to various effective medium theories and rigorous approximations like bounds and expansions. The accuracy of these equations is unknown for general porous media. To verify a particular theory it is important to check that it predicts both isotropic elastic moduli, i.e. prediction of Young's modulus alone is necessary but not sufficient. The subtleties of Poisson's ratio behaviour actually provide a very effective method for showing differences between the theories and demonstrating their ranges of validity. We find that for moderate- to high-porosity materials, none of the analytical theories is accurate and, at present, numerical techniques must be relied upon.

Modelling of Lamb waves in composite laminated plates excited by interdigital transducers

The technique of permanently attaching interdigital transducers (IDT) to either flat or curved structural surfaces to excite single Lamb wave mode has demonstrated great potential for quantitative non-destructive evaluation and smart materials design, In this paper, the acoustic wave field in a composite laminated plate excited by an IDT is investigated. On the basis of discrete layer theory and a multiple integral transform method, an analytical-numerical approach is developed to evaluate the surface velocity response of the plate due to the IDTs excitation. In this approach, the frequency spectrum and wave number spectrum of the output of IDT are obtained directly. The corresponding time domain results are calculated by applying a standard inverse fast Fourier transformation technique. Numerical examples are presented to validate the developed method and show the ability of mode selection and isolation. A new effective way of transfer function estimation and interpretation is presented by considering the input wave number spectrum in addition to the commonly used input frequency spectrum. The new approach enables the simple physical evaluation of the influences of IDT geometrical features such as electrode finger widths and overall dimension and excitation signal properties on the input-output characteristics of IDT. Finally, considering the convenience of Mindlin plate wave theory in numerical computations as well as theoretical analysis, the validity is examined of using this approximate theory to design IDT for the excitation of the first and second anti-symmetric Lamb modes. (C) 2002 Elsevier Science Ltd. All rights reserved.

Link invariants associated with gauge equivalent solutions of the Yang-Baxter equation: The one-parameter family of minimal typical representations of Uq[gl(2|1)]

In this paper we investigate the construction of state models for link invariants using representations of the braid group obtained from various gauge choices for a solution of the trigonometric Yang-Baxter equation. Our results show that it is possible to obtain invariants of regular isotopy (as defined by Kauffman) which may not be ambient isotopic. We illustrate our results with explicit computations using solutions of the trigonometric Yang-Baxter equation associated with the one-parameter family of minimal typical representations of the quantum superalgebra U-q,[gl(2/1)]. We have implemented MATHEMATICA code to evaluate the invariants for all prime knots up to 10 crossings.

Nitrate retention under sugarcane in wet tropical Queensland deep soil profiles

Nitrate leaching below the crop root-zone in variable charge soils may be adsorbed at anion exchange sites, thereby temporarily reducing the risk of contamination of water bodies. The objectives of this study were (i) to investigate whether nitrate adsorption, accumulation, and retention in the Johnstone River Catchment of Far North Queensland wet tropics is widespread; (ii) to assess the capacity of soil in the Johnstone River Catchment to retain nitrate; and (iii) to deduce the consequences of nitrate adsorption/desorption on contamination of water bodies. Soil cores ranging from 8 to 12.5 m depth were taken from 28 sites across the catchment, representing 9 Ferrosol soil types under sugarcane (Saccharum officinarum-S) cultivation for at least 50 years and from rainforest. The cores were segmented at 0.5-m depth increments and subsamples were analysed for nitrate-N, cation and anion exchange capacities, pH, exchangeable cations (Ca, Mg, K, Na), soil organic C, electrical conductivity, sulfate-S, and chloride. Nitrate-N concentration under sugarcane ranged from 0 to 72.5 mg/kg, compared with 0 to 0.31 mg/kg under rainforest, both Pin Gin soils. The average N load in 1-12 m depth across 19 highly oxidic profiles of the Pin Gin soil series was 1550 kg/ha, compared with 185 kg/ha under 8 non-Pin Gin soils and 11 kg/ha in rainforest on a Pin Gin soil. Most of the nitrate retention was observed at depth of 2-12 m, particularly at 4-10 m, indicating that the accumulation was well below the crop root-zone. The average maximum potential nitrate retention capacity was 10.8 t/ha for the Pin Gin and 4.7 t/ha for the non-Pin Gin soil. Compared with the current N load, the soils still possess a large capacity to adsorb and retain nitrate in profiles. Retention of large quantities of the leached nitrate deep in most of the profiles has reduced the risk of contamination of water bodies. However, computations show that substantial quantities of the nitrate leached below the root-zone were not adsorbed and remain unaccounted for. This unaccounted nitrate might have entered both on- and off-site water bodies and/or have been denitrified.

An optical flow-based sensing system for reactive mobile robot navigation

This work discusses the use of optical flow to generate the sensorial information a mobile robot needs to react to the presence of obstacles when navigating in a non-structured environment. A sensing system based on optical flow and time-to-collision calculation is here proposed and experimented, which accomplishes two important paradigms. The first one is that all computations are performed onboard the robot, in spite of the limited computational capability available. The second one is that the algorithms for optical flow and time-to-collision calculations are fast enough to give the mobile robot the capability of reacting to any environmental change in real-time. Results of real experiments in which the sensing system here proposed is used as the only source of sensorial data to guide a mobile robot to avoid obstacles while wandering around are presented, and the analysis of such results allows validating the proposed sensing system.

An interactive state monad example

A common problem among information systems is the storage and maintenance of permanent information identified by a key. Such systems are typically known as data base engines or simply as data bases. Today the systems information market is full of solutions that provide mass storage capacities implemented in different operating system and with great amounts of extra functionalities. In this paper we will focus on the formal high level specification of data base systems in the Haskell language. We begin by introducing a high level view of a data base system with a specification of the most common operations in a functional point of view. We then augment this specification by lifting to the state monad which is then modified once again to permit input/output operations between the computations

Error bounds for low-rank approximations of the first exponential integral kernel

A hierarchical matrix is an efficient data-sparse representation of a matrix, especially useful for large dimensional problems. It consists of low-rank subblocks leading to low memory requirements as well as inexpensive computational costs. In this work, we discuss the use of the hierarchical matrix technique in the numerical solution of a large scale eigenvalue problem arising from a finite rank discretization of an integral operator. The operator is of convolution type, it is defined through the first exponential-integral function and, hence, it is weakly singular. We develop analytical expressions for the approximate degenerate kernels and deduce error upper bounds for these approximations. Some computational results illustrating the efficiency and robustness of the approach are presented.

Projecto de execução de fundações e estruturas de uma ponte em betão armado pré-esforçado

Este Trabalho refere-se ao Projecto de Execução de Fundações e Estruturas de uma Ponte Rodoviária em betão armado pré-esforçado, realizado no âmbito do Trabalho Final de Mestrado em Engenharia Civil – Especialização em Estruturas, do Instituto Superior de Engenharia de Lisboa. O Projecto de Execução é composto de Peças Escritas e Peças Desenhadas. Nas Peças Escritas estão incluídos: Memória Justificativa e Descritiva; Cálculos Justificativos e Anexos. A ponte é composta por dois tabuleiros paralelos com 10,28m de largura cada um e afastados entre si de 0,10m. A obra é constituída de 8 tramos; os tramos correntes com 31m de comprimento e os tramos extremos com 25 e 20m de comprimento, perfazendo um comprimento total de 231m. A obra foi parcialmente isolada dos sismos pela introdução, em todos os pilares, de aparelhos de apoio de elevado amortecimento sísmico do tipo HDRB (High Damping Rubber Bearings). Encontram-se particularmente discriminadas e detalhadas neste projecto as seguintes situações: - Cálculo do Pré-esforço e respectivas perdas; - Acção das sobrecargas rodoviárias; - Diferença de comportamento da obra na entrada em serviço e no longo prazo; - Análise sísmica e do isolamento sísmico; - Estudo dos efeitos diferidos: retracção e fluência. Tendo as abordagens de cálculo e as verificações de segurança seguido a regulamentação nacional em vigor, nomeadamente RSA e REBAP, foi no entanto feita uma aproximação às regras do “Capacity Design” previstas no EC8, em que se privilegia a actuação do projectista sobre o comportamento da estrutura, procurando uma resposta não linear da mesma, visando garantir que: - A rotura não ocorrerá nos elementos de fundação; - Nos pilares a dissipação de energia se faz através de rótulas plásticas, evitando-se roturas associadas a esforços transversos. A aplicação destas regras neste Projecto demonstrou haver um agravamento substancial na definição dos esforços a que devem resistir alguns dos componentes da estrutura, designadamente os pilares e as fundações, originando soluções de secções de betão e armaduras bem mais exigentes do que aqueles que resultariam da simples verificação de segurança, pela comparação entre esforços actuante e esforços resistentes “secção a secção”, imposta pela actual regulamentação nacional.

Code offloading on real-time multimedia systems: a framework for handling code mobility and code offloading in a QoS aware environment

Actualmente, os smartphones e outros dispositivos móveis têm vindo a ser dotados com cada vez maior poder computacional, sendo capazes de executar um vasto conjunto de aplicações desde simples programas de para tirar notas até sofisticados programas de navegação. Porém, mesmo com a evolução do seu hardware, os actuais dispositivos móveis ainda não possuem as mesmas capacidades que os computadores de mesa ou portáteis. Uma possível solução para este problema é distribuir a aplicação, executando partes dela no dispositivo local e o resto em outros dispositivos ligados à rede. Adicionalmente, alguns tipos de aplicações como aplicações multimédia, jogos electrónicos ou aplicações de ambiente imersivos possuem requisitos em termos de Qualidade de Serviço, particularmente de tempo real. Ao longo desta tese é proposto um sistema de execução de código remota para sistemas distribuídos com restrições de tempo-real. A arquitectura proposta adapta-se a sistemas que necessitem de executar periodicamente e em paralelo mesmo conjunto de funções com garantias de tempo real, mesmo desconhecendo os tempos de execução das referidas funções. A plataforma proposta foi desenvolvida para sistemas móveis capazes de executar o Sistema Operativo Android.

Constraint solving over multi-valued logics - application to digital circuits

Due to usage conditions, hazardous environments or intentional causes, physical and virtual systems are subject to faults in their components, which may affect their overall behaviour. In a ‘black-box’ agent modelled by a set of propositional logic rules, in which just a subset of components is externally visible, such faults may only be recognised by examining some output function of the agent. A (fault-free) model of the agent’s system provides the expected output given some input. If the real output differs from that predicted output, then the system is faulty. However, some faults may only become apparent in the system output when appropriate inputs are given. A number of problems regarding both testing and diagnosis thus arise, such as testing a fault, testing the whole system, finding possible faults and differentiating them to locate the correct one. The corresponding optimisation problems of finding solutions that require minimum resources are also very relevant in industry, as is minimal diagnosis. In this dissertation we use a well established set of benchmark circuits to address such diagnostic related problems and propose and develop models with different logics that we formalise and generalise as much as possible. We also prove that all techniques generalise to agents and to multiple faults. The developed multi-valued logics extend the usual Boolean logic (suitable for faultfree models) by encoding values with some dependency (usually on faults). Such logics thus allow modelling an arbitrary number of diagnostic theories. Each problem is subsequently solved with CLP solvers that we implement and discuss, together with a new efficient search technique that we present. We compare our results with other approaches such as SAT (that require substantial duplication of circuits), showing the effectiveness of constraints over multi-valued logics, and also the adequacy of a general set constraint solver (with special inferences over set functions such as cardinality) on other problems. In addition, for an optimisation problem, we integrate local search with a constructive approach (branch-and-bound) using a variety of logics to improve an existing efficient tool based on SAT and ILP.

Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

Specification of software architecture reconfiguration

In the past years, Software Architecture has attracted increased attention by academia and industry as the unifying concept to structure the design of complex systems. One particular research area deals with the possibility of reconfiguring architectures to adapt the systems they describe to new requirements. Reconfiguration amounts to adding and removing components and connections, and may have to occur without stopping the execution of the system being reconfigured. This work contributes to the formal description of such a process. Taking as a premise that a single formalism hardly ever satisfies all requirements in every situation, we present three approaches, each one with its own assumptions about the systems it can be applied to and with different advantages and disadvantages. Each approach is based on work of other researchers and has the aesthetic concern of changing as little as possible the original formalism, keeping its spirit. The first approach shows how a given reconfiguration can be specified in the same manner as the system it is applied to and in a way to be efficiently executed. The second approach explores the Chemical Abstract Machine, a formalism for rewriting multisets of terms, to describe architectures, computations, and reconfigurations in a uniform way. The last approach uses a UNITY-like parallel programming design language to describe computations, represents architectures by diagrams in the sense of Category Theory, and specifies reconfigurations by graph transformation rules.