No description available.

No description available.

Let F be a free group of finite rank. Given words u, v ∈ F, J.H.C. Whitehead solved the decision problem of finding an automorphism φ ∈ Aut(F), carrying u to v. He used topological methods to produce an algorithm. Higgins and Lyndon gave a very concise proof of the problem based on the works of Rapaport. We provide a detailed account of Higgins and Lyndon’s proof of the peak reduction lemma and the restricted version of Whitehead’s theorem, for cyclic words as well as for sets of cyclic words, with a full explanation of each step. Then, we give an inductive proof of Whitehead’s minimization theorem and describe Whitehead’s decision algorithm. Noticing that Higgins and Lyndon’s work is limited to the cyclic words, we extend their proofs to ordinary words and sets of ordinary words. In the last chapter, we mention an example given by Whitehead to show that the decision problem for finitely generated subgroups is more difficult and outline an approach due to Gersten to overcome this difficulty. We also give an extensive literature survey of Whitehead’s algorithm / Thesis / Master of Science (MSc)

Finite-state automata are a central computational model in computer science, with numerous and diverse applications. In one such application, viz. model-checking, automata over infinite words play a central rˆole. In this thesis, we concentrate on B¨uchi automata (BA), which are arguably the simplest finite-state model recognizing languages of infinite words. Two algorithmic problems are paramount in the theory of automata: language inclusion and automata minimization. They are both PSPACE-complete, thus under standard complexity-theoretic assumptions no deterministic algorithm with worst case polynomial time can be expected. In this thesis, we develop techniques to tackle these problems. In automata minimization, one seeks the smallest automaton recognizing a given language (“small” means with few states). Despite PSPACE-hardness of minimization, the size of an automaton can often be reduced substantially by means of quotienting. In quotienting, states deemed equivalent according to a given equivalence are merged together; if this merging operation preserves the language, then the equivalence is said to be Good for Quotienting (GFQ). In general, quotienting cannot achieve exact minimization, but, in practice, it can still offer a very good reduction in size. The central topic of this thesis is the design of GFQ equivalences for B¨uchi automata. A particularly successful approach to the design of GFQ equivalences is based on simulation relations. Simulation relations are a powerful tool to compare the local behavior of automata. The main contribution of this thesis is to generalize simulations, by relaxing locality in three perpendicular ways: by fixing the input word in advance (fixed-word simulations, Ch. 3), by allowing jumps (jumping simulations, Ch. 4), and by using multiple pebbles (multipebble simulations for alternating BA, Ch. 5). In each case, we show that our generalized simulations induce GFQ equivalences. For fixed-word simulation, we argue that it is the coarsest GFQ simulation implying language inclusion, by showing that it subsumes a natural hierarchy of GFQ multipebble simulations. From a theoretical perspective, our study significantly extends the theory of simulations for BA; relaxing locality is a general principle, and it may find useful applications outside automata theory. From a practical perspective, we obtain GFQ equivalences coarser than previously possible. This yields smaller quotient automata, which is beneficial in applications. Finally, we show how simulation relations have recently been applied to significantly optimize exact (exponential) language inclusion algorithms (Ch. 6), thus extending their practical applicability.

Given a set P of n points in R^d, we consider the k-connected interference minimization problem, in which the objective is to assign a transmission radius to each node in P such that the resulting network is k-connected and the maximum interference is minimized. We show for any n and any 1 <= k < n, Omega(sqrt(kn)) and Omega(k log n) are lower bounds on the worst-case minimum maximum interference in the symmetric and asymmetric models, respectively. In the symmetric case, we present polynomial-time algorithms that build a k-connected network on any given set of n nodes with interference O(sqrt(kn)) in one dimension and O(min{k sqrt(n), k log lambda}) in two dimensions, where lambda denotes the ratio of the longest to shortest distances between any pair of nodes. In the asymmetric case, we present a polynomial-time algorithm that builds a strongly k-connected network with maximum interference O(k log lambda) in two dimensions. / October 2016

