Orientador: Vanderlei Minori Horita / Banca: Isabel Lugão Rios / Banca: Claudio Aguinaldo Buzzi / Resumo: Neste trabalho vamos estudar equações diferenciais ordinárias e analisar seu comportamento ao longo de suas trajetórias, com o principal objetivo de encontar, caso possível, uma função de Lyapunov apropriada para o sistema, isto é, dar condição suficiente e necessária para a existência dessa função. / Abstract: In this work we study ordinary differential equations and analyse the behavior along of trajectories. The main goal is to find Lyapunov functions for the system when possibel: i e, we want to find necessary and sufficient conditions for the existence of those. / Mestre

Les sous-décalages sont des ensembles de coloriages d'un groupe définis en excluant certains motifs, et munis d'une action de décalage. Ces objets apparaissent naturellement comme discrétisations de systèmes dynamiques : à partir d'une partition de l'espace, on associe à chaque point de ce-dernier la suite des partitions visitées sous l'action du système.Plusieurs résultats récents ont mis en évidence la riche interaction entre la dynamique des sous-décalages et leur propriétés algorithmiques. Un exemple remarquable est la classification des entropies des sous-décalages multidimensionnels de type fini comme l'ensemble des nombres récursivement énumérables à droite. Cette thèse s'intéresse aux sous-décalages avec une approche double : d'un côté on s'intéresse à leurs propriétés dynamiques et de l'autre on les étudie comme des modèles de calcul.Cette thèse contient plusieurs résultats : une condition combinatoire suffisante prouvant qu'un sous-décalage dans un groupe dénombrable est non-vide, un théorème de simulation qui réalise une action effective d'un groupe de type fini comme un facteur d'une sous-action d'un sous-décalage de type fini, une caractérisation de l'effectivité à l'aide de machines de Turing généralisées et l'indécidabilité du problème de torsion pour deux groupes, qui sont invariants de systèmes dynamiques.Comme corollaires de nos résultats, nous obtenons d'abord une preuve courte de l'existence de sous-décalages fortement apériodiques sur tout groupe dénombrable. Puis, dans le cas d'un produit semi-direct de la grille bidimensionnelle avec un groupe de type fini avec problème du mot décidable, nous montrons que le sous-décalage obtenu est de type fini. / Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.Severa! breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the ether hand we studythese abjects as computational models.Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a d-dimensional integer lattice with a finitely generated group with decida ble word problem whenever d> 1.

La dualité et la robustesse sont des outils essentiels dans les processus d'aide à la décision. Cette thèse concerne trois thèmes: dualité en optimisation convexe conique à données incertaines, dualité et régularisation en convexité généralisée, et la maximisation du rayon de robustesse en optimisation continue. Dans la première partie de ce travail, on considère les notions de pire valeur et de valeur robuste d'un problème d'optimisation conique à données incertaines. On donne une condition nécessaire et suffisante pour l'égalité entre la pire valeur et la valeur robuste de ce problème avec exactitude de la pire valeur. On déduit une condition suffisante permettant d'obtenir la propriété de dualité robuste forte pour ce problème. La deuxième partie est consacrée à la dualité et à la régularisation de fonctions numériques à valeurs réelles étendues. Deux points de vue sont considérés: l'approche par les niveaux et l'approche par les épigraphes. On étend ainsi à la convexité généralisée des résultats récents concernant le passage de la dualité quasi-convexe à la dualité convexe. On applique cette théorie à un problème d'optimisation pour déduire un résultat de dualité forte. La troisième partie de ce travail porte une étude du problème de maximisation du rayon de stabilité. On définit le rayon de robustesse pour un problème de décision en milieu incertain, et on étudie certaines de ces propriétés analytiques (concavité et semi-continuité). La contrepartie robuste d'un problème d'optimisation à données incertaines au sens du rayon de robustesse est introduite. On étudie le lien en termes d'ensemble de solutions optimales entre la contrepartie robuste au sens du rayon de robustesse et celle au sens de l'optimisation robuste d'un problème incertain d'optimisation continue. Un modèle générique du problème de maximisation du rayon de robustesse regroupant une large classe de cas pratique est proposé. On examine ce modèle dans un cas polyédral, dans le cas de la régression linéaire puis dans un cas quadratique. Notre stratégie dans ces différents cas, consiste à expliciter le rayon de robustesse et/ou à transformer le problème de maximisation du rayon de stabilité en un programme tractable. Une application à un problème de conception d'antenne circulaire est proposée dans le cas de la régression et une application au calcul d'un estimateur robuste est proposée dans le cas quadratique. / Duality and robustness are two important tools in decision making process. This thesis deals with tree topics : duality for an uncertain convex conical optimization problem, duality and regularity in generalized convexity, and the maximization of the stability radius. In the first part of this work, we consider the notions of worst value and robust value of an uncertain convex conical optimization problem. We give a necessary and sufficient condition to obtain the equality between the robust value and the worst value with exactness for the worst value. We derive a sufficient condition to obtain a robust strong duality property for this problem. The second part of this work is devoted to duality and regularity of the extended real-valued functions. Two points of view are considered: the sub-level set approach and the epigraphical approach. We then extend some recent results concerning the passage from the quasi-convex duality to convex duality to the generalized convexity. We apply this theory to an optimization problem to derive a strong duality property for this problem. The third part of this work is devoted to the study of the problem of maximization of the stability radius. We define the stability radius for a decision problem under data uncertainty, and study some of its analytical properties (e.g concavity and upper semi-continuity). The robust counterpart of an uncertain optimization problem according to the stability radius is introduced. We study the relation between the solution set of this counterpart and the solution set of the robust counterpart according to the robust optimization approach. We propose a generic model of the maximization of stability radius which covers a large class of applications. We study this problem in a polyhedral case, in the case of regression and in quadratic case. In each case, we compute the stability radius and/ or transform the problem of maximization of the stability radius to a tractable problem. An application to a circular antenna design problem is given in the regression case, and an application to compute a robust estimator is provided in the quadratic case.

