Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.     

On generators and generative capacity of EOL forms

Summary In this paper we study the generative capacity of EOL forms from two different points of view. On the one hand, we consider the generative capacity of special EOL forms which one could call linear like and context free like, establishing the existence of a rich variety of non-regular sub-EOL language families. On the other hand, we propose the notion of a generator L of a language family We mean by this that any synchronized EOL system generating L generates — if understood as an EOL form — all languages of . We characterize the generators of the family of regular languages, and prove that other well known language families do not have generators.Partially supported under NSE Research Council of Canada, grant No. A-7700     

On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

Genes without prominence: a reappraisal of the foundations of biology

The sequencing of the human genome raises two intriguing questions: why has the prediction of the inheritance of common diseases from the presence of abnormal alleles proved so unrewarding in most cases and how can some 25 000 genes generate such a rich complexity evident in the human phenotype? It is proposed that light can be shed on these questions by viewing evolution and organisms as natural processes contingent on the second law of thermodynamics, equivalent to the principle of least action in its original form. Consequently, natural selection acts on variation in any mechanism that consumes energy from the environment rather than on genetic variation. According to this tenet cellular phenotype, represented by a minimum free energy attractor state comprising active gene products, has a causal role in giving rise, by a self-similar process of cell-to-cell interaction, to morphology and functionality in organisms, which, in turn, by a self-similar process entailing Darwin''s proportional numbers are influencing their ecosystems. Thus, genes are merely a means of specifying polypeptides: those that serve free energy consumption in a given surroundings contribute to cellular phenotype as determined by the phenotype. In such natural processes, everything depends on everything else, and phenotypes are emergent properties of their systems.     

An experimental investigation into the pre-treatment of synthetic membranes using sodium hydroxide solutions

In this paper the effect of two pre-treatment methods are compared experimentally for the filtration of (i) a spent sulphite liquor (17.8 wt.% dry solids) using a 20 kg mol⁻¹ molar mass cut off (MMCO) fluoropolymer membrane and (ii) a molasses solution (45° Brix) using a polysulphone (Psf) membrane (1.5 μm pore size). Both feeds are industrially relevant, and subject to severe fouling issues when membranes are used in their subsequent processing. The pre-treatment methods evaluated were: (i) conditioning with water at 60 °C only [Protocol 1], and (ii) conditioning with water at 60 °C followed by cleaning with 0.5 wt.% NaOH [Protocol 2]. Results are presented that confirm the benefits of sodium hydroxide preconditioning upon performance, supporting the suggestion by some membrane manufacturers that this step be included as part of the pre-treatment protocol.     

Development of color density concept with color difference formulas in respect to human vision system

The aims of this study are to develop the color density concept and to propose the color density based color difference formulas. The color density is defined using the metric coefficients that are based on the discrimination ellipses and the locations of the colors in the color space. The ellipse sets are the MacAdam ellipses in the CIE 1931 xy-chromaticity diagram and the chromaticity-discrimination ellipses in the CIELAB space. The latter set was originally used to develop the CIEDE2000 color difference formula. The color difference can be calculated from the color density for the two colors under consideration. As a result, the color density represents the perceived color difference more accurately, and it could be used to characterize a color by a quantity attribute matching better to the perceived color difference from this color. Resulting from this, the color density concept provides simply a correction term for the estimation of the color differences. In the experiments, the line element formula and the CIEDE2000 color difference formula performed better than the color density based difference measures. The reason behind this is in the current modeling of the color density concept. The discrimination ellipses are typically described with three-dimensional data consisting of two axes, the major and the minor, and the inclination angle. The proposed color density is only a one-dimensional corrector for color differences; thus, it cannot capture all the details of the ellipse information. Still, the color density gives clearly more correct estimations to perceived color differences than Euclidean distances using directly the coordinates of the color space.     

Codes defined by multiple sets of trajectories

We investigate the use of shuffle on trajectories to model certain classes of languages arising in the theory of codes. In particular, for each finite set of sets of trajectories, which we call a hyperset of trajectories, we define a class of languages induced by that hyperset of trajectories. We investigate the properties of hypersets of trajectories and the associated classes of languages, including the problem of decidability of membership and the problem of equivalence of hypersets of trajectories.     

SPUDT filters for the 2.45 GHz ISM band

Filters based on using single-phase, unidirectional transducers (SPUDT) consisting of lambda/4 and wider electrodes are presented. The design variants exploit the significant difference between the reflectivity of short-circuited lambda/4 electrodes and that of floating wide electrodes on 128 degree lithium niobate (LiNbO3). The surface acoustic wave (SAW) devices operating at 2.45 GHz have critical dimensions of about 0.3-0.4 microm, accessible to standard optical lithography. When matched, the fabricated SPUDT filters exhibit minimum insertion losses of 5.5-7.9 dB together with 3 dB passbands of 89-102 MHz. The majority of the insertion loss can be attributed to the attenuation on free surface and inside the grating, and to the resistivity of the electrodes.     

Finite element simulations of thin-film composite BAW resonators

A finite element method (FEM) formulation is presented for the numerical solution of the electroelastic equations that govern the linear forced vibrations of piezoelectric media. A harmonic time dependence is assumed. Both of the approaches, that of solving the field problem (harmonic analysis) and that of solving the corresponding eigenvalue problem (modal analysis), are described. A FEM software package has been created from scratch. Important aspects central to the efficient implementation of FEM are explained, such as memory management and solving the generalized piezoelectric eigenvalue problem. Algorithms for reducing the required computer memory through optimization of the matrix profile, as well as Lanczos algorithm for the solution of the eigenvalue problem are linked into the software from external numerical libraries. Our FEM software is applied to detailed numerical modeling of thin-film bulk acoustic wave (BAW) composite resonators. Comparison of results from 2D and full 3D simulations of a resonator are presented. In particular, 3D simulations are used to investigate the effect of the top electrode shape on the resonator electrical response. The validity of the modeling technique is demonstrated by comparing the simulated and measured displacement profiles at several frequencies. The results show that useful information on the performance of the thin-film resonators can be obtained even with relatively coarse meshes and, consequently, moderate computational resources     

Limitations of lower bound methods for deterministic nested word automata

Finite automata operating on nested words were introduced by Alur and Madhusudan in 2006. While nested word automata retain many of the desirable properties of ordinary finite automata, there is no known efficient minimization algorithm for deterministic nested word automata and, interestingly, state complexity bounds for nested word automata turn out to differ significantly from the corresponding bounds for ordinary finite automata. Consequently lower bounds for the state complexity of nested word languages need to rely on fooling set type techniques. We discuss limitations of the techniques and show that, even in the deterministic case, the bounds given by the lower bound methods may be arbitrarily far away from the actual state complexity of the nested word language.