Structural and Computational Existence Results for Multidimensional Subshifts

Symbolic dynamics is a branch of mathematics that studies the structure of infinite sequences of symbols, or in the multidimensional case, infinite grids of symbols. Classes of such sequences and grids defined by collections of forbidden patterns are called subshifts, and subshifts of finite type are defined by finitely many forbidden patterns. The simplest examples of multidimensional subshifts are sets of Wang tilings, infinite arrangements of square tiles with colored edges, where adjacent edges must have the same color. Multidimensional symbolic dynamics has strong connections to computability theory, since most of the basic properties of subshifts cannot be recognized by computer programs, but are instead characterized by some higher-level notion of computability. This dissertation focuses on the structure of multidimensional subshifts, and the ways in which it relates to their computational properties. In the first part, we study the subpattern posets and Cantor-Bendixson ranks of countable subshifts of finite type, which can be seen as measures of their structural complexity. We show, by explicitly constructing subshifts with the desired properties, that both notions are essentially restricted only by computability conditions. In the second part of the dissertation, we study different methods of defining (classes of ) multidimensional subshifts, and how they relate to each other and existing methods. We present definitions that use monadic second-order logic, a more restricted kind of logical quantification called quantifier extension, and multi-headed finite state machines. Two of the definitions give rise to hierarchies of subshift classes, which are a priori infinite, but which we show to collapse into finitely many levels. The quantifier extension provides insight to the somewhat mysterious class of multidimensional sofic subshifts, since we prove a characterization for the class of subshifts that can extend a sofic subshift into a nonsofic one.

Using Computational Fluid-Dynamics (CFD) for the evaluation of beer pasteurization: effect of orientation of cans

In-package pasteurization is the most used method for beer microbiological stabilization. The search for safer and better quality food has created a need to better understand the processes involved in producing it. However, little is known about the temperature and velocity profiles during the thermal processes of liquid foods in commercial packaging, which results in over-dimensioned processes to guarantee safety, decreasing the sensorial and nutritional characteristics of the product and increasing process costs. Simulations using Computational Fluid-Dynamics (CFD) have been used by various authors to evaluate those processes. The objective of the present paper was to evaluate the effect of packaging orientation in the pasteurization of beer in a commercial aluminum can using CFD. A heating process was simulated at 60 ºC up to 15 PUs (a conventional beer process, in which 1 Pasteurization Unit (PU) is equivalent to 1minute at 60 ºC). The temperature profile and convection current velocity along the process and the variation of the PUs were evaluated in relation to time considering the cans in the conventional, inverted, and horizontal positions. The temperature and velocity profiles were similar to those presented in the literature. The package position did not result in process improvement.

Computational fluid dynamics evaluation of liquid food thermal process in a brick shaped package

Food processes must ensure safety and high-quality products for a growing demand consumer creating the need for better knowledge of its unit operations. The Computational Fluid Dynamics (CFD) has been widely used for better understanding the food thermal processes, and it is one of the safest and most frequently used methods for food preservation. However, there is no single study in the literature describing thermal process of liquid foods in a brick shaped package. The present study evaluated such process and the influence of its orientation on the process lethality. It demonstrated the potential of using CFD to evaluate thermal processes of liquid foods and the importance of rheological characterization and convection in thermal processing of liquid foods. It also showed that packaging orientation does not result in different sterilization values during thermal process of the evaluated fluids in the brick shaped package.

Analysis of Phase Separator Design Criteria Using Computational Fluid Dynamics

Gravitational phase separation is a common unit operation found in most large-scale chemical processes. The need for phase separation can arise e.g. from product purification or protection of downstream equipment. In gravitational phase separation, the phases separate without the application of an external force. This is achieved in vessels where the flow velocity is lowered substantially compared to pipe flow. If the velocity is low enough, the denser phase settles towards the bottom of the vessel while the lighter phase rises. To find optimal configurations for gravitational phase separator vessels, several different geometrical and internal design features were evaluated based on simulations using OpenFOAM computational fluid dynamics (CFD) software. The studied features included inlet distributors, vessel dimensions, demister configurations and gas phase outlet configurations. Simulations were conducted as single phase steady state calculations. For comparison, additional simulations were performed as dynamic single and two-phase calculations. The steady state single phase calculations provided indications on preferred configurations for most above mentioned features. The results of the dynamic simulations supported the utilization of the computationally faster steady state model as a practical engineering tool. However, the two-phase model provides more truthful results especially with flows where a single phase does not determine the flow characteristics.

Computational models for and from biology : simple gene assembly and reaction systems

