Rozprawy doktorskie na temat „Infinite”

Les principaux sujets d'intérêt de cette thèse concerneront deux notions de la complexité d'un mot infini : la complexité abélienne et la complexité de permutation. La complexité abélienne a été étudiée durant les dernières décennies. La complexité de permutation est, elle, une forme de complexité des mots relativement nouvelle qui associe à chaque mot apériodique de manière naturelle une permutation infinie. Nous nous pencherons sur deux sujets dans le domaine de la complexité abélienne. Dans un premier temps, nous nous intéresserons à une notion abélienne de la maximal pattern complexity définie par T. Kamae. Deuxièmement, nous analyserons une limite supérieure de cette complexité pour les mots C-équilibré. Dans le domaine de la complexité de permutation des mots apériodiques binaires, nous établissons une formule pour la complexité de permutation du mot de Thue-Morse, conjecturée par Makarov, en étudiant la combinatoire des sous-permutations sous l'action du morphisme de Thue-Morse. Par la suite, nous donnons une méthode générale pour calculer la complexité de permutation de l'image de certains mots sous l'application du morphisme du doublement des lettres. Finalement, nous déterminons la complexité de permutation de l'image du mot de Thue-Morse et d'un mot Sturmien sous l'application du morphisme du doublement des lettres
The main topics of interest in this thesis will be two types of complexity, abelian complexity and permutation complexity. Abelian complexity has been investigated over the past decades. Permutation complexity is a relatively new type of word complexity which investigates lexicographical ordering of shifts of an aperiodic word. We will investigate two topics in the area of abelian complexity. Firstly we will consider an abelian variation of maximal pattern complexity. Secondly we consider an upper bound for words with the C-balance property. In the area of permutation complexity, we compute the permutation complexity function for a number of words. A formula for the complexity of Thue-Morse word is established by studying patterns in subpermutations and the action of the Thue-Morse morphism on the subpermutations. We then give a method to calculate the complexity of the image of certain words under the doubling map. The permutation complexity function of the image of the Thue-Morse word under the doubling map and the image of a Sturmian word under the doubling map are established

How many equivalence classes of geodesic rays does a graph contain? How many bounded automorphisms does a planar graph have? Neimayer and Watkins studied these two questions and answered them for a certain class of graphs. Using the concept of excess of a vertex, the class of graphs that Neimayer and Watkins studied are extended to include graphs with positive excess at each vertex. The results of this paper show that there are an uncountable number of geodesic fibers for graphs in this extended class and that for any graph in this extended class the only bounded automorphism is the identity automorphism.

The theory of infinite multiplication has been studied in the case of the Hawaiian earring group, and has been seen to simplify the description of that group. In this paper we try to extend the theory of infinite multiplication to other groups and give a few examples of how this can be done. In particular, we discuss the theory as applied to symmetric groups and braid groups. We also give an equivalent definition to K. Eda's infinitary product as the fundamental group of a modified wedge product.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Chemical Engineering, 2008.
Includes bibliographical references (p. 235-249).
The goals of this thesis are the development of global optimization algorithms for semi-infinite and generalized semi-infinite programs and the application of these algorithms to kinetic model reduction. The outstanding issue with semi-infinite programming (SIP) was a methodology that could provide a certificate of global optimality on finite termination for SIP with nonconvex functions participating. We have developed the first methodology that can generate guaranteed feasible points for SIP and provide e-global optimality on finite termination. The algorithm has been implemented in a branch-and-bound (B&B) framework and uses discretization coupled with convexification for the lower bounding problem and the interval constrained reformulation for the upper bounding problem. Within the framework of SIP we have also proposed a number of feasible-point methods that all rely on the same basic principle; the relaxation of the lower-level problem causes a restriction of the outer problem and vice versa. All these methodologies were tested using the Watson test set. It was concluded that the concave overestimation of the SIP constraint using McCormcick relaxations and a KKT treatment of the resulting expression is the most computationally expensive method but provides tighter bounds than the interval constrained reformulation or a concave overestimator of the SIP constraint followed by linearization. All methods can work very efficiently for small problems (1-3 parameters) but suffer from the drawback that in order to converge to the global solution value the parameter set needs to subdivided. Therefore, for problems with more than 4 parameters, intractable subproblems arise very high in the B&B tree and render global solution of the whole problem infeasible.
(cont.) The second contribution of the thesis was the development of the first finite procedure that generates guaranteed feasible points and a certificate of e-global optimality for generalized semi-infinite programs (GSIP) with nonconvex functions participating. The algorithm employs interval extensions on the lower-level inequality constraints and then uses discretization and the interval constrained reformulation for the lower and upper bounding subproblems, respectively. We have demonstrated that our method can handle the irregular behavior of GSIP, such as the non-closedness of the feasible set, the existence of re-entrant corner points, the infimum not being attained and above all, problems with nonconvex functions participating. Finally, we have proposed an extensive test set consisting of both literature an original examples. Similar to the case of SIP, to guarantee e-convergence the parameter set needs to be subdivided and therefore, only small examples (1-3 parameters) can be handled in this framework in reasonable computational times (at present). The final contribution of the thesis was the development of techniques to provide optimal ranges of valid reduction between full and reduced kinetic models. First of all, we demonstrated that kinetic model reduction is a design centering problem and explored alternative optimization formulations such as SIP, GSIP and bilevel programming. Secondly, we showed that our SIP and GSIP techniques are probably not capable of handling large-scale systems, even if kinetic model reduction has a very special structure, because of the need for subdivision which leads to an explosion in the number of constraints. Finally, we propose alternative ways of estimating feasible regions of valid reduction using interval theory, critical points and line minimization.
by Panayiotis Lemonidis.
Ph.D.

