<p>This thesis consists of three papers, all of them on the topic of function spaces on fractals.</p><p>The papers summarised in this thesis are:</p><p>Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umeå University, 2005.</p><p>Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umeå University, 2005.</p><p>Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript.</p><p>The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams.</p><p>In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base.</p><p>The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.</p>

This thesis consists of three papers, all of them on the topic of function spaces on fractals. The papers summarised in this thesis are: Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umeå University, 2005. Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umeå University, 2005. Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript. The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams. In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base. The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.

Two standard invariants used to study the fundamental group of the complement X of a hyperplane arrangement are the Malcev completion of its fundamental group G and the cohomology groups of X with coefficients in rank one local systems. In this thesis, we develop a tool that unifies these two approaches. This tool is the Malcev completion S_p of G relative to a homomorphism p from G into (C^*)^N. The relative completion S_p is a prosolvable group that generalizes the classical Malcev completion; when p is the trivial representation, S_p is the Malcev completion of G. The group S_p is tightly controlled by the cohomology groups H^1(X,L_{p^k}) with coefficients in the irreducible local systems L_{p^k} associated to the representation p.The pronilpotent Lie algebra u_p of the prounipotent radical U_p of S_p has been described by Hain. If p is the trivial representation, then u_p is the holonomy Lie algebra, which is well-known to be quadratically presented. In contrast, we show that when X is the complement of the braid arrangement in complex two-space, there are infinitely many representations p from G into (C^*)^2 for which u_p is not quadratically presented.We show that if Y is a subtorus of the character torus T containing the trivial character, then S_p is combinatorially determined for general p in Y. We do not know whether S_p is always combinatorially determined. If S_p is combinatorially determined for all characters p of G, then the characteristic varieties of the arrangement X are combinatorially determined.When Y is an irreducible subvariety of T^N, we examine the behavior of S_p as p varies in Y. We define an affine group scheme S_Y over Y such that if Y = {p}, then S_Y is the relative Malcev completion S_p. For each p in Y, there is a canonical homomorphism of affine group schemes from S_p into the affine group scheme which is the restriction of S_Y to p. This is often an isomorphism. For example, if there exists p in Y whose image is Zariski dense in G_m^N, then this homomorphism is an isomorphism for general p in Y. / Dissertation

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.

The use of fractal-based methods in imaging was first popularized with fractal image compression in the early 1990s. In this application, one seeks to approximate a given target image by the fixed point of a contractive operator called the fractal transform. Typically, one uses Local Iterated Function Systems with Grey-Level Maps (LIFSM), where the involved functions map a parent (domain) block in an image to a smaller child (range) block and the grey-level maps adjust the shading of the shrunken block. The fractal transform is defined by the collection of optimal parent-child pairings and parameters defining the grey-level maps. Iteration of the fractal transform on any initial image produces an approximation of the fixed point and, hence, an approximation of the target image. Since the parameters defining the LIFSM take less space to store than the target image does, image compression is achieved.This thesis extends the theoretical and practical frameworks of fractal imaging to one involving a particular type of multifunction that captures the idea that there are typically many near-optimal parent-child pairings. Using this extended machinery, we treat three application areas. After discussing established edge detection methods, we present a fractal-based approach to edge detection with results that compare favourably to the Sobel edge detector. Next, we discuss two methods of information hiding: first, we explore compositions of fractal transforms and cycles of images and apply these concepts to image-hiding; second, we propose and demonstrate an algorithm that allows us to securely embed with redundancy a binary string within an image. Finally, we discuss some theory of certain random fractal transforms with potential applications to texturing. / The Natural Sciences and Engineering Research Council and the University of Guelph helped to provide financial support for this research.

The Learning Classifier System (LCS) and its descendant, XCS, are promising paradigms for machine learning design and implementation. Whereas LCS allows classifier payoff predictions to guide system performance, XCS focuses on payoff-prediction accuracy instead, allowing it to evolve "optimal" classifier sets in particular applications requiring rational thought. This research examines LCS and XCS performance in artificial situations with broad social/commercial parallels, created using the non-Markov Iterated Prisoner's Dilemma (IPD) game-playing scenario, where the setting is sometimes asymmetric and where irrationality sometimes pays. This research systematically perturbs a "conventional" IPD-playing LCS-based agent until it results in a full-fledged XCS-based agent, contrasting the simulated behavior of each LCS variant in terms of a number of performance measures. The intent is to examine the XCS paradigm to understand how it better copes with a given situation (if it does) than the LCS perturbations studied.Experiment results indicate that the majority of the architectural differences do have a significant effect on the agents' performance with respect to the performance measures used in this research. The results of these competitions indicate that while each architectural difference significantly affected its agent's performance, no single architectural difference could be credited as causing XCS's demonstrated superiority in evolving optimal populations. Instead, the data suggests that XCS's ability to evolve optimal populations in the multiplexer and IPD problem domains result from the combined and synergistic effects of multiple architectural differences.In addition, it is demonstrated that XCS is able to reliably evolve the Optimal Population [O] against the TFT opponent. This result supports Kovacs' Optimality Hypothesis in the IPD environment and is significant because it is the first demonstrated occurrence of this ability in an environment other than the multiplexer and Woods problem domains.It is therefore apparent that while XCS performs better than its LCS-based counterparts, its demonstrated superiority may not be attributed to a single architectural characteristic. Instead, XCS's ability to evolve optimal classifier populations in the multiplexer problem domain and in the IPD problem domain studied in this research results from the combined and synergistic effects of multiple architectural differences.