This thesis is concerned with extending properties of regular word languages to richer structures. We consider intricate properties like the relationship between one-way and two-way temporal logics, minimization of automata, and the ability to effectively characterize logics. We investigate whether these properties can be extended to tree languages or word languages over an infinite alphabet. It is known that linear temporal logic (LTL) is as expressive as first-order logic over finite words [Kam68, GPSS80]. LTL is a unidirectional logic, that can only navigate forwards in a word, hence it is quite surprising that it can capture all of first-order logic. In fact, one of the main ideas of the proof of [GPSS80] is to show that the expressiveness of LTL is not increased if modalities for navigating backwards are added. It is also known that an extension of bidirectional LTL to ordered trees, called Conditional XPath, is first-order complete [Mar04]. We investigate whether the unidirectional fragment of Conditional XPath is also first-order complete. We show that this is not the case. In fact we show that there is a strict hierarchy of expressiveness consisting of languages that are all weaker than first-order logic. Unidirectional Conditional XPath is contained in the lowest level of this hierarchy. In the second part of the thesis we consider data word languages. That is, word languages over an infinite alphabet. We extend the theorem of Myhill and Nerode to a class of automata for data word languages, called deterministic finite memory automata (DMA). We give a characterization of the languages that are accepted by DMA, and also provide an algorithm for minimizing DMA. Finally we extend theorems of Büchi, Schützenberger, McNaughton, and Papert to data word languages. A theorem of Büchi states that a language is regular iff it can be defined in monadic second-order logic. Schützenberger, McNaughton, and Papert have provided an effective characterization of first-order logic, that is, an algorithm for deciding whether a regular language can be defined in first-order logic. We provide a counterpart of Büchi's theorem for data languages. More precisely we define a new logic and we show that it has the same expressiveness as non-deterministic finite memory automata. We then turn to a smaller class of data languages, those that are recognized by algebraic objects called orbit finite data monoids. We define a second new logic and show that it can define precisely the languages accepted by orbit finite data monoids. We provide an effective characterization of a first-order variant of this second logic, as well as of restrictions of first-order logic, such as its two variable fragment and local variants.

O estudo dos centros geradores de padrão, CPGs, ´e um excelente exemplo das limitações do método reducionista, na tentativa de explicar um comportamento de ordem mais global. Não queremos, com isso, relegar a descrição esmiuçada dos mecanismos biofísicos e moleculares ao ostracismo. Muito pelo contrário, iremos nos apropriar de um subconjunto desses conceitos, na forma do modelo de Hodgkin & Huxley, para construir um sistema de simulação computacional de redes neurais, em pequena escala, passível de realizar duas métricas. Uma destinada a medir a complexidade da geração de informação circulante interna a rede, enquanto a outra traz dados relativos ao consumo energético das células neurais. Espera-se, com isso, alguma resposta para a seguinte questão: existe algum mecanismo, algum princípio básico em redes que oscilam, capaz de mapear um mínimo de uma grandeza física externa em algum outro mínimo interno a rede? Ao que tudo indica a resposta é afirmativa. Apresentaremos um tal ponto de minimização, juntamente com um formalismo, ainda em desenvolvimento, que justifica os resultados / The study of central pattern generators is a great example of the limitations in a reductionist approach, to achieve global knowledge about a system. We are not neglecting the importance of biophysical and molecular mechanisms. Quite the contrary, we will apply some of this concepts by means of Hodgkin & Huxley formalism, to build up a small form factor neural network software simulator. This platform will be able to perform two measurements, informational complexity and metabolic consumption with the aim of answer the question: is there some mechanism, some basic principle in oscillatory networks, capable of mapping a minimum in an external physical quantity into another minimum internal to the network? It seems that the answer is affirmative. We will present this minimization point, together with an under development formalism, to embase the results

