This dissertation is devoted to various aspects of groups generated by automata. We study particular classes and examples of such groups from different points of view. It consists of four main parts. In the first part we study Sushchansky p-groups introduced in 1979 by Sushchansky in "Periodic permutation p-groups and the unrestricted Burnside problem". These groups represent one of the earliest examples of Burnside groups and, at the same time, show the potential of the class of groups generated by automata to contain groups with extraordinary properties. The original definition is translated into the language of automata. The original actions of Sushchansky groups on p- ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definition and prove that these groups admit faithful level-transitive actions on the same tree. Certain branch structures in their self-similar closures are established. We provide the connection with so-called G groups introduced by Bartholdi, Grigorchuk and Suninc in "Branch groups" that shows that all Sushchansky groups have intermediate growth and allows us to obtain an upper bound on their period growth functions. The second part is devoted to the opposite question of realization of known groups as groups generated by automata. We construct a family of automata with n states, n greater than or equal to 4, acting on a rooted binary tree and generating the free products of cyclic groups of order 2. The iterated monodromy group IMG(z2+i) of the self-map of the complex plain z -> z2 + i is the central object of the third part of dissertation. This group acts faithfully on the binary rooted tree and is generated by 4-state automaton. We provide a self-similar measure for this group giving alternative proof of its amenability. We also compute an L-presentation for IMG(z2+i) and provide calculations related to the spectrum of the Markov operator on the Schreier graph of the action of IMG(z2 + i) on the orbit of a point on the boundary of the binary rooted tree. Finally, the last part is discussing the package AutomGrp for GAP system developed jointly by the author and Yevgen Muntyan. This is a very useful tool for studying the groups generated by automata from the computational point of view. Main functionality and applications are provided.

This thesis conducts a comprehensive examination on the random walk behavior of 29 foreign exchange rates over the period of floating exchange regime, using variance-ratio tests. The cross-country and time-series test show that random walk model cannot be rejected on majority, and the random walk behavior is quite volatile across the whole floating exchange regime period. It then goes further to explore possible factors that can explain the probability of rejection/ non-rejections on random walk model using linear as well as nonlinear probability models, and find that the factors such as capital openness and investment-to-trade ratio significantly increases the chance of its exchange rate exhibiting random walk behavior.

The studies discussed in this thesis unify experimental and theoretical techniques, both established and novel, in investigating the problem of how a protein that binds specific sites on DNA translocates to, recognizes, and stably binds to its target site or sites. The thesis is organized into two parts. Part I outlines the history of the problem and the theory and experiments that have addressed the problem and presents an apparent incompatibility between efficient search and stable, specific binding. To address this problem, we elaborate a model of protein-DNA interaction in which the protein may bind DNA in either a search (S) mode or a recognition (R) mode. The former is characterized by zero or weak sequence-dependence in the binding energy, while the latter is highly sequence-dependent. The protein undergoes a random walk along the DNA in the S mode, and if it encounters its target site, must undergo a conformational transition into the R mode. The model resolves the apparent paradox, and accounts for the observed speed, specificity, and stability in protein-DNA interactions. The model shows internal agreement as regards theoretical and simulated results, as well as external agreement with experimental measurements. Part II reports on research that has tested the applicability of the two-mode model to the tumor suppressor transcription factor p53. It describes in greater depth the experimental techniques and findings up to the present work, and introduces the techniques and biological system used in our research. We employ single-molecule optical microscopy in two projects to study the diffusional kinetics of p53 on DNA. The first project measures the diffusion coefficient of p53 and determines that the protein satisfies a number of requirements for the validity of the two-mode model and for efficient target localization. The second project examines the sequence-dependence in p53's sliding kinetics, and explicitly models the energy landscape it experiences on DNA and relates features of the landscape to observed local variation in diffusion coefficient. The thesis closes with proposed extensions and complements to the projects, and a discussion of the implications of our work and its relation to recent developments in the field.