Non-representational cognitive science is a promising research field that provides an alternative to the view of the brain as a “computer” filled with symbolic representations of the world and cognition as “calculations” performed on those symbols. Autopoiesis is a biological, bottom-up, non-representational theory of cognition, in which representations and meaning are framed as explanatory concepts that are constituted in an observer’s description of a cognitive system, not operational concepts in the system itself. One of the problems of autopoiesis, and all non-representational theories, is that they struggle with scaling up to high-level cognitive behaviour such as language. The Iterated Learning Model is a theory of language evolution that shows that certain features of language are explained not because of something happening in the linguistic agent’s brain, but as the product of the evolution of the linguistic system itself under the pressures of learnability and expressivity. Our goal in this work is to combine an autopoietic approach with the cultural transmission chains that the ILM uses, in order to provide the first step in an autopoietic explanation of the evolution of language. In order to do that, we introduce a simple, joint action physical task in which agents are rewarded for dancing around each other in either of two directions, left or right. The agents are simulated e-pucks, with continuous-time recurrent neural networks as nervous systems. First, we adapt a biologically plausible reinforcement learning algorithm based on spike-timing dependent plasticity tagging and dopamine reward signals. We show that, using this algorithm, our agents can successfully learn the left/right dancing task and examine how learning time influences the agents’ task success rates. Following that, we link individual learning episodes in cultural transmission chains and show that an expert agent’s initial behaviour is successfully transmitted in long chains. We investigate the conditions under which these transmission chains break down, as well as the emergence of behaviour in the absence of expert agents. By using long transmission chains, we look at the boundary conditions for the re-establishment of transmitted behaviour after chain breakdowns. Bringing all the above experiments together, we discuss their significance for non-representational cognitive science and draw some interesting parallels to existing Iterated Learning research; finally, we close by putting forward a number of ideas for additions and future research directions.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

Dans cette thèse nous proposons de nouveaux algorithmes d'analyse vidéo. La première contribution de cette thèse concerne le domaine de la segmentation de vidéos avec pour objectif d'obtenir une segmentation dense et spatio-temporellement cohérente. Nous proposons de combiner les aspects spatiaux et temporels d'une vidéo en une seule notion, celle de Fibre. Une fibre est un ensemble de trajectoires qui sont spatialement connectées par un maillage. Les fibres sont construites en évaluant simultanément les aspects spatiaux et temporels. Par rapport a l’état de l'art une segmentation de vidéo a base de fibres présente comme avantages d’accéder naturellement au voisinage grâce au maillage et aux correspondances temporelles pour la plupart des pixels de la vidéo. De plus, cette segmentation à base de fibres a une complexité quasi linéaire par rapport au nombre de pixels. La deuxième contribution de cette thèse concerne le suivi d'objets multiples. Nous proposons une approche de suivi qui utilise des caractéristiques des points suivis, la cinématique des objets suivis et l'apparence globale des détections. L'unification de toutes ces caractéristiques est effectuée avec un champ conditionnel aléatoire. Ensuite ce modèle est optimisé en combinant les techniques de passage de message et une variante de processus ICM (Iterated Conditional Modes) pour inférer les trajectoires d'objet. Une troisième contribution mineure consiste dans le développement d'un descripteur pour la mise en correspondance d'apparences de personne. Toutes les approches proposées obtiennent des résultats compétitifs ou meilleurs (qualitativement et quantitativement) que l’état de l'art sur des base de données. / In this thesis we propose novel algorithms for video analysis. The first contribution of this thesis is in the domain of video segmentation wherein the objective is to obtain a dense and coherent spatio-temporal segmentation. We propose joining both spatial and temporal aspects of a video into a single notion Fiber. A fiber is a set of trajectories which are spatially connected by a mesh. Fibers are built by jointly assessing spatial and temporal aspects of the video. Compared to the state-of-the-art, a fiber based video segmentation presents advantages such as a natural spatio-temporal neighborhood accessor by a mesh, and temporal correspondences for most pixels in the video. Furthermore, this fiber-based segmentation is of quasi-linear complexity w.r.t. the number of pixels. The second contribution is in the realm of multiple object tracking. We proposed a tracking approach which utilizes cues from point tracks, kinematics of moving objects and global appearance of detections. Unification of all these cues is performed on a Conditional Random Field. Subsequently this model is optimized by a combination of message passing and an Iterated Conditional Modes (ICM) variant to infer object-trajectories. A third, minor, contribution relates to the development of suitable feature descriptor for appearance matching of persons. All of our proposed approaches achieve competitive and better results (both qualitatively and quantitatively) than state-of-the-art on open source datasets.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.