Descriptive set theory and the ergodic theory of countable groups

The primary focus of this thesis is on the interplay of descriptive set theory and the ergodic theory of group actions. This incorporates the study of turbulence and Borel reducibility on the one hand, and the theory of orbit equivalence and weak equivalence on the other. Chapter 2 is joint work with Clinton Conley and Alexander Kechris; we study measurable graph combinatorial invariants of group actions and employ the ultraproduct construction as a way of constructing various measure preserving actions with desirable properties. Chapter 3 is joint work with Lewis Bowen; we study the property MD of residually finite groups, and we prove a conjecture of Kechris by showing that under general hypotheses property MD is inherited by a group from one of its co-amenable subgroups. Chapter 4 is a study of weak equivalence. One of the main results answers a question of Abért and Elek by showing that within any free weak equivalence class the isomorphism relation does not admit classification by countable structures. The proof relies on affirming a conjecture of Ioana by showing that the product of a free action with a Bernoulli shift is weakly equivalent to the original action. Chapter 5 studies the relationship between mixing and freeness properties of measure preserving actions. Chapter 6 studies how approximation properties of ergodic actions and unitary representations are reflected group theoretically and also operator algebraically via a group's reduced C^*-algebra. Chapter 7 is an appendix which includes various results on mixing via filters and on Gaussian actions.

Compact universal logic gates realized using quantization of current in nanodevices

This paper proposes novel universal logic gates using the current quantization characteristics of nanodevices. In nanodevices like the electron waveguide (EW) and single-electron (SE) turnstile, the channel current is a staircase quantized function of its control voltage. We use this unique characteristic to compactly realize Boolean functions. First we present the concept of the periodic-threshold threshold logic gate (PTTG), and we build a compact PTTG using EW and SE turnstiles. We show that an arbitrary three-input Boolean function can be realized with a single PTTG, and an arbitrary four-input Boolean function can be realized by using two PTTGs. We then use one PTTG to build a universal programmable two-input logic gate which can be used to realize all two-input Boolean functions. We also build a programmable three-input logic gate by using one PTTG. Compared with linear threshold logic gates, with the PTTG one can build digital circuits more compactly. The proposed PTTGs are promising for future smart nanoscale digital system use.

On equations for regular languages, finite automata, and sequential networks

We consider systems of equations of the form where A is the underlying alphabet, the Xi are variables, the Pi,a are boolean functions in the variables Xi, and each δi is either the empty word or the empty set. The symbols υ and denote concatenation and union of languages over A. We show that any such system has a unique solution which, moreover, is regular. These equations correspond to a type of automation, called boolean automation, which is a generalization of a nondeterministic automation. The equations are then used to determine the language accepted by a sequential network; they are obtainable directly from the network.

寻找布尔函数的零化子

通过解方程组来研究密码系统,是代数攻击的研究内容代.对方程组降次是降低求解复杂度的一种重要方法.为了达到这个目的,引入了布尔函数零化子的概念.然而迄今为止,尚未有求解零化子的有效算法.这篇文章提出了一种计算给定布尔函数的零化子集的算法.由前两个算法,可以得到给定布尔函数的零化子集的一组基;从第三个算法,可以得到最低次数的零化子.算法的复杂度与函数的单项式个数相关.对流密码来说,在很多情况下,相比以前的算法而言,这种算法的复杂度大为降低.最后,我们将给出一个实例,说明算法是如何工作的.

Methods to accelerate the learning of bayesian network structures

R. Daly and Q. Shen. Methods to accelerate the learning of bayesian network structures. Proceedings of the Proceedings of the 2007 UK Workshop on Computational Intelligence.

On Finding Sensitivity of Quantum and Classical Gates

We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results.

Consistent couplings between fields with a gauge freedom and deformations of the master equation

The antibracket in the antifield-BRST formalism is known to define a map Hp × Hq → Hp + q + 1 associating with two equivalence classes of BRST invariant observables of respective ghost number p and q an equivalence class of BRST invariant observables of ghost number p + q + 1. It is shown that this map is trivial in the space of all functionals, i.e. that its image contains only the zeroth class. However, it is generically non-trivial in the space of local functionals. Implications of this result for the problem of consistent interactions among fields with a gauge freedom are then drawn. It is shown that the obstructions to constructing non-trivial such interactions lie precisely in the image of the antibracket map and are accordingly non-existent if one does not insist on locality. However consistent local interactions are severely constrained. The example of the Chern-Simons theory is considered. It is proved that the only consistent, local, Lorentz covariant interactions for the abelian models are exhausted by the non-abelian Chern-Simons extensions. © 1993.

Classification analytique de systèmes différentiels linéaires déployant une singularité irrégulière de rang de Poincaré 1

