This thesis aims to better represent a framework for asynchrony. Traditional asynchronous models, particularly those used to simulate cellular automata, have used stochasticity or randomness to generate update times. We claimthat, while they may make good representations of their application, such asynchronousmethods rid themodel of the essence of interesting asynchronous processes. Thus, we attempt to better harness the aspects internal to the decision process of such discretely dynamic cells as those in cellular automata.We propose the maxmin-m model as a suitable model for the asynchronous computation of cellular automata. The model uses maxmin-plus algebra, a special case of which is max-plus algebra. This algebra arises naturally from the cellular automaton requirement that a cell receives the state of its neighbours before updating. The maxmin-m model allows each cell to update after it receives m out of a possible n neighbours' states.The max-plus model shows that, while update times may be asynchronous in real time, there is no loss of information, since the corresponding asynchronous process is bijectively related to the synchronous model. In turn, the cellular automaton output, measured by the Shannon and word entropies, is shown to vary little from the synchronous model. Moreover, this type of asynchrony is simple, i.e. it is deterministically obtained due to the linearity of max-plus algebra.Indeed, the maxmin-m model is also shown to be deterministic and always reaches periodic behaviour. In the long time limit, this model is shown to be represented by a max-plus model, supporting its determinism further. Consequently, the complexity of such a model may be thought to be limited. However, we show through large scale experiments that the case where m is approximately n/2 generates most complex behaviour in terms of large periods and transients to the aforementioned periodic orbits. In particular, the complexity is empirically shown to obey a bell form as a function of m (where m ranges from 1 to n). The resulting cellular automaton simulations indicate a correspondence from the complexity of the update times. Therefore, cellular automaton behaviour may be predictable with the type of asynchrony employed in this thesis.

In max-plus algebra we work with the max-plus semi-ring which is the set ℝ_max=[-∞)∪ℝ together with operations 𝑎⊕𝑏 = max(𝑎,𝑏) and 𝑎⊗𝑏= 𝑎+𝑏.  The additive and multiplicative identities are taken to be ε=-∞ and ε=0 respectively. Max-plus algebra is one of many idempotent semi-rings which have been considered in various fields of mathematics. Max-plus algebra is becoming more popular not only because its operations are associative, commutative and distributive as in conventional algebra but because it takes systems that are non-linear in conventional algebra and makes them linear. Max-plus algebra also arises as the algebra of asymptotic growth rates of functions in conventional algebra which will play a significant role in several aspects of this thesis. This thesis is a survey of max-plus algebra that will concentrate on max-plus linear algebra results. We will then consider from a max-plus perspective several results by Wentzell and Freidlin for finite state Markov chains with an asymptotic dependence. / Master of Science

Nous construisons, pour les corps quadratiques imaginaires avec nombre de classes 1, un site arithmétique de type Connes-Consani. La principale difficulté ici est que les constructions de Connes et Consani et une partie de leurs résultats reposent sur la relation d'ordre naturellement présente sur les nombres réels qui est compatible avec les opérations arithmétiques basiques. Bien sûr rien de la sorte n'existe pas dans le cas des corps quadratiques imaginaires avec nombre de classes 1. Nous définissons ce que nous appelons le site arithmétique pour de tels corps de nombres, puis nous calculons les points de ces sites arithmétiques et nous les exprimons en termes de l'espace des classes d'adèles considéré par Connes pour donner une interprétation spectrale des zéros des fonctions L de Hecke. On obtient alors que pour un corps quadratique imaginaire avec nombre de classes 1, les points de notre site arithmétique sont reliés aux zéros de la fonction zêta de Dedekind du corps de nombres considéré et aux zéros de certaines fonctions L de Hecke. Nous étudions ensuite la relation entre le spectre de l'anneau des entiers du corps de nombres et le site arithmétique. Enfin nous construisons le carré du site arithmétique. / We construct, for imaginary quadratic number fields with class number 1, an arithmetic site of Connes-Consani type. The main difficulty here is that the constructions of Connes and Consani and part of their results strongly rely on the natural order existing on real numbers which is compatible with basic arithmetic operations. Of course nothing of this sort exists in the case of imaginary quadratic number fields with class number 1. We first define what we call arithmetic site for such number fields, we then calculate the points of those arithmetic sites and we express them in terms of the ad\`eles class space considered by Connes to give a spectral interpretation of zeroes of Hecke L functions of number fields. We get therefore that for a fixed imaginary quadratic number field with class number 1, that the points of our arithmetic site are related to the zeroes of the Dedekind zeta function of the number field considered and to the zeroes of some Hecke L functions. We then study the relation between the spectrum of the ring of integers of the number field and the arithmetic site. Finally we construct the square of the arithmetic site.