The advancement of science and technology makes it clear that no single perspective is any longer sufficient to describe the true nature of any phenomenon. That is why the interdisciplinary research is gaining more attention overtime. An excellent example of this type of research is natural computing which stands on the borderline between biology and computer science. The contribution of research done in natural computing is twofold: on one hand, it sheds light into how nature works and how it processes information and, on the other hand, it provides some guidelines on how to design bio-inspired technologies. The first direction in this thesis focuses on a nature-inspired process called gene assembly in ciliates. The second one studies reaction systems, as a modeling framework with its rationale built upon the biochemical interactions happening within a cell. The process of gene assembly in ciliates has attracted a lot of attention as a research topic in the past 15 years. Two main modelling frameworks have been initially proposed in the end of 1990s to capture ciliates’ gene assembly process, namely the intermolecular model and the intramolecular model. They were followed by other model proposals such as templatebased assembly and DNA rearrangement pathways recombination models. In this thesis we are interested in a variation of the intramolecular model called simple gene assembly model, which focuses on the simplest possible folds in the assembly process. We propose a new framework called directed overlap-inclusion (DOI) graphs to overcome the limitations that previously introduced models faced in capturing all the combinatorial details of the simple gene assembly process. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs. We also introduce DOI graph-based rewriting rules that capture all the operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model. Reaction systems (RS) is another nature-inspired modeling framework that is studied in this thesis. Reaction systems’ rationale is based upon two main regulation mechanisms, facilitation and inhibition, which control the interactions between biochemical reactions. Reaction systems is a complementary modeling framework to traditional quantitative frameworks, focusing on explicit cause-effect relationships between reactions. The explicit formulation of facilitation and inhibition mechanisms behind reactions, as well as the focus on interactions between reactions (rather than dynamics of concentrations) makes their applicability potentially wide and useful beyond biological case studies. In this thesis, we construct a reaction system model corresponding to the heat shock response mechanism based on a novel concept of dominance graph that captures the competition on resources in the ODE model. We also introduce for RS various concepts inspired by biology, e.g., mass conservation, steady state, periodicity, etc., to do model checking of the reaction systems based models. We prove that the complexity of the decision problems related to these properties varies from P to NP- and coNP-complete to PSPACE-complete. We further focus on the mass conservation relation in an RS and introduce the conservation dependency graph to capture the relation between the species and also propose an algorithm to list the conserved sets of a given reaction system.

Computational Market Dynamics of Virtual Economies

The last two decades have provided a vast opportunity to live and explore the compulsive imaginary world or virtual world through massively multiplayer online role-playing games (MMORPGs). MMORPG gives a wide range of opportunities to its users to participate with multi-players on the same platform, to communicate and to do real time actions. There is a virtual economy in these games which is largely player-driven. In-game currency provides its users to build up their Avatars, to buy or sell the necessary goods to play, survive in the games and so on. As a part of virtual economies generated through EVE Online, this thesis mainly focuses on how the prices of the minerals in EVE Online behave by applying the Jabłonska- Capasso-Morale (JCM) mathematical simulation model. It is to verify up to what degree the model can reproduce the virtual economy behavior. The model is applied to buy and sell prices of two minerals namely, isogen and morphite. The simulation results demonstrate that JCM model ts reasonably well to the mineral prices, which lets us conclude that virtual economies behave similarly to the real ones.

Experimental and Computational Studies on Copper and Hydrobenzoin Derivatives in Catalytic Asymmetric Reactions

The use of theory to understand and facilitate catalytic enantioselective organic transformations involving copper and hydrobenzoin derivatives is reported. Section A details the use of theory to predict, facilitate, and understand a copper promoted amino oxygenation reaction reported by Chemler et al. Using Density Functional Theory (DFT), employing the hybrid B3LYP functional and a LanL2DZ/6-31G(d) basis set, the mechanistic details were studied on a N-tosyl-o-allylaniline and a [alpha]-methyl-[gamma]-alkenyl sulfonamide substrate. The results suggest the N-C bond formation proceeds via a cisaminocupration, and not through a radical-type mechanism. Additionally, the origin of diastereoselection observed with [alpha]-methyl-[gamma]-alkenyl sulfonamide arises from avoidance of unfavourable steric interactions between the methyl substituent and the N -protecting group. Section B details the computationally guided, experimental investigation of two hydrobenzoin derivatives as ligands/ catalysts, as well as the attempted synthesis of a third hydrobenzoin derivative. The bis-boronic acid derived from hydrobenzoin was successful as a Lewis acid catalyst in the Bignielli reaction and the Conia ene reaction, but provided only racemic products. The chiral diol derived from hydrobenzoin successfully increased the rate of the addition of diethyl zinc to benzaldehyde in the presence of titanium tetraisopropoxide, however poor enantioinduction was obseverved. Notably, the observed reactivity was successfully predicted by theoretical calculations.