In this thesis some essential aspects of an infinite derivative theory of gravity are studied. Namely, we considered the Hamiltonian formalism, where the true physical degrees of freedom for infinite derivative scalar models and infinite derivative gravity are obtained. Furthermore, the Gibbons-Hawking-York boundary term for the infinite derivative theory of gravity was obtained. Finally, we considered the thermodynamical aspects of the infinite derivative theory of gravity over different backgrounds. Throughout the thesis, our methodology is applied to other modified theories of gravity as a check and validation. Infinite derivative theory of gravity is a modification to the general theory of relativity. Such modification maintains the massless gravi- ton as the only true physical degree of freedom and avoids ghosts. Moreover, this class of modified gravity can address classical singularities.

In this study of David Foster Wallace’s Infinite Jest, I combine the linguistic and literary theories of renowned scholar Mikhail Bakhtin to create a new lens through which to consider Wallace’s thematic project. Combining Bakhtin’s linguistic theories of dialogic conflict and heteroglossia with his literary theories on the grotesque provides an integrated stylistic methodology that illustrates the connections between Wallace’s use of imagery and style. In view of his use of both grotesque liminal imagery and dialogized heteroglossia, Wallace’s seemingly obsessive use of language is recast as a manifestation of grotesque embodiment that reflects the postmodern mileau in which he writes. I propose that Wallace crafts a series of grotesque stylistic devices that shape his words to match his theme. I propose two particular grotesque stylistic devices: narrative bleed in which the seemingly neutral narrative voice begins to reflect particular character discourses and character-to-character voice bleed in which dialogic conflict between characters is dramatically rendered within the novel.

In a world where technology advances, it is important that the human-computer interface follows in the same pace, to maximize the user experience. This means that when the machines become more powerful and the services become more comprehensive, it is important that they still are adapted to the users.In the web browsing world, a concept called infinite-scroll has become popular when trying to maximise the user experience. This technique uses JavaScript to dynamically load more content to a webpage whilst the user is scrolling without ever reloading the page, to achieve a more fluid experience. This technique is used widely in social media websites such as Facebook and Twitter among others.However, this technique have been used very rarely on other types of websites. Why this could be the case and how infinite-scroll performs on an intranet will be described in this report. A quantitative study on how the user behaviour differs between a website with pagination and infinite-scroll has been conducted and analysed by gathering statistics through Google Analytics about how users interacts with the website in question. The study indicates that infinite-scroll can be useful on an intranet when adapted according to usability guidelines.

