PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

A Dynamic Dictionary for Priced Information with Application

In this paper we design a dynamic dictionary for the priced information model initiated by Charikar et al. Assume that a set S consisting of n elements is given such that each element has an associated price, a positive real number. The cost of performing an operation on elements of S is a function of their prices. The cost of an algorithm is the sum of the costs of all operations it performs. The objective is to design algorithms which incur low cost. In this model we propose a dynamic dictionary, supporting search, insert and delete, for keys drawn from a linearly ordered set. As an application we show that the dictionary can be used in computing the trapezoidal map of a set of line segments, a fundamental problem in computational geometry.     

Applications of the 4×4 determinant method and the POLYGON ENGINE

In the first half of the paper, various types of processing pertaining to a polygon, using the 4×4 determinant theories are explained along with a new containment test algorithm of a point in a polygon. In the latter half of the paper, a general-purpose geometric processor, the POLYGON ENGINE, is presented which can deal with various types of interference problems, such as Boolean operations in solid modelling, hidden line and surface eliminations, ray tracing and so on. It is, a successor of the TRIANGLE PROCESSOR and is also based upon the 4×4 determinant theories [4–6]. While the TRIANGLE PROCESSOR processes a triangulated polygon on a triangle-by-triangle basis, the POLYGON ENGINE can treat a polygon without triangulation. The latter is expected to be more functional, more efficient and easier to use.     

PROGRESS IN THE MODELLING OF AIR FLOW PATTERNS IN TIMBER KILNS

Progress in modelling air flow patterns in timber kilns using Computational Fluid Dynamics is reviewed in this work. These simulations are intended to predict the distribution of the flow in the fillet spaces between boards in a hydraulic model of a timber kiln. Here, the flow regime between the boards is transitional between laminar and turbulent flow, with Reynolds numbers of the order of 5000. Running the simulation as a transient calculation has shown few problems with convergence issues, reaching a mass residual of 0.2% of the total inflow after 40-100 iterations per time step for time steps of 0.01 s. Grid sensitivity studies have shown that non-uniform grids are necessary because of the sudden changes in flow cross section, and the flow simulations are insensitive to grid refinement for non-uniform grids with more than 300,000 cells. The best agreement between the experimentally-measured flow distributions between fillet spaces and those predicted by the simulation have been achieved for (effective) bulk viscosities between the laminar viscosity for water and ten times that value. This change in viscosity is not very large (less than an order of magnitude), given that effective turbulent viscosities are typically several orders of magnitude greater than laminar ones. This result is consistent with the transitional flows here.     

Co-evolution as a computational and cognitive model of design

Co-evolutionary design has been developed as a computational model that assumes two parallel search spaces: the problem space and the solution space. The design process iteratively searches each space using the other space as the basis for a fitness function when evaluating the alternatives. Co-evolutionary design can also be developed as a cognitive model of design by characterizing the way in which designers iteratively search for a design solution, making revisions to the problem specification. This paper presents the computational model of co-evolutionary design and then describes a protocol study of human designers looking for evidence of co-evolution of problem specifications and design solutions. The study shows that co-evolutionary design is a good cognitive model of design and highlights the similarities and differences between the computational model and the cognitive model. The results show that the two kinds of co-evolutionary design complement each other, having strengths in different aspects of the design process. Electronic Publication     

Validation of a Three-Dimensional Computational Fluid Dynamics Model of a Contact Tank

A three-dimensional (3D) computational fluid dynamics (CFD) model of a contact tank is presented in this paper. The model results are compared against 3D velocities and flow through curve (FTC) data, representing a tracer concentration profile, from a 1:8 scale physical model. The objective is to demonstrate that CFD models can simulate both the FTC and the 3D velocity field quite well. Simultaneous validation of velocities and FTC is important in ascertaining the predictive capabilities of CFD models, as physical model studies indicate that different baffle arrangements can lead to similar FTCs. Therefore, a good prediction of only FTC, as presented in previous 3D CFD model studies, does not necessarily imply a correct simulation of the flow field.     

Erosion rate correlations of a pipe protruded in an abrupt pipe contraction

Erosion is one of the most serious problems in various gas and liquid flow passages such as flow in pipes, pumps, turbines, compressors and many other devices. Sand presence causes loss of pipe wall thickness that can lead to pipe erosion, frequent failures and loss of expensive production time. The importance of this problem is mainly due to many related engineering applications, viz. heat exchangers. In order to reduce the frequency of such pipe erosions, caps in the form of replaceable pipes are protruded in the sudden contraction regions which are exposed to most of the serious erosion rates. In the present work, numerical investigation of the erosion of a pipe protruded in a sudden contraction is presented. The turbulent, steady, 2-D axi-symmetric flow inside an axi-symmetric abrupt contraction pipe with a pipe protrusion embedded in it was solved by steady-state time averaged conservation equations of mass and momentum along with two equation model for turbulence. Particles are tracked using Lagrangian particle tracking. An erosion model was employed to investigate the erosion phenomena for the given geometry. The influence of the different parameters such as the inlet flow velocity (3–10 m/s), the particle diameter (10–400 μm), the protruded pipe geometry (thickness T=1–5 mm and depth H=2–5 mm) and the pipe contraction ratio (Cr=0.25–0.5) on the erosion of pipe protrusion was investigated. Correlations for the influence of inlet flow velocity, depth and thickness of the protruded pipe on the erosion rate are presented.     

Computational materials: Multi-scale modeling and simulation of nanostructured materials

The paper provides details on the current approach to multi-scale modeling and simulation of advanced materials for structural applications. Examples are given that illustrate the suggested approaches to predicting the behavior and influencing the design of nanostructured materials such as high-performance polymers, composites, and nanotube-reinforced polymers. Primary simulation and measurement methods applicable to multi-scale modeling are outlined. Key challenges including verification and validation are highlighted and discussed.     

Optimal implementations of UPGMA and other common clustering algorithms

In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n²)-time implementations of such algorithms which use a ‘locally closest’ joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. ‘globally closest’).