Towards reverse engineering of Photosystem II: Synergistic Computational and Experimental Approaches

ABSTRACT Photosystem II (PSII) of oxygenic photosynthesis has the unique ability to photochemically oxidize water, extracting electrons from water to result in the evolution of oxygen gas while depositing these electrons to the rest of the photosynthetic machinery which in turn reduces CO2 to carbohydrate molecules acting as fuel for the cell. Unfortunately, native PSII is unstable and not suitable to be used in industrial applications. Consequently, there is a need to reverse-engineer the water oxidation photochemical reactions of PSII using solution-stable proteins. But what does it take to reverse-engineer PSII’s reactions? PSII has the pigment with the highest oxidation potential in nature known as P680. The high oxidation of P680 is in fact the driving force for water oxidation. P680 is made up of a chlorophyll a dimer embedded inside the relatively hydrophobic transmembrane environment of PSII. In this thesis, the electrostatic factors contributing to the high oxidation potential of P680 are described. PSII oxidizes water in a specialized metal cluster known as the Oxygen Evolving Complex (OEC). The pathways that water can take to enter the relatively hydrophobic region of PSII are described as well. A previous attempt to reverse engineer PSII’s reactions using the protein scaffold of E. coli’s Bacterioferritin (BFR) existed. The oxidation potential of the pigment used for the BFR ‘reaction centre’ was measured and the protein effects calculated in a similar fashion to how P680 potentials were calculated in PSII. The BFR-RC’s pigment oxidation potential was found to be 0.57 V, too low to oxidize water or tyrosine like PSII. We suggest that the observed tyrosine oxidation in BRF-RC could be driven by the ZnCe6 di-cation. In order to increase the efficiency of iii tyrosine oxidation, and ultimately oxidize water, the first potential of ZnCe6 would have to attain a value in excess of 0.8 V. The results were used to develop a second generation of BFR-RC using a high oxidation pigment. The hypervalent phosphorous porphyrin forms a radical pair that can be observed using Transient Electron Paramagnetic Resonance (TR-EPR). Finally, the results from this thesis are discussed in light of the development of solar fuel producing systems.

Modeling Metal Protein Complexes from Experimental Extended X-ray Absorption Fine Structure using Computational Intelligence

Experimental Extended X-ray Absorption Fine Structure (EXAFS) spectra carry information about the chemical structure of metal protein complexes. However, pre- dicting the structure of such complexes from EXAFS spectra is not a simple task. Currently methods such as Monte Carlo optimization or simulated annealing are used in structure refinement of EXAFS. These methods have proven somewhat successful in structure refinement but have not been successful in finding the global minima. Multiple population based algorithms, including a genetic algorithm, a restarting ge- netic algorithm, differential evolution, and particle swarm optimization, are studied for their effectiveness in structure refinement of EXAFS. The oxygen-evolving com- plex in S1 is used as a benchmark for comparing the algorithms. These algorithms were successful in finding new atomic structures that produced improved calculated EXAFS spectra over atomic structures previously found.

Optimizing Computational Frameworks to Study the Influence of the Protein Environment on the Individual Site Energies of Chromophores in Photosystem II of Photosynthesis

Photosynthesis is a process in which electromagnetic radiation is converted into chemical energy. Photosystems capture photons with chromophores and transfer their energy to reaction centers using chromophores as a medium. In the reaction center, the excitation energy is used to perform chemical reactions. Knowledge of chromophore site energies is crucial to the understanding of excitation energy transfer pathways in photosystems and the ability to compute the site energies in a fast and accurate manner is mandatory for investigating how protein dynamics ef-fect the site energies and ultimately energy pathways with time. In this work we developed two software frameworks designed to optimize the calculations of chro-mophore site energies within a protein environment. The first is for performing quantum mechanical energy optimizations on molecules and the second is for com-puting site energies of chromophores in a fast and accurate manner using the polar-izability embedding method. The two frameworks allow for the fast and accurate calculation of chromophore site energies within proteins, ultimately allowing for the effect of protein dynamics on energy pathways to be studied. We use these frame-works to compute the site energies of the eight chromophores in the reaction center of photosystem II (PSII) using a 1.9 Å resolution x-ray structure of photosystem II. We compare our results to conflicting experimental data obtained from both isolat-ed intact PSII core preparations and the minimal reaction center preparation of PSII, and find our work more supportive of the former.