This dissertation describes the rigidity theory of bar joint frameworks, especially infinite ones. The first chapter revises some of the well established results for finite frameworks. We then look at how this can be extended to the infinite case, specifically from the analysis point of view. In particular, we look at vanishing flexibility that is observed in some specific examples. Then we look at a proof of the sufficient condition for the existence of a flex in an infinite framework as described in Owen and Power [6]. In the fourth chapter we establish that the rigidity operator arising from the infinite matrix is bounded. 'Ve then observe its structure for specific examples. As decribed in [8], we describe the representation of the rigidity operator as a matrix valued function on the torus. Finally we look at the decomposition of the space of infinitesimal flexes for crystal frameworks in terms of a product basis.

Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet, auf endlichen Strukturen, ist bekanntermassen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen, wie Constraint Satisfaction Problems (CSP): Im Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen, dass Datalog auf linearen Ordnungen (auch dichte und diskrete, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist. Für die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme, die sich ohne Rekursion lösen lassen. Ein Transfer unserer Methoden auf CSPs zeigt, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen, wie Datalog.
Datalog is the relational variant of logic programming and has become a standard query language in database theory. The (program) complexity of datalog in its main context so far, on finite databases, is well known to be in EXPTIME. We research the complexity of datalog on infinite databases, motivated by possible applications of datalog to infinite structures (e.g. linear orders) in temporal and spatial reasoning on one hand and the upcoming interest in infinite structures in problems related to datalog, like constraint satisfaction problems: Unlike datalog on finite databases, on infinite structures the computations may take infinitely long, leading to the undecidability of datalog on some infinite structures. But even in the decidable cases datalog on infinite structures may have arbitrarily high complexity, and because of this result, we research some structures with the lowest complexity of datalog on infinite structures: Datalog on linear orders (also dense or discrete, with and without constants, even colored) and tree orders has EXPTIME-complete complexity. To achieve the upper bound on these structures, we introduce a tool set specialized for datalog on orders: Order types, distance types and type disjoint programs. The type concept yields a finite representation of the infinite program results, which could also be of interest for practical applications. We create special type disjoint versions of the programs allowing to solve datalog without the recursion inherent in each datalog program. A transfer of our methods shows that constraint satisfaction problems on infinite structures occur with arbitrarily high time complexity, like datalog.

The objective of this thesis is to study classical and quantum aspects of infinite derivative field theories and infinite derivative gravity. In- finite derivative theories of gravity can be made free from ghosts and classical singularities. In order to avoid ghosts, one modifies the graviton propagator by employing entire functions so that no new poles are introduced apart from the pole corresponding to the massless graviton of General Relativity. Inspired by infinite derivative gravity, we consider an infinite derivative scalar toy model and demonstrate renormalisability when the loop-order is arbitrarily large. Moreover, scattering diagrams within the framework of infinite derivative field theories are explicitly evaluated and it is shown that the cross section can be made finite. Finally, we perform a Hamiltonian analysis of an infinite derivative gravitational theory with a simpler action containing only the Ricci scalar and compute the number of relevant degrees of freedom.

By first looking at the orthonormal basis: Γ = {∑i 4 ibi ∈{0, 1}, finite sums} and the related orthonormal basis 5Γ = {5∑i 4i bi : bi ∈ {0, 1}, finite sums} we find several interesting relationships with the unitary matrix Uα,β arising from the operator U: Γ → 5Γ. Further, we investigate the relationships between U and the operators So : Γ → 4Γ defined by Soe4γ where eγ = e2ΠiΓ and S1: Γ → 4Γ+1 defined by S1eγ = e4γ+1. Most intriguing, we found that when taking powers of the aforementioned Uα,β matrix that although there are infinitely many 1's occurring in the entries of Uα,β only one such 1 occurs in the subsequent higher powers Ukα,β. This means that there are infinitely many γ ∈ Γ ∩ 5Γ, but only one such γ in the intersection Γ and 5kΓ, for k ≥ 2.

This is a contribution to combinatorial set theory, specifically to infinite Ramsey Theory, which deals with partitions of infinite sets. The basic pigeon hole principle states that for every partition of the set of all natural numbers in finitely many classes there is an infinite set of natural numbers that is included in some one class. Ramsey’s Theorem, which can be seen as a generalization of this simple result, is about partitions of the set [N]k of all k-element sets of natural numbers. It states that for every k ≥ 1 and every partition of [N]k into finitely many classes, there is an infinite subset M of N such that all k-element subsets of M belong to some same class. Such a set is said to be homogeneous for the partition. In Ramsey’s own formulation (Ramsey, [8], p.264), the theorem reads as follows. Theorem (Ramsey). Let Γ be an infinite class, and μ and r positive numbers; and let all those sub-classes of Γ which have exactly r numbers, or, as we may say, let all r−combinations of the members of Γ be divided in any manner into μ mutually exclusive classes Ci (i = 1, 2, . . . , μ), so that every r−combination is a member of one and only one Ci; then assuming the axiom of selections, Γ must contain an infinite sub-class △ such that all the r−combinations of the members of △ belong to the same Ci. In [5], Neil Hindman proved a Ramsey-like result that was conjectured by Graham and Rotschild in [3]. Hindman’s Theorem asserts that if the set of all natural numbers is divided into two classes, one of the classes contains an infinite set such that all finite sums of distinct members of the set remain in the same class. Hindman’s original proof was greatly simplified, though the same basic ideas were used, by James Baumgartner in [1]. We will give new proofs of these two theorems which rely on forcing arguments. After this, we will be concerned with the particular partial orders used in each case, with the aim of studying its basic properties and its relations to other similar forcing notions. The partial order used to get Ramsey’s Theorem will be seen to be equivalent to Mathias forcing. The analysis of the partial order arising in the proof of Hindmans Theorem, which we denote by PFIN, will be object of the last chapter of the thesis. A summary of our work follows. In the first chapter we give some basic definitions and state several known theorems that we will need. We explain the set theoretic notation used and we describe some forcing notions that will be useful in the sequel. Our notation is generally standard, and when it is not it will be sufficiently explained. This work is meant to be self-contained. Thus, although most of the theorems recorded in this first, preliminary chapter, will be stated without proof, it will be duly indicated where a proof can be found. Chapter 2 is devoted to a proof of Ramsey’s Theorem in which forcing is used to produce a homogeneous set for the relevant partition. The partial order involved is isomorphic to Mathias forcing. In Chapter 3 we modify Baumgartner’s proof of Hindman’s Theorem to define a partial order, denoted by PC , from which we get by a forcing argument a suitable homogeneous set. Here C is an infinite set of finite subsets of N, and PC adds an infinite block sequence of finite subsets of natural numbers with the property that all finite unions of its elements belong to C. Our proof follows closely Baumgartner’s. The partial order PC is similar both to the one due to Matet in [6] and to Mathias forcing. This prompts the question whether it is equivalent to one of them or to none, which can only be solved by studying PC , which we do in chapter 4. In chapter 4 we first show that the forcing notion PC is equivalent to a more manageable partial order, which we denote by PFIN. From a PFIN- generic filter an infinite block sequence can be defined, from which, in turn, the generic filter can be reconstructed, roughly as a Mathias generic filter can be reconstructed from a Mathias real. In section 4.1 we prove that PFIN is not equivalent to Matet forcing. This we do by showing that PFIN adds a dominating real, thus also a splitting real (see [4]). But Blass proved that Matet forcing preserves p-point ultrafilters in [2], from which follows that Matet forcing does not add splitting reals. Still in section 4.1 we prove that PFIN adds a Mathias real by using Mathias characterization of a Mathias real in [7] according to which x ⊆ ω is a Mathias real over V iff x diagonalizes every maximal almost disjoint family in V . In fact, we prove that if D = (Di)i∈ω is the generic block sequence of finite sets of natural numbers added by forcing with PFIN, then both {minDi : i ∈ ω} and {maxDi : i ∈ ω} are Mathias reals. In section 4.2 we prove that PFIN is equivalent to a two-step iteration of a σ-closed and a σ-centered forcing notions. In section 4.3 we prove that PFIN satisfies Axiom A and in section 4.4 that, as Mathias forcing, it has the pure decision property. In section 4.5 we prove that PFIN does not add Cohen reals. So far, all the properties we have found of PFIN are also shared by Mathias forcing. The question remains, then, whether PFIN is equivalent to Mathias forcing. This we solve by first showing in section 5.1 that PFIN adds a Matet real and then, in section 5.2, that Mathias forcing does not add a Matet real, thus concluding that PFIN and Mathias forcing are not equivalent forcing notions. In the last, 5.3, section we explore another forcing notion, denoted by M2, which was introduced by Shelah in [9]. It is a kind of “product” of two copies of Mathias forcing, which we relate to denoted by M2. Bibliography [1] J.E. Baumgartner. A short proof of Hindmanʼs theorem. Journal of Combinatorial Theory, 17:384–386, 1974. [2] A. Blass. Applications of superperfect forcing and its relatives. In Set theory and its applications. Lecture notes in Mathematics. Springer, Berlin., 1989. [3] R.L. Graham and B. L. Rothschild. Ramseyʼs theorem for n-parameter sets. Transaction American Mathematical Society, 159:257–292, 1971. [4] L. Halbeisen. A playful approach to Silver and Mathias forcing. Studies in Logic (London), 11:123142, 2007. [5] N. Hindman. Finite sums from sequences within cells of partition of N. Journal of Combinatorial Theory (A), 17:1–11, 1974. [6] P. Matet. Some filters of partitions. The Journal of Symbolic Logic, 53:540– 553, 1988. [7] A.R.D. Mathias. Happy families. Annals of Mathematical logic, 12:59– 111, 1977. [8] F.P. Ramsey. On a problem of formal logic. London Mathematical Society, 30:264–286, 1930. [9] S. Shelah and O. Spinas. The distributivity numbers of finite products of P(ω)/fin. Fundamenta Mathematicae, 158:81–93, 1998.
Aquesta tesi és una contribució a la teoria combinatria de conjunts, específcament a la teoria de Ramsey, que estudia les particions de conjunts infinits. El principi combinatori bàsic diu que per a tota partició del conjunt dels nombres naturals en un nombre finit de classes hi ha un conjunt infinit de nombres naturals que està inclòs en una de les classes. El teorema de Ramsey [6], que hom pot veure com una generalització d'aquest principi bàsic, tracta de les particions del conjunt [N]k de tots els subconjunts de k elements de nombres naturals. Afirma que, per a cada k >/=1 i cada partició de [N]k en un nombre finit de classes, existeix un subconjunt infinit de nombres naturals, M, tal que tots els subconjunts de k elements de M pertanyen a una mateixa classe. Els conjunts amb aquesta propietat són homogenis per a la partició. En [3], Neil Hindman va demostrar un resultat de tipus Ramsey que Graham i Rotschild havien conjecturat en [2]. El teorema de Hindman afirma que si el conjunt de nombres naturals es divideix en dues classes, almenys una d'aquestes classes conté un conjunt infinit tal que totes les sumes finites d'elements distints del conjunt pertanyen a la mateixa classe. La demostració original del Teorema de Hindman va ser simplificada per James Baumgartner en [1]. En aquesta tesi donem noves demostracions d'aquests dos teoremes, basades en la tècnica del forcing. Després, analitzem els ordres parcials corresponents i n'estudiem les propietats i la relació amb altres ordres coneguts semblants. L'ordre parcial emprat en la demostració del teorema de Ramsey és equivalent al forcing de Mathias, definit en [5]. L'ordre parcial que apareix en la prova del teorema de Hindman, que anomenem PFIN, serà l'objecte d'estudi principal de la tesi. En el primer capítol donem algunes definicions bàsiques i enunciem alguns teoremes coneguts que necessitarem més endavant. El segon capítol conté la demostració del teorema de Ramsey. Usant la tècnica del forcing, produïm un conjunt homogeni per a una partició donada. L'ordre parcial que utilitzem és equivalent al de Mathias. En el tercer capítol, modifiquem la demostració de Baumgartner del teorema de Hindman per definir un ordre parcial, que anomenem PC , a partir del qual, mitjançant arguments de forcing, obtenim el conjunt homogeni buscat. Aquí, C es un conjunt infinit de conjunts finits disjunts de nombres naturals, i PC afegeix una successió de conjunts finits de nombres naturals amb la propietat de que totes les unions finites de elements d'aquesta successió pertanyen al conjunt C . A partir d'aquesta successió és fàcil obtenir un conjunt homogeni per a la partició del teorema original de Hindman. L'ordre parcial PC és similar a l'ordre definit per Pierre Matet en [4] i també al forcing de Mathias. Per això, és natural preguntar-nos si aquests ordres són equivalents o no. En el quart capítol treballem amb un ordre parcial que és equivalent a PC i que anomenem PFIN. Mostrem que PFIN té les propietats següents: (1) A partir d'un filtre genèric per a PFIN obtenim una successió infinita de conjunts finits de nombres naturals. Com en el cas del real de Mathias, aquesta successi_o ens permet reconstruir tot el filtre genèric. (2) PFIN afegeix un real de Mathias, que és un "dominating real". Ara bé, si afegim un "dominating real" afegim també un "splitting real". Aquest fet ens permet concloure que PFIN no és equivalent al forcing de Matet, ja que el forcing de Matet no afegeix "splitting reals" (3) PFIN es pot veure com una iteració de dos ordres parcials, el primer dels quals és "sigma-closed" i el segon és "sigma-centered". (4) PFIN té la "pure decision property". (5) PFIN no afegeix reals de Cohen. En el cinquè capítol demostrem que PFIN afegeix un real de Matet i, finalment, que el forcing de Mathias no afegeix reals de Matet. Això és com demostrem que el forcing de Mathias i PFIN no són ordres equivalents. Al final del capítol donem una aplicació de PFIN. Demostrem que un cert ordre definit per Saharon Shelah en [7], que anomenem M2, és una projecció de PFIN. Això implica que si G és un filtre PFIN-genèric sobre V, l'extensió V [G] conté també un filtre genèric per a M2. L'ordre M2 és una mena de producte de dues cópies del forcing de Mathias. REFERÈNCIES [1] J.E. Baumgartner. A short proof of Hindman's theorem, Journal of Combinatorial Theory, 17: 384-386, (1974). [2] R.L. Graham and B.L. Rothschild. Ramsey's theorem for m-parameter sets, Transaction American Mathematical Society, 159: 257-292, (1971). [3] N. Hindman. Finite sums from sequences within cells of partitions of N, Journal of Combinatorial Theory (A), 17: 1-11, (1974). [4] P. Matet. Some _lters of partitions, The Journal of Symbolic Logic, 53: 540-553, (1988). [5] A.R.D. Mathias. Happy families, Annals of Mathematical Logic, 12: 59-111, (1977). [6] F.P. Ramsey. On a problem of formal logic, London Mathematical Society, 30:264_D286, 1930. [7] S. Shelah and O. Spinas. The distributivity numbers of finite products of P(!)=fin, Fundamenta Mathematicae, 158:81_D93, 1998.

Modern data collection methods are now frequently returning observations that should be viewed as the result of digitized recording or sampling from stochastic processes rather than vectors of finite length. In spite of great demands, only a few classification methodologies for such data have been suggested and supporting theory is quite limited. The focus of this dissertation is on discrimination and classification in this infinite dimensional setting. The methodology and theory we develop are based on the abstract canonical correlation concept of Eubank and Hsing (2005), and motivated by the fact that Fisher's discriminant analysis method is intimately tied to canonical correlation analysis. Specifically, we have developed a theoretical framework for discrimination and classification of sample paths from stochastic processes through use of the Loeve-Parzen isomorphism that connects a second order process to the reproducing kernel Hilbert space generated by its covariance kernel. This approach provides a seamless transition between the finite and infinite dimensional settings and lends itself well to computation via smoothing and regularization. In addition, we have developed a new computational procedure and illustrated it with simulated data and Canadian weather data.

Real time systems distinguish themselves by explicitly stating timing constraints in the system specification. This requires specific methods and tools in system design to ensure such constraints. We focus on one of the methods applied in the validation phase, namely formal verification. This method automatically establishes correctness of the system model with mathematical rigor. In order to apply mechanical procedures to determine whether the system satisfies the requirements, we first have to model the validated part of the system in a mathematical form. This thesis deals with one such formalism - timed automata - and investigates different types of infinite state structures arising in the verification procedures related to this formalism. There are two different views which open the door for introduction of such structures. First, we turn outwards and extend timed automata with additional infinite data structures - unbounded queues. These queues serve different purposes. In one case, the queues contain computation tasks and, together with a timed automaton, model a real-time system with tasks. The problem of interest in this setting is schedulability analysis. We investigate the decidability boundary in presence of various features such as preemption, variable computation times of tasks, and communication between the timed automaton and the task queue. In the other case, we use queues for asynchronous communication between timed automata running synchronously in parallel. These queues store messages issued by one automaton and waiting to be read by another automaton. Such situations occur among other cases in real-time control systems where several concurrently running tasks communicate via buffers. We study the decidability border for reachability analysis depending on various communication topologies of these systems. Secondly, we turn inwards and study a peculiar feature of timed automata which allows them to enforce behaviors where time distances between events monotonically grow while being bounded by some integer. This feature can be characterized by unbounded counters recording the number of such enforced increases. When we switch from the dense time semantics used for modeling to an implementation with a fixed clock rate (sampled semantics), only behaviors which correspond to a bounded usage of these counters are preserved. We describe operation of these counters as a new type of a counter automaton and prove that one can effectively check whether the counters are used in a bounded way. As a result, it is possible to check for a given timed automaton whether there is an implementation with a fixed sampling rate which preserves all qualitative behaviors.

The subject of infinite series and the properties thereof are explored, showing the theorems of Bernhard Riemann, Augustin Louis Cauchy, Otto Toeplitz, Franz Mertens and Niels Henrik Abel, among others and also several standard and nonstandard examples and problems where these theorems are useful.
Oändliga serier och deras egenskaper utforskas med hjälp av satser av bland andra Bernhard Riemann, Augustin Louis Cauchy, Otto Toeplitz, Franz Mertens och Niels Henrik Abel. Flertalet exempel och problem där dessa satser är användbara presenteras och löses.

The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical adjacent blocks) xx. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well. In this thesis we primarily study several variations of the problems studied by Thue in his work on repetitions in words, including some recent connections to other areas, such as graph theory. In Chapter 1 we give a brief introduction to the subject of combinatorics on words. In Chapter 2 we use uniform morphisms to construct an infinite binary word that contains no cubes xxx and no squares yy with |y| ≥ 4, thus giving a simpler construction than that of Dekking. We also use uniform morphisms to construct an infinite binary word avoiding all squares except 0², 1², and (01)², thus giving a simpler construction than that of Fraenkel and Simpson. We give some new enumeration results for these avoidance properties and solve an open problem of Prodinger and Urbanek regarding the perfect shuffle of infinite binary words that avoid arbitrarily large squares. In Chapter 3 we examine ternary squarefree words in more detail, and in Chapter 4 we study words w satisfying the property that for any sufficiently long subword w' of w, w does not contain the reversal of w' as a subword. In Chapter 5 we discuss an application of the property of squarefreeness to colourings of graphs. In Chapter 6 we study strictly increasing sequences (a(n))n≥0 of non-negative integers satisfying the equation a(a(n)) = dn. Finally, in Chapter 7 we give a brief conclusion and present some open problems.