We will extend the conjugacy problem of maximal toral subalgebras for Lie algebras of the form $\g{g} \otimes_k R$ by considering $R=k[t,t^{-1}]$ and $R=k[t,t^{-1},(t-1)^{-1}]$, where $k$ is an algebraically closed field of characteristic zero and $\g{g}$ is a direct limit Lie algebra. In the process, we study properties of infinite matrices with entries in a B\'zout domain and we also look at how our conjugacy results extend to universal central extensions of the suitable direct limit Lie algebras.

We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \''komprimiertes Wortproblem\'' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Systeme mit Zeitverzögerung sind dadurch charakterisiert, dass deren zukünftige Entwicklung durch den Zustand zum aktuellen Zeitpunkt nicht eindeutig festgelegt ist. Die Historie des Zustands muss in einem Zeitraum bekannt sein, dessen Länge Totzeit genannt wird und die Gedächtnislänge festlegt. In dieser Arbeit werden fundamentale Effekte untersucht, die sich ergeben, wenn die Totzeit zeitlich variiert wird. Im ersten Teil werden zwei Klassen periodischer Totzeitvariationen eingeführt. Da diese von den dynamischen Eigenschaften einer eindimensionalen iterierten Abbildung abgeleitet werden, die über die Totzeit definiert wird, werden die Klassen entsprechend der zugehörigen Dynamik konservativ oder dissipativ genannt. Systeme mit konservativer Totzeit können in Systeme mit konstanter Totzeit transformiert werden und besitzen gleiche charakteristische Eigenschaften. Dagegen weisen Systeme mit dissipativer Totzeit fundamentale Unterschiede z.B. in der Tangentialraumdynamik auf. Im zweiten Teil werden diese Ergebnisse auf Systeme angewendet, deren Totzeit im Vergleich zur internen Relaxationszeit des Systems groß ist. Es zeigt sich, dass ein durch dissipative Totzeitvariationen induzierter Mechanismus, genannt resonanter Dopplereffekt, unter anderem zu neuen Arten chaotischer Dynamik führt. Diese sind im Vergleich zur bekannten chaotischen Dynamik in Systemen mit konstanter Totzeit sehr niedrig-dimensional. Als Spezialfall wird das so genannte laminare Chaos betrachtet, dessen Zeitreihen durch nahezu konstante Phasen periodischer Dauer gekennzeichnet sind, deren Amplitude chaotisch variiert. Im dritten Teil dieser Arbeit wird auf der Basis experimenteller Daten und durch die Analyse einer nichtlinearen retardierten Langevin-Gleichung gezeigt, dass laminares Chaos robust gegenüber Störungen wie zum Beispiel Rauschen ist und experimentell realisiert werden kann. Es werden Methoden zur Zeitreihenanalyse entwickelt, um laminares Chaos in experimentellen Daten ohne Kenntnis des erzeugenden Systems zu detektieren. Mit diesen Methoden ist selbst dann eine Detektion möglich, wenn das Rauschen so stark ist, dass laminares Chaos mit bloßem Auge nur schwer erkennbar ist.:1. Introduction 2. Dissipative and conservative delays in systems with time-varying delay 3. Laminar Chaos and the resonant Doppler effect 4. Laminar Chaos: a robust phenomenon 5. Summary and concluding remarks A. Appendix / In systems with time-delay, the evolution of a system is not uniquely determined by the state at the current time. The history of the state must be known for a time period of finite duration, where the duration is called delay and determines the memory length of the system. In this work, fundamental effects arising from a temporal variation of the time-delay are investigated. In the first part, two classes of periodically time-varying delays are introduced. They are related to a specific dynamics of a one-dimensional iterated map that is defined by the time-varying delay. Referring to the related map dynamics the classes are called conservative or dissipative. Systems with conservative delay can be transformed into systems with constant delay, and thus have the same characteristic properties as constant delay systems. In contrast, there are fundamental differences, for instance, in the tangent space dynamics, between systems with dissipative delay and systems with constant delay. In the second part, these results are applied to systems with a delay that is considered large compared to the internal relaxation time of the system. It is shown that a mechanism induced by dissipative delays leads to new kinds of regular and chaotic dynamics. The dynamics caused by the so-called resonant Doppler effect is fundamentally different from the behavior known from systems with constant delay. For instance, the chaotic attractors in systems with dissipative delay are very low-dimensional compared to typical ones arising in systems with constant delay. An example of this new kind of low-dimensional dynamics is given by the so-called Laminar Chaos. It is characterized by nearly constant laminar phases of periodic duration, where the amplitude varies chaotically. In the third part of this work, it is shown that Laminar Chaos is a robust phenomenon, which survives perturbations such as noise and can be observed experimentally. Therefore experimental data is provided and a nonlinear delayed Langevin equation is analyzed. Using the robust features that characterize Laminar Chaos, methods for time series analysis are developed, which enable us to detect Laminar Chaos without the knowledge of the specific system that has generated the time series. By these methods Laminar Chaos can be detected even for comparably large noise strengths, where the characteristic properties are nearly invisible to the eye.:1. Introduction 2. Dissipative and conservative delays in systems with time-varying delay 3. Laminar Chaos and the resonant Doppler effect 4. Laminar Chaos: a robust phenomenon 5. Summary and concluding remarks A. Appendix