Cette thèse traite de la classification analytique du déploiement de systèmes différentiels linéaires ayant une singularité irrégulière. Elle est composée de deux articles sur le sujet: le premier présente des résultats obtenus lors de l'étude de la confluence de l'équation hypergéométrique et peut être considéré comme un cas particulier du second; le deuxième contient les théorèmes et résultats principaux. Dans les deux articles, nous considérons la confluence de deux points singuliers réguliers en un point singulier irrégulier et nous étudions les conséquences de la divergence des solutions au point singulier irrégulier sur le comportement des solutions du système déployé. Pour ce faire, nous recouvrons un voisinage de l'origine (de manière ramifiée) dans l'espace du paramètre de déploiement $\epsilon$. La monodromie d'une base de solutions bien choisie est directement reliée aux matrices de Stokes déployées. Ces dernières donnent une interprétation géométrique aux matrices de Stokes, incluant le lien (existant au moins pour les cas génériques) entre la divergence des solutions à $\epsilon=0$ et la présence de solutions logarithmiques autour des points singuliers réguliers lors de la résonance. La monodromie d'intégrales premières de systèmes de Riccati correspondants est aussi interprétée en fonction des éléments des matrices de Stokes déployées. De plus, dans le second article, nous donnons le système complet d'invariants analytiques pour le déploiement de systèmes différentiels linéaires $x^2y'=A(x)y$ ayant une singularité irrégulière de rang de Poincaré $1$ à l'origine au-dessus d'un voisinage fixé $\mathbb{D}_r$ dans la variable $x$. Ce système est constitué d'une partie formelle, donnée par des polynômes, et d'une partie analytique, donnée par une classe d'équivalence de matrices de Stokes déployées. Pour chaque valeur du paramètre $\epsilon$ dans un secteur pointé à l'origine d'ouverture plus grande que $2\pi$, nous recouvrons l'espace de la variable, $\mathbb{D}_r$, avec deux secteurs et, au-dessus de chacun, nous choisissons une base de solutions du système déployé. Cette base sert à définir les matrices de Stokes déployées. Finalement, nous prouvons un théorème de réalisation des invariants qui satisfont une condition nécessaire et suffisante, identifiant ainsi l'ensemble des modules.

Amplification de l'amplitude : analyse et applications

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement.

Multilevel Training of Binary Morphological Operators

The design of binary morphological operators that are translation-invariant and locally defined by a finite neighborhood window corresponds to the problem of designing Boolean functions. As in any supervised classification problem, morphological operators designed from a training sample also suffer from overfitting. Large neighborhood tends to lead to performance degradation of the designed operator. This work proposes a multilevel design approach to deal with the issue of designing large neighborhood-based operators. The main idea is inspired by stacked generalization (a multilevel classifier design approach) and consists of, at each training level, combining the outcomes of the previous level operators. The final operator is a multilevel operator that ultimately depends on a larger neighborhood than of the individual operators that have been combined. Experimental results show that two-level operators obtained by combining operators designed on subwindows of a large window consistently outperform the single-level operators designed on the full window. They also show that iterating two-level operators is an effective multilevel approach to obtain better results.

Arquitetura multiprocessada e reconfigurável para a síntese de redes de Petri em hardware

Uma arquitetura reconfigurável e multiprocessada para a implementação física de Redes de Petri foi desenvolvida em VHDL e mapeada sobre um FPGA. Convencionalmente, as Redes de Petri são transformadas em uma linguagem de descrição de hardware no nível de transferências entre registradores e um processo de síntese de alto nível é utilizado para gerar as funções booleanas e tabelas de transição de estado para que se possa, finalmente, mapeá-las num FPGA (Morris et al., 2000) (Soto and Pereira, 2001). A arquitetura proposta possui blocos lógicos reconfiguráveis desenvolvidos exclusivamente para a implementação dos lugares e das transições da rede, não sendo necessária a descrição da rede em níveis de abstração intermediários e nem a utilização de um processo de síntese para realizar o mapeamento da rede na arquitetura. A arquitetura permite o mapeamento de modelos de Redes de Petri com diferenciação entre as marcas e associação de tempo no disparo das transições, sendo composta por um arranjo de processadores reconfiguráveis, cada um dos quais representando o comportamento de uma transição da Rede de Petri a ser mapeada e por um sistema de comunicação, implementado por um conjunto de roteadores que são capazes de enviar pacotes de dados de um processador reconfigurável a outro. A arquitetura proposta foi validada num FPGA de 10.570 elementos lógicos com uma topologia que permitiu a implementação de Redes de Petri de até 9 transições e 36 lugares, atingindo uma latência de 15,4ns e uma vazão de até 17,12GB/s com uma freqüência de operação de 64,58MHz.

Branch and bound algorithm for transmission network expansion planning using DC model

This paper presents an algorithm to solve the network transmission system expansion planning problem using the DC model which is a mixed non-linear integer programming problem. The major feature of this work is the use of a Branch-and-Bound (B&B) algorithm to directly solve mixed non-linear integer problems. An efficient interior point method is used to solve the non-linear programming problem at each node of the B&B tree. Tests with several known systems are presented to illustrate the performance of the proposed method. ©2007 IEEE.