The description of a black hole in the limit of very large number of spacetime dimensions D simplifies considerably. When D approaches infinity, the gravitational field lines of force are infinitely dispersed among the infite number of spacetime directions. This implies that outside the near-horizon region of the black hole the background spacetime will be flat, while the gravitational field will be strongly localized near the horizon. Thus, we can attempt to replace the black hole by a sphere cut off at the horizon in an empty background. In this project we attempt to obtain the physical conditions that the sphere has to meet in order to be able to reproduce the dynamics of the black hole when embedded in the empty background. This is described in the effective equation that we derive starting from the Einstein equations. Finally, we apply our results to take a look at ’black droplets’, black holes localized at the boundary of AdS and extending a finite distance into the bulk.

Optimisation problems occur in many branches of science, engineering, and economics, as well as in other areas. The diversity of the various types of optimisation problems is extremely large, and so a unified approach is not attempted here. This thesis concentrates on a specific type of problem: non-linear semi-infinite programming.

The results contained within this thesis concern an abstract framework for a robustness analysis of exponential stability of infinite dimensional systems. The abstract analysis relies on the strong relationship between exponential stability and L2-stability which exists for many classes of linear systems. In Chapter 1a "stability radius", for systems governed by semigroups, is developed, for a class of "structured" perturbations of its generator. The abstract theory is illustrated by examples of perturbations of the boundary data for homogeneous boundary value problems and also perturbations arising due to neglected delay terms in differential delay equations. In Chapter 2a related problem of a non standard linear quadratic problem is studied, which leads to a stability analysis for certain nonlinear systems. In Chapter 3 an abstract L2-stability theory is developed and then applied to integrodifferential equations and time-varying systems, to investigate the robustness of exponential stability of such systems.