Timing verification in transaction modeling

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application.

Computational prediction of neural progenitor cell fates

Understanding how stem and progenitor cells choose between alternative cell fates is a major challenge in developmental biology. Efforts to tackle this problem have been hampered by the scarcity of markers that can be used to predict cell division outcomes. Here we present a computational method, based on algorithmic information theory, to analyze dynamic features of living cells over time. Using this method, we asked whether rat retinal progenitor cells (RPCs) display characteristic phenotypes before undergoing mitosis that could foretell their fate. We predicted whether RPCs will undergo a self-renewing or terminal division with 99% accuracy, or whether they will produce two photoreceptors or another combination of offspring with 87% accuracy. Our implementation can segment, track and generate predictions for 40 cells simultaneously on a standard computer at 5 min per frame. This method could be used to isolate cell populations with specific developmental potential, enabling previously impossible investigations.

A computational fluid dynamic study on the filtering mechanics in suspension feeding marine invertebrates

Les suspensivores ont la tâche importante de séparer les particules de l'eau. Bien qu'une grande gamme de morphologies existe pour les structures d'alimentation, elles sont pratiquement toutes constituées de rangées de cylindres qui interagissent avec leur environnement fluide. Le mécanisme de capture des particules utilisé dépend des contraintes morphologiques, des besoins énergétiques et des conditions d'écoulement. Comme nos objectifs étaient de comprendre ces relations, nous avons eu recours à des études de comparaison pour interpréter les tendances en nature et pour comprendre les conditions qui provoquent de nouveaux fonctionnements. Nous avons utilisé la dynamique des fluides numérique (computational fluid dynamics, CFD) pour créer des expériences contrôlées et pour simplifier les analyses. Notre première étude démontre que les coûts énergétiques associés au pompage dans les espaces petits sont élevés. De plus, le CFD suggère que les fentes branchiales des ptérobranches sont des structures rudimentaires, d'un ancêtre plus grande. Ce dernier point confirme l'hypothèse qu'un ver se nourrit par filtration tel que l'ancêtre des deuterostomes. Notre deuxième étude détermine la gamme du nombre de Reynolds number critique où la performance d'un filtre de balane change. Quand le Re est très bas, les différences morphologiques n'ont pas un grand effet sur le fonctionnement. Cependant, une pagaie devient une passoire lorsque le Re se trouve entre 1 et 3,5. Le CFD s’est dévoilé être un outil très utile qui a permis d’obtenir des détails sur les microfluides. Ces études montrent comment la morphologie et les dynamiques des fluides interagissent avec la mécanisme de capture ou de structures utilisées, ainsi que comment des petits changements de taille, de forme, ou de vitesse d'écoulement peuvent conduire à un nouveau fonctionnement.

Computational models for the prediction of severe thunderstorms over east indian region

Thunderstorm is one of the most spectacular weather phenomena in the atmosphere. Many parts over the Indian region experience thunderstorms at higher frequency during pre-monsoon months (March- May), when the atmosphere is highly unstable because of high temperatures prevailing at lower levels. Most dominant feature of the weather during the pre-monsoon season over the eastern Indo-Gangetic plain and northeast India is the outburst of severe local convective storms, commonly known as ‘Nor’wester’ or ‘Kalbaishakhi’. The severe thunderstorms associated with thunder, squall line, lightning and hail cause extensive losses in agriculture, damage to structure and also loss of life. The casualty due to lightning associated with thunderstorms in this region is the highest in the world. The highest numbers of aviation hazards are reported during occurrence of these thunderstorms. In India, 72% of tornadoes are associated with this thunderstorm.

Vibrational spectroscopic studies and computational study of quinoline-2-carbaldehyde benzoyl hydrazone

FT-IR spectrum of quinoline-2-carbaldehyde benzoyl hydrazone (HQb H2O) was recorded and analyzed. The synthesis and crystal structure data are also described. The vibrational wavenumbers were examined theoretically using the Gaussian03 package of programs using HF/6-31G(d) and B3LYP/6-31G(d) levels of theory. The data obtained from vibrational wavenumber calculations are used to assign vibrational bands obtained in infrared spectroscopy of the studied molecule. The first hyperpolarizability, infrared intensities and Raman activities are reported. The calculated first hyperpolarizability is comparable with the reported values of similar derivatives and is an attractive object for future studies of non-linear optics. The geometrical parameters of the title compound obtained from XRD studies are in agreement with the calculated values. The changes in the CAN bond lengths suggest an extended p-electron delocalization over quinoline and hydrazone moieties which is responsible for the non-linearity of the molecule