Equivalência de estímulos com procedimentos combinados e consciência fonológica na aquisição da leitura generalizada

A formação de classes de equivalência entre figuras, palavras ditadas e palavras impressas promove a leitura com compreensão, mas não estabelece o controle discriminativo por todos as unidades da palavra (letras e sílabas). A aplicação de procedimentos especiais combinados (cópia, ditado e oralização fluente e escandida) durante o ensino das relações condicionais entre palavras ditadas e palavras impressas (AC) favorece o estabelecimento de controle discriminativo por unidades menores que a palavra, e a leitura textual e com compreensão das palavras formadas por recombinações daquelas unidades. O treino explícito de discriminações silábicas tem sido adotado como um dos procedimentos nos estudos sobre consciência fonológica, com resultados satisfatórios em testes de leitura. O presente estudo teve como objetivo investigar o efeito dos dois procedimentos sobre a aquisição da leitura recombinativa em pré-escolares. Três crianças foram expostas ao procedimento de equivalência e procedimento especiais combinados durante o ensino das relações AC (com as palavras MALA, PATO e BOCA), e quatro ao treino explícito de discriminações silábicas em tarefas de rima, aliteração, adição e subtração de sílabas e correspondência grafosilábica. Após um Pré-teste, os participantes do primeiro grupo foram submetidos ao teste / ensino das relações AB (palavras ditadas-figuras), e em seguida ao ensino das relações AC com procedimentos combinados e aos testes BC (figuras-palavras impressas) e CB. Posteriormente à emergência das relações de equivalência (BC/CB), as crianças participavam de testes de leitura textual das sílabas, das palavras de ensino e de generalização (formadas pela recombinação das sílabas das palavras de ensino). Quando os participantes atingiam o mínimo de 90% de acertos no teste de leitura generalizada eram conduzidos ao Pós-teste. Caso contrário, participavam antes da mesma seqüência anterior, porém, com três palavras de generalização (BOLA, LAMA e CAPA). Já as quatro crianças do segundo grupo inicialmente foram submetidas a tarefas de reconhecimento silábico e posteriormente a tarefas de correspondência grafosilábica, rima, aliteração, subtração e adição silábica com as sílabas MA, LA, PA, TO, BO e CA. O participante só era exposto ao treino de uma outra sílaba se obtivesse 100% de acertos na tarefa de correspondência grafosilábica e acertasse todos os itens experimentais das demais atividades. Ao final do programa os participantes eram expostos ao Pós-teste: os três participantes do grupo de equivalência de estímulos e um do grupo de consciência fonológica apresentaram a leitura recombinativa de algumas palavras, mas nenhum deles apresentou leitura recombinativa generalizada. Sugere-se que outras variáveis podem interferir no desempenho dos participantes, como: a história pré e extraexperimental, a aquisição do conceito de impressos (e.g. leitura da esquerda para a direita) e a quantidade de tentativas de ensino. Supõe-se ainda que no caso do ensino de leitura do português o uso conjunto de procedimentos de equivalência de estímulos e de discriminação/correspondência silábica seja um método eficiente no ensino da leitura recombinativa. Propõe-se que novos estudos avaliem os efeitos da combinação destes procedimentos no ensino de tal repertório.

Procedimentos de treino e teste de relações entre estímulos em Cebus apella

A aprendizagem complexa abrange o controle por relações abstratas após a exposição a relações diretamente treinadas. Neste trabalho, uma seqüência de experimentos investigou a aprendizagem de relações entre estímulos em dois macacos prego (Cebus apella) envolvendo o treino direto de relações de identidade, testes sucessivos de identidade generalizada, o treino direto de relações arbitrárias e teste de relações simétricas como indicação da formação de classes de equivalência. Três bases teóricas foram seguidas: 1) A formação de classes de equivalência é uma função básica de estímulo 2) A teoria da coerência de topografia de controle de estímulos, e 3) Uma versão do sistema personalizado de instrução como uma alternativa para estabelecer repertórios relacionais em organismos não-verbais. Os sujeitos apresentaram altos níveis de desempenho em discriminações condicionais de identidade e arbitrárias. Os sujeitos expostos a testes de identidade generalizada demonstraram essa relação abstrata; o sujeito exposto ao treino arbitrário apresentou resultados negativos no teste de desempenhos simétricos. A maioria dos problemas de aprendizagem de relações entre estímulos encontrados aqui com não-humanos parece similar aos problemas apresentados por indivíduos com desenvolvimento retardado. Os procedimentos de ensino para indivíduos com retardo foram suficientes para solucionar grande parte das deficiências de repertório de não-humanos, as quais geralmente são atribuídas a limitações da espécie.