The main objects of interest in this thesis are H1F-groups. These are groups that act on finite-dimensional contractible CW-spaces with finite stabilisers. Important examples of these are given by groups admitting a finite-dimensional classifying space for proper actions EFG. A large part of the thesis is motivated by an old conjecture of Kropholler and Mislin claiming that every H1F-group G admits a finite-dimensional model for EFG. The natural choice for studying algebraically H1F-groups is F-cohomology. This is a form of group cohomology relative to a G-set introduced by Nucinkis in 1999. In this theory there is a well-defined notion of F-cohomological dimension and we study its behaviour under taking group extensions. A conjecture of Nucinkis claims that every group G of finite F-cohomological dimension admits a finite-dimensional model for EFG. Note that it is unknown whether the class H1F is closed under taking extensions. It is also unknown whether the class of groups admitting a finite-dimensional classifying space for proper actions is closed under taking extensions. In Chapter 3 we introduce and study the notion of F-homological dimension and give an upper bound on the homological length of non-uniform lattices on locally finite CATp0q polyhedral complexes, giving an easier proof that generalises an important result for arithmetic groups over function fields, due to Bux and Wortman. The first Grigorchuk group G was introduced in 1980 and has been extensively studied since due to its extraordinary properties. The class HF of hierarchically decomposable groups was introduced by Kropholler in 1993. There are very few known examples of groups that lie outside HF. We answer the question regarding the HF-membership of G by showing that G lies outside HF. In the final chapter we introduce a new class of groups U, and show that the Kropholler-Mislin conjecture holds for a subclass of U and discuss its validity in general