<p>In this dissertation we study combinatorial Hodge Laplacians on simplicial com-</p><p>plexes using tools generalized from spectral graph theory. Specifically, we consider</p><p>generalizations of graph Cheeger numbers and graph random walks. The results in</p><p>this dissertation can be thought of as the beginnings of a new spectral theory for</p><p>simplicial complexes and a new theory of high-dimensional expansion.</p><p>We first consider new high-dimensional isoperimetric constants. A new Cheeger-</p><p>type inequality is proved, under certain conditions, between an isoperimetric constant</p><p>and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar</p><p>to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is</p><p>proved, using the new Cheeger-type inequality and special examples, showing that</p><p>certain Cheeger-type inequalities cannot hold in codimension 1.</p><p>Second, we consider new random walks with killing on the set of oriented sim-</p><p>plexes of a certain dimension. We show that there is a systematic way of relating</p><p>these walks to combinatorial Laplacians such that a certain notion of mixing time</p><p>is bounded by a spectral gap and such that distributions that are stationary in a</p><p>certain sense relate to the harmonics of the Laplacian. In addition, we consider the</p><p>possibility of using these new random walks for semi-supervised learning. An algo-</p><p>rithm is devised which generalizes a classic label-propagation algorithm on graphs to</p><p>simplicial complexes. This new algorithm applies to a new semi-supervised learning</p><p>problem, one in which the underlying structure to be learned is flow-like.</p> / Dissertation

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. We will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. Let A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

Thesis (Ph. D.)--University of Missouri-Columbia, 2002. / Typescript. Vita. Includes bibliographical references (leaves 79-81). Also available on the Internet.

The past three decades have seen extraordinary progress in the manipulation of neutral atoms with laser light, to the point where it is now routine to trap and cool both individual atoms and entire atomic clouds to temperatures of only a few tens of nanoKelvin in a controlled and repeatable fashion. In this thesis we study several applications of Rydberg atoms - atoms with an electron in a highly excited state - within such ultracold atomic systems. Due to their highly-excited electron, Rydberg atoms have a number of exaggerated properties: in addition to being physically large, they have long radiative lifetimes, and interact strongly both with one another and with applied external fields. Rydberg atoms consequently find many interesting applications within ultracold atomic physics. We begin this thesis by analysing the way in which a rubidium atom prepared in an excited Rydberg state decays to the ground state. Using quantum defect theory to model the wavefunction of the excited electron, we compute branching ratios for the various decay channels that lead out of the Rydberg states of rubidium. By using these results to carry out detailed simulations of the radiative cascade process, we show that the dynamics of spontaneous emission from Rydberg states cannot be adequately described by a truncated atomic level structure. We then investigate the stability of ultra-large diatomic molecules formed by pairs of Rydberg atoms. Using quantum defect theory to model the electronic wavefunctions, we apply molecular integral techniques to calculate the equilibrium distance and binding energy of these molecular Rydberg states. Our results indicate that these Ryberg macro-dimers are predicted to show a potential minimum, with equilibrium distances of up to several hundred nanometres. In the second half of this thesis, we present a new method of symbolically evaluating functions of matrices. This method, which we term the method of path-sums, has applications to the simulation of strongly-correlated many-body Rydberg systems, and is based on the combination of a mapping between matrix multiplications and walks on weighted directed graphs with a universal result on the structure of such walks. After presenting and proving this universal graph theoretic result, we develop the path-sum approach to matrix functions. We discuss the application of path-sums to the simulation of strongly-correlated many-body quantum systems, and indicate future directions for the method.

L’objet de cette thèse est d’établir des théorèmes limites locaux pour des marches aléatoires réfléchies sur N. La théorie des fluctuations des marches aléatoires et la factorisation de Wiener- Hopf y jouent un rôle important. On développera dans la première partie une approche classique que l’on appliquera à l’étude des marches aléatoires sur R+ avec réflexions non élastiques en 0. Dans la deuxième partie, on explicitera une méthode différente qui fait intervenir des outils algébriques, d’analyse complexe et des techniques de factorisation utilisant de manière essentielle les fonctions génératrices. Cette approche a été développée il y a une cinquantaine d’année pour l’étude de marches de Markov, elle sera présentée dans cette partie dans le cas des marches aléatoires à pas i.i.d. où un certain nombre de simplifications apparaissent et sera ensuite utilisée pour étudier les marches aléatoires sur N avec réflexions élastiques ou non élastiques en zéro. Finalement, dans la dernière partie, nous mettons en place les outils nécessaires pour établir une factorisation de Wiener-Hopf dans un cadre markovien afin d’étudier les fluctuations des marches de Markov sur Z; nous reprenons des travaux anciens dont les démonstrations méritaient d’être détaillées, l’objectif à moyen terme étant d’appliquer les méthodes algébriques décrites ci-dessus pour l’étude de marches de Markov réfléchies sur N. / The purpose of this thesis is to establish some local limit theorems for reflected random walks on N. The fluctuations theory and the Wiener-Hopf factorization play a crucial role. We will develop in the first part a classical approach that we will apply to the study of random walks on R+ with non-elastic reflections at zero. In the second part, we will explicit a different method which involves algebraic tools, complex analysis and factorization techniques, using in an essential way generating functions. These approach was developed 50 years ago to cover Markov walks, it will be presented in this part in the case of random walks with i.i.d jumps where many simplifications appear and will be then used to study random walks on N with either elastic or non-elastic reflections at zero. Finally, in the last part, we will introduce the useful tools to establish a Wiener-Hopf factorization in a markovian framework in order to study the fluctuations of Markov walks on Z. We investigate some previous work, especially some proofs that warranted to be more detailed, with a mediumterm objective of applying the algebraic tools described above to study reflected Markov walks on N.

Este trabalho traz uma investigação sobre as ruas de pedestres e as mudanças que elas provocam no centro de uma cidade. O objetivo da pesquisa foi verificar os aspectos positivos e os negativos da implantação de uma rua de pedestres, como forma de buscar subsídios para a implantação e manutenção desses espaços. O objeto principal desta pesquisa é a rua de pedestres de Londrina-PR, sendo a rua de pedestres de Bauru-SP o objeto secundário. Foi feita uma análise comparativa entre as duas. A pesquisa teve por base três tipos de análises: a da autora, a aplicação de questionários e a elaboração de mapas comportamentais, o que possibilitou o cruzamento das informações levando em consideração diferentes pontos de vista o do pesquisador e o do usuário. O trabalho procurou verificar, sobretudo, como um projeto de revitalização urbana contribui para ampliar a qualidade dos espaços urbanos. / This work investigates pedestrian malls and the changes they bring about to downtown areas. The objective of the research was to verify the positive and negative aspects of pedestrian mall implementation and maintenance. The main focus of this study is a pedestrian mall located in Londrina, Paraná, having another pedestrian mall located in Bauru, São Paulo as a secondary object of study. A comparative study of the two walks was carried out using three types of analyses: personal ( by the author of this study ), questionnaires and behavior maps . Data from these three analyses were crossed, taking into consideration the different viewpoints those of the researcher and those of the users. Most importantly, this work tried to verify the contribution of urban revitalization project to the improvement of the quality of urban areas.

A análise de texturas tem atraído um crescente interesse em visão computacional devido a sua importância na caracterização de imagens. Basicamente, as pesquisas em texturas podem ser divididas em duas categorias: texturas estáticas e texturas dinâmicas. As texturas estáticas são caracterizadas por variações de intensidades que formam um determinado padrão repetido espacialmente na imagem. Por outro lado, as texturas dinâmicas são padrões de texturas presentes em uma sequência de imagens. Embora muitas pesquisas tenham sido realizadas, essa área ainda se encontra aberta a estudos, principalmente em texturas dinâmicas por se tratar de um assunto recente e pouco explorado. Este trabalho tem como objetivo o desenvolvimento de pesquisas que abrangem ambos os tipos de texturas nos âmbitos teórico e prático. Em texturas estáticas, foram propostos dois métodos: (i) baseado em caminhadas determinísticas parcialmente auto-repulsivas e dimensão fractal - (ii) baseado em atividade em redes direcionadas. Em texturas dinâmicas, as caminhadas determinísticas parcialmente auto-repulsivas foram estendidas para sequências de imagens e obtiveram resultados interessantes em reconhecimento e segmentação. Os métodos propostos foram aplicados em problemas da biologia e nanotecnologia, apresentando resultados interessantes para o desenvolvimento de ambas as áreas. / Texture analysis has attracted an increasing interest in computer vision due to its importance in describing images. Basically, research on textures can be divided into two categories: static and dynamic textures. Static textures are characterized by intensity variations which form a pattern repeated in the image spatially. On the other hand, dynamic textures are patterns of textures present in a sequence of images. Although many studies have been carried out, this area is still open to study, especially in dynamic textures since it is a recent and little-explored subject. This study aims to develop research covering both types of textures in theoretical and practical fields. In static textures, two methods were proposed: (i) based on deterministic partially self-avoiding walks and fractal dimension - (ii) based on activity in directed networks. In dynamic textures, deterministic partially self-avoiding walks were extended to sequences of images and obtained interesting results in recognition and segmentation. The proposed methods were applied to problems of biology and nanotechnology, presenting interesting results in the development of both areas.