Submitted by Marcos Samuel (msamjunior@gmail.com) on 2016-06-07T13:27:47Z No. of bitstreams: 1 Dissertaçao Bruno Cesar.pdf: 764734 bytes, checksum: 3d0b35f72432678a4559b8ce350db5db (MD5) / Approved for entry into archive by Alda Lima da Silva (sivalda@ufba.br) on 2016-06-13T16:51:44Z (GMT) No. of bitstreams: 1 Dissertaçao Bruno Cesar.pdf: 764734 bytes, checksum: 3d0b35f72432678a4559b8ce350db5db (MD5) / Made available in DSpace on 2016-06-13T16:51:44Z (GMT). No. of bitstreams: 1 Dissertaçao Bruno Cesar.pdf: 764734 bytes, checksum: 3d0b35f72432678a4559b8ce350db5db (MD5) / Neste trabalho, vamos considerar uma função contínua definida em um espaço compacto Ω, o Princípio Variacional nos diz que ${\cal{P}}(A) . Considerando agora, em vez de , com , analisaremos o que acontece com . Faremos relações entre e medidas que realizam , onde é uma medida invariante e usaremos a álgebra Max-Plus como ferramenta para estudar o comportamento do

No description available.

No description available.

Often mathematics is seen by high school students as a science restricted to memorizing formulas and concepts. Therefore limiting in its essence. The work seeks to reverse that view by submitting a new eld of study: Tropical Algebra. Relatively new area of mathematics that keeps the curious feature to handle the operations of addition and multiplication di erently from traditional, already presents interesting practical results. Tropical algebra will be presented in a didactic way, comparing it with the traditional algebra, showing the consequences of tropical operations in the study of polynomials, matrices and geometry, and presenting some practical applications. / Frequentemente a matemática é vista pelos alunos do ensino médio como uma ciência restrita à memorização de fórmulas e conceitos. Portanto, limitante em sua essência. O trabalho busca reverter tal visão através da apresentação de um novo campo de estudos: A Àlgebra Tropical. Área relativamente nova da matemática que guarda a curiosa característica de tratar as operações de adi- ção e multiplicação de forma diferente da tradicional, já apresenta resultados práticos interessantes. A Àlgebra Tropical será apresentada de forma didática, comparando-a com a álgebra tradicional e mostrando as consequências das operações tropicais no estudo dos polinômios, matrizes e geometria, além de apresentar algumas aplicações práticas.