A Schur ring is a subring of the group algebra with a basis that is formed by a partition of the group. These subrings were initially used to study finite permutation groups, and classifications of Schur rings over various finite groups have been studied. Here we investigate Schur rings over various infinite groups, including free groups. We classify Schur rings over the infinite cyclic group.

Approved for public release; distribution is unlimited
A pipeline technique by Loomis and Sinha has been applied to the design of recursive digital filters. Recursive digital filters operating at hitherto impossibly high rates can be designed by this technique. An alternate technique by R. Gnanasekaran allows high speed implementation using the state-space structure directly. High throughput is also achieved by use of pipelined multiply-add modules. The actual hardware complexity will depend upon the number of pipeline stages. These techniques are used for the design of the I IR notch filter and finally, a comparison of the performance and complexity of these two techniques is presented.
http://archive.org/details/infiniteimpulser00jang
Lieutenant, Royal Thai Navy

Résumé:

Cette dissertation s’intéresse aux méthodes numériques dans le domaine de l’acoustique. Les propriétés acoustiques d’un produit sont devenues une part intégrante de la conception. En effet, de nos jours le bruit est perçu comme une nuisance par le consommateur et constitue un critère de vente. Il y a de plus des normes à respecter. Les méthodes numériques permettent de prédire la propagation sonore et constitue dès lors un outil de conception incontournable pour réduire le temps et les coûts de développement d’un produit.