A reconfiguração de sistemas de distribuição de energia elétrica consiste em alterar a topologia das redes através da abertura ou fechamento das chaves de interconexão existentes nos alimentadores de distribuição primários, de forma a otimizar uma determinada função objetivo. Normalmente os objetivos são a minimização de perdas ativas, o isolamento de faltas, o balanceamento de cargas entre alimentadores e/ou a melhoria dos níveis de tensão. Neste trabalho considera-se a minimização da perda ativa total. As dificuldades do problema de reconfiguração de redes de distribuição resultam do tamanho dos sistemas reais, aos quais correspondem um número elevado de variáveis binárias que representam as chaves, e também da relação quadrática existente entre a perda elétrica e a corrente que flui nos elementos da rede. Este trabalho desenvolve algumas novas formulações para o problema de reconfiguração de redes de distribuição, utilizando Programação Não Linear Inteira Mista. Além disso, demonstra-se que a parte contínua de todas as formulações é convexa, o que garante a unicidade da solução ótima para um dado estado das chaves na rede. Esta propriedade permitiu a utilização do Método de Newton na resolução do problema contínuo, com as seguintes vantagens: impossibilidade de o método identificar mínimos locais em vez do mínimo global procurado, e convergência em apenas uma iteração, proporcionada pela natureza quadrática das formulações. As formulações desenvolvidas foram implementadas na forma de programas computacionais. O desempenho das formulações é descrito e analisado através de diversos casos de estudo. / The reconfiguration of electricity distribution systems is concerned with finding the state of switching and protective devices so as to optimize a given objective function, which is usually defined as minimization of total loss, fault isolation, load balancing among feeders, or improvement of voltage profile. In this work, the objective function is defined as the minimization of total active loss. The main difficulties associated with this problem arise from the high number of binary variables that represent the switching and protective devices, as well as the quadratic relationship between electric loss and currents flowing through the network branches. This work develops some new formulations for the distribution system reconfiguration problem, which are then solved through mixed-integer nonlinear programming. In addition, it is shown that the continuous part in all formulations is convex, which guarantees the uniqueness of the optimal solution for a given switch profile. This property allows using the Standard Newton Method for solving the continuous part of the problem, with the following advantages: impossibility of the Newton Method identifying a local minimum instead of the desired global minimum, and convergence in just one iteration owing to the quadratic nature of all formulations. The proposed formulations were implemented as computational programs and their performance was evaluated through various study cases.

Model building is a fundamental scientific tool. Increasingly there is interest in building neurally-implemented models of cognitive processes with the intention of modelling brains. However, simulation of such models can be prohibitively expensive in both the time and energy required. For example, Spaun - "the world's first functional brain model", comprising 2.5 million neurons - required 2.5 hours of computation for every second of simulation on a large compute cluster. SpiNNaker is a massively parallel, low power architecture specifically designed for the simulation of large neural models in biological real time. Ideally, SpiNNaker could be used to facilitate rapid simulation of models such as Spaun. However the Neural Engineering Framework (NEF), with which Spaun is built, maps poorly to the architecture - to the extent that models such as Spaun would consume vast portions of SpiNNaker machines and still not run as fast as biology. This thesis investigates whether real time simulation of Spaun on SpiNNaker is at all possible. Three techniques which facilitate such a simulation are presented. The first reduces the memory, compute and network loads consumed by the NEF. Consequently, it is demonstrated that only a twentieth of the cores are required to simulate a core component of the Spaun network than would otherwise have been needed. The second technique uses a small number of additional cores to significantly reduce the network traffic required to simulated this core component. As a result simulation in real time is shown to be feasible. The final technique is a novel logic minimisation algorithm which reduces the size of the routing tables which are used to direct information around the SpiNNaker machine. This last technique is necessary to allow the routing of models of the scale and complexity of Spaun. Together these provide the ability to simulate the Spaun model in biological real time - representing a speed-up of 9000 times over previously reported results - with room for much larger models on full-scale SpiNNaker machines.

We study optimization algorithms for the finite sum problems frequently arising in machine learning applications. First, we propose novel variants of stochastic gradient descent with a variance reduction property that enables linear convergence for strongly convex objectives. Second, we study distributed setting, in which the data describing the optimization problem does not fit into a single computing node. In this case, traditional methods are inefficient, as the communication costs inherent in distributed optimization become the bottleneck. We propose a communication-efficient framework which iteratively forms local subproblems that can be solved with arbitrary local optimization algorithms. Finally, we introduce the concept of Federated Optimization/Learning, where we try to solve the machine learning problems without having data stored in any centralized manner. The main motivation comes from industry when handling user-generated data. The current prevalent practice is that companies collect vast amounts of user data and store them in datacenters. An alternative we propose is not to collect the data in first place, and instead occasionally use the computational power of users' devices to solve the very same optimization problems, while alleviating privacy concerns at the same time. In such setting, minimization of communication rounds is the primary goal, and we demonstrate that solving the optimization problems in such circumstances is conceptually tractable.