Les problèmes de contrôle stochastique optimal à horizon fini forment une classe de problèmes de contrôle optimal où interviennent des processus stochastiques considérés sur un intervalle de temps borné. Tout comme beaucoup de problème de contrôle optimal, ces problèmes sont résolus en utilisant le principe de la programmation dynamique qui induit une équation aux dérivées partielles (EDP) appelée équation d'Hamilton-Jacobi-Bellman. Les méthodes basées sur la discrétisation de l’espace sous forme de grille, les méthodes probabilistes ou plus récemment les méthodes max-plus peuvent alors être utilisées pour résoudre cette équation. Cependant, le premier type de méthode est mis en défaut quand un espace à dimension grande est considéré à cause de la malédiction de la dimension tandis que le deuxième type de méthode ne permettait jusqu'ici que de résoudre des problèmes où la non linéarité de l'équation aux dérivées partielles par rapport à la Hessienne n'est pas trop forte. Quant au troisième type de méthode, il entraine une explosion de la complexité de la fonction valeur. Nous introduisons dans cette thèse deux nouveaux schémas probabilistes permettant d'agrandir la classe des problèmes pouvant être résolus par les méthodes probabilistes. L'une est adaptée aux EDP à coefficients bornés tandis que l'autre peut être appliqué aux EDP à coefficients bornés ou non bornés. Nous prouvons la convergence des deux schémas probabilistes et obtenons des estimées de l'erreur de convergence dans le cas d'EDP à coefficients bornés. Nous donnons également quelques résultats sur le comportement du deuxième schéma dans le cas d'EDP à coefficients non bornés. Ensuite, nous introduisons une méthode complètement nouvelle pour résoudre les problèmes de contrôle stochastique optimal à horizon fini que nous appelons la méthode max-plus probabiliste. Elle permet d'utiliser le caractère non linéaire des méthodes max-plus dans un contexte probabiliste tout en contrôlant la complexité de la fonction valeur. Une application au calcul du prix de sur-réplication d'une option dans un modèle de corrélation incertaine est donnée dans le cas d’un espace à dimension 2 et 5. / Stochastic optimal control problems with finite horizon are a class of optimal control problems where intervene stochastic processes in a bounded time. As many optimal control problems, they are often solved using a dynamic programming approach which results in a second order Partial Differential Equation (PDE) called the Hamilton-Jacobi-Bellman equation. Grid-based methods, probabilistic methods or more recently max-plus methods can be used then to solve this PDE. However, the first type of methods default in a space of high dimension because of the curse of dimensionality while the second type of methods allowed till now to solve only problems where the nonlinearity of the PDE with respect to the second order derivatives is not very high. As for the third type of method, it results in an explosion of the complexity of the value function. We introduce two new probabilistic schemes in order to enlarge the class of problems that can be solved with probabilistic methods. One is adapted to PDE with bounded coefficients while the other can be applied to PDE with bounded or unbounded coefficients. We prove the convergence of the two probabilistic scheme and obtain error estimates in the case of a PDE with bounded coefficients. We also give some results about the behavior of the second probabilistic scheme in the case of a PDE with unbounded coefficients. After that, we introduce a completely new type of method to solve stochastic optimal control problems with finite horizon that we call the max-plus probabilistic method. It allows to add the non linearity feature of max-plus methods to a probabilistic method while controlling the complexity of the value function. An application to the computation of the optimal super replication price of an option in an uncertain correlation model is given in a 5 dimensional space.

Max-plus代数は，実数全体に無限小元を付加した集合に，加法として最大値をとる演算，乗法として通常の加法を考えた代数系である．本論文では，max-plus線形方程式に対するCramerの公式の類似物を用いて，線形方程式の解空間の基底が構成できることを示した．さらに固有値問題に関連して，max-plus行列の固有ベクトルの概念を2通りの観点から拡張した． / The max-plus algebra is the semiring with addition "max" and multiplication "+". In the present thesis, the author gives a combinatorial characterization of solutions of linear systems in terms of the max-plus Cramer's rule. Further, the author extends the concept of eigenvectors of max-plus matrices from two different perspectives. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

Heap models in the max-plus algebra are interesting dynamical systems that can be used to model a variety of tetris-like systems, such as batch flow shops for manufacturing models. Each heap in the model can be identified with a single product to manufacture. The objective is to manufacture a group of products in such an order so as to minimize the total manufacturing time. Because this scheduling problem reduces to a variation of the Traveling Salesman Problem (known to be NP-complete), the optimal solution is computationally infeasible for many real-world systems. Thus, a feasible approximation method is needed. This work builds on and expands the existing heap model in order to more effectively solve the scheduling problems. Specifically, this work:1. Further characterizes the admissible products to these systems.2. Further characterizes sets of admissible products. 3. Presents a novel algorithm, the asynchronous $t$-step approximation, to approximate these systems.4. Proves error bounds for the system approximation, and show why these error bounds are better than the existing approximation.