Cette dissertation considère la propagation d’ondes acoustiques dans le domaine fréquentiel en tenant compte de la présence d’un écoulement. Nous pouvons citer comme application industrielle, le rayonnement d’une nacelle de réacteur d’avion. Le but de la thèse est de proposer une nouvelle méthode et démontrer ses performances par rapport aux méthodes actuellement utilisées (i.e. la méthode des éléments finis).

L’originalité du travail consiste à étendre la méthode de partition de l’unité polynomiale dans le cadre de la propagation acoustique convectée, pour des domaines extérieurs. La simulation acoustique dans des domaines de dimensions infinies est réalisée dans ce travail à l’aide d’un couplage entre éléments finis et éléments infinis.

La dissertation présente la formulation de la méthode pour des applications axisymétriques et tridimensionnelles et vérifie la méthode en comparant les résultats numériques obtenus avec des solutions analytiques pour des applications académiques (i.e. propagation dans un conduit, rayonnement d’un multipole, bruit émis par la vibration d’un piston rigide, etc.). Les performances de la méthode sont ensuite analysées. Des courbes de convergences illustrent à une fréquence donnée, la précision de la méthode en fonction du nombre d’inconnues. Tandis que des courbes de performances présentent le temps de calcul nécessaire pour obtenir une solution d’une précision donnée en fonction de la fréquence d’excitation. Ces études de performances montrent l’intérêt de la méthode présentée.

Le rayonnement d’un réacteur d’avion a été abordé dans le but de vérifier la méthode sur une application de type industriel. Les résultats illustrent la propagation pour une nacelle axisymétrique en tenant compte de l’écoulement et la présence de matériau absorbant dans la nacelle et compare les résultats obtenus avec la méthode proposée et ceux obtenus avec la méthode des éléments finis.

Les performances de la méthode de la partition de l’unité dans le cadre de la propagation convectée en domaines infinis sont présentées pour des applications académiques et de type industriel. Le travail effectué illustre l’intérêt d’utiliser des fonctions polynomiales d’ordre élevé ainsi que les avantages à enrichir l’approximation localement afin d’améliorer la solution sans devoir créer un maillage plus fin.

Summary:

Environmental considerations are important in the design of many engineering systems and components. In particular, the environmental impact of noise is important over a very broad range of engineering applications and is increasingly perceived and regulated as an issue of occupational safety or health, or more simply as a public nuisance. The acoustic quality is then considered as a criterion in the product design process. Numerical prediction techniques allow to simulate vibro-acoustic responses. The use of such techniques reduces the development time and cost.

This dissertation focuses on acoustic convected radiation in outer domains such as it is the case for turbofan radiation. In the current thesis the mapped infinite partition of unity method is implemented within a coupled finite and infinite element model. This method allows to enrich the approximation with polynomial functions.

We present axisymmetric and three-dimensional formulations, verify and analyse the performance of the method. The verification compares computed results with the proposed method and analytical solutions for academic applications (i.e. duct propagation, multipole radiation, noise radiated by a vibrating rigid piston, etc.) .Performance analyses are performed with convergence curves plotting, for a given frequency, the accuracy of the computed solution with respect to the number of degrees of freedom or with performance curves, plotting the CPU time required to solve the application within a given accuracy, with respect to the excitation frequency. These performance analyses illustrate the interest of the mapped infinite partition of unity method.

We compute the radiation of an axisymmetric turbofan (convected radiation and acoustic treatments). The aim is to verify the method on an industrial application. We illustrate the radiation and compare the mapped infinite partition of unity results with finite element computations.

The dissertation presents the mapped partition of unity method as a computationally efficient method and illustrates its performances for academic as well as industrial applications. We suggest to use the method with high order polynomials and take the advantage of the method which allows to locally enrich the approximation. This last point improves the accuracy of the solution and prevent from creating a finer mesh.

Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

Thesis (Ph. D.) -- University of Maryland, College Park, 2004.
Thesis research directed by: Mathematics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

A major current challenge consists in extending formal methods in order to handle infinite-state systems. Infiniteness stems from the fact that the system operates on unbounded data structure such as stacks, queues, clocks, integers; as well as parameterization.

Systems with unbounded data structure are natural models for reasoning about communication protocols, concurrent programs, real-time systems, etc. While parameterized systems are more suitable if the system consists of an arbitrary number of identical processes which is the case for cache coherence protocols, distributed algorithms and so forth.

In this thesis, we consider model checking problems for certain fundamental classes of probabilistic infinite-state systems, as well as the verification of safety properties in parameterized systems. First, we consider probabilistic systems with unbounded data structures. In particular, we study probabilistic extensions of Lossy Channel Systems (PLCS), Vector addition Systems with States (PVASS) and Noisy Turing Machine (PNTM). We show how we can describe the semantics of such models by infinite-state Markov chains; and then define certain abstract properties, which allow model checking several qualitative and quantitative problems.

Then, we consider parameterized systems and provide a method which allows checking safety for several classes that differ in the topologies (linear or tree) and the semantics (atomic or non-atomic). The method is based on deriving an over-approximation which allows the use of a symbolic backward reachability scheme. For each class, the over-approximation we define guarantees monotonicity of the induced approximate transition system with respect to an appropriate order. This property is convenient in the sense that it preserves upward closedness when computing sets of predecessors.

Studying the zeros of a parameter dependent operator F defined on a Hilbert space H is a fundamental problem in mathematics. When the Hilbert space is finite dimensional, continuation provides, via predictor-corrector algorithms, efficient techniques to numerically follow the zeros of F as we move the parameter. In the case of infinite dimensional Hilbert spaces, this procedure must be applied to some finite dimensional approximation which of course raises the question of validity of the output. We introduce a new technique that combines the information obtained from the predictor-corrector steps with ideas from rigorous computations and verifies that the numerically produced zero for the finite dimensional system can be used to explicitly define a set which contains a unique zero for the infinite dimensional problem F: HxR->Im(F). We use this new validated continuation to study equilibrium solutions of partial differential equations, to prove the existence of chaos in ordinary differential equations and to follow branches of periodic solutions of delay differential equations. In the context of partial differential equations, we show that the cost of validated continuation is less than twice the cost of the standard continuation method alone.

We analyse different Gibbsian properties of interactive Brownian diffusions X indexed by the lattice $Z^{d} : X = (X_{i}(t), i ∈ Z^{d}, t ∈ [0, T], 0 < T < +∞)$. In a first part, these processes are characterized as Gibbs states on path spaces of the form $C([0, T],R)Z^{d}$. In a second part, we study the Gibbsian character on $R^{Z}^{d}$ of $v^{t}$, the law at time t of the infinite-dimensional diffusion X(t), when the initial law $v = v^{0}$ is Gibbsian.

The authors analyse different Gibbsian properties of interactive Brownian diffusions X indexed by the d-dimensional lattice. In the first part of the paper, these processes are characterized as Gibbs states on path spaces. In the second part of the paper, they study the Gibbsian character on R^{Z^d} of the law at time t of the infinite-dimensional diffusion X(t), when the initial law is Gibbsian.

AMS Classifications: 60G15
60G60
60H10
60J60

Infinite variance distributions are among the competing models used to explain the non-normality of stock price changes (Mandelbrot, 1963; Fama, 1965; Mandelbrot and Taylor, 1967; Rachev and Samorodnitsky, 1993). We investigate the asymptotic option price formula in infinite variance setting for both independent and correlated data using point processes. As we shall see the application of point process models can also lead us to investigate a more general option price formula. We also apply a recursion technique to quantify various characteristics of the resulting formulas. It shows that such formulas, and even their approximations, may be difficult to apply in practice. A nonparametric bootstrap method is proposed as one alternative approach and its asymptotic consistency is established under a resampling scheme of m = o(n). Some empirical evidence is provided showing the method works in principle, although large sample sizes appear to be needed for accuracy. This method is also illustrated using publicly available financial data.

Dan Kiley (American, 1912-2004) is one of the most highly regarded modernist landscape architects of the 20th century. As described in Kiley scholarship to-date, his decades-long practice exhibits a commitment to modernism inspired by classical landscape elements and modernist spatial techniques as a means of recreating the experience of a “walk in nature”. An unexamined aspect of Kiley scholarship is his consistent references to infinity in published writing and interviews, references which date as far back as the 1960s and continue into the 1990s, and therefore span much of his professional career. These references to infinity are often used to describe a personal appreciation of nature as well as an intentional approach to design. Through an analysis of these references, literature review of Kiley scholarship, interviews with selected Kiley colleagues, and archival research and site visits of five case studies (Miller Garden, North Christian Church, Fountain Place, Kiley Garden, and Donald J. Hall Sculpture Garden), this thesis examines the way in which Kiley referred to infinity and how he may have expressed infinity in his designed landscapes. This examination is contextualised within the histories of the ideas of infinity and artificial infinity in mathematics, theology, cosmology, art, and design. The history of the artificial infinite is synthesised into an updated taxonomy of expressions of the artificial infinite which is applied for an analysis of the case studies. The five case studies illustrate varying levels of richness and clarity, where expressions of the artificial infinite are spatially distributed and/or layered, connective and/or isolated (horizontally and/or vertically), and clearly expressed and/or interrupted. This analysis of the artificial infinite in the landscape architecture of Dan Kiley deepens our understanding of his design approach, connects Kiley to a longer and broader history of cultural ideas and expression, leads to a more nuanced understanding of modernist landscape architecture in the USA, broadens our understanding of the expression of infinity in landscape architecture, and demonstrates the applicability of an interpretive technique grounded in aesthetic analysis that could be applied to both art and design.