Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

No description available.

One of the main applications of machine learning in bioinformatics is the construction of classification models which can accurately classify new instances using information gained from previous instances. With the help of machine learning algorithms (such as supervised classification and gene selection) new meaningful knowledge can be extracted from bioinformatics datasets that can help in disease diagnosis and prognosis as well as in prescribing the right treatment for a disease. One particular challenge encountered when analyzing bioinformatics datasets is data noise, which refers to incorrect or missing values in datasets. Noise can be introduced as a result of experimental errors (e.g. faulty microarray chips, insufficient resolution, image corruption, and incorrect laboratory procedures), as well as other errors (errors during data processing, transfer, and/or mining). A special type of data noise called class noise, which occurs when an instance/example is mislabeled. Previous research showed that class noise has a detrimental impact on machine learning algorithms (e.g. worsened classification performance and unstable feature selection). In addition to data noise, gene expression datasets can suffer from the problems of high dimensionality (a very large feature space) and class imbalance (unequal distribution of instances between classes). As a result of these inherent problems, constructing accurate classification models becomes more challenging. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2015. / FAU Electronic Theses and Dissertations Collection

In response to the massive amounts of data that make up a large number of bioinformatics datasets, it has become increasingly necessary for researchers to use computers to aid them in their endeavors. With difficulties such as high dimensionality, class imbalance, noisy data, and difficult to learn class boundaries, being present within the data, bioinformatics datasets are a challenge to work with. One potential source of assistance is the domain of data mining and machine learning, a field which focuses on working with these large amounts of data and develops techniques to discover new trends and patterns that are hidden within the data and to increases the capability of researchers and practitioners to work with this data. Within this domain there are techniques designed to eliminate irrelevant or redundant features, balance the membership of the classes, handle errors found in the data, and build predictive models for future data. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2015. / FAU Electronic Theses and Dissertations Collection

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that <b>BQP</b> is contained in <b>AWPP</b>, where <b>AWPP</b> is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in <b>AWPP</b>. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals <b>AWPP</b>, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference.

The main subject of this thesis is the investigation of the transformations of pure multipartite entangled states having Schmidt rank 2 by using only local operations assisted with classical communications (LOCC). A new parameterization is used for describing the entangled state of p particles distributed to p distant, spatially separated persons. Product, bipartite and truly multipartite states are identified in this new parametrization. Moreover, alternative parameterizations of local operations carried out by each party are provided. For the case of a deterministic transformation to a truly multipartite final state, one can find an analytic expression that determines whether such a transformation is possible. In this case, a chain of measurements by each party for carrying out the transformation is found. It can also be seen that, under deterministic LOCC transformations, there are some quantities that remain invariant. For the purpose of applying the results of this thesis in the context of the quantum information and computation, brief reviews of the entanglement purification, measurement based quantum computation and quantum codes are given.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:52:55Z (GMT). No. of bitstreams: 1 Faleiros_ThiagodePaulo_M.pdf: 2870028 bytes, checksum: fc82c1cba0951230720985bb3a712fd0 (MD5) Previous issue date: 2010 / Resumo: Investigamos Problemas de Particionamento de objetos que têm relações de similaridade entre si. Instâncias desses problemas podem ser representados por grafos, em que objetos são vértices e a similaridade entre dois objetos é representada por um valor associado à aresta que liga os objetos. O objetivo do problema é particionar os objetos de tal forma que objetos similares pertençam a um mesmo subconjunto de objetos. Nosso foco é o estudo de algoritmos para clusterização em grafos, onde deve-se determinar clusteres tal que arestas ligando vértices de clusteres diferentes tenham peso baixo e ao mesmo tempo as arestas entre vértices de um mesmo cluster tenha peso alto. Problemas de particionamento e clusterização possuem aplicações em diversas áreas, como mineração de dados, recuperação de informação, biologia computacional, entre outros. No caso geral estes problemas são NP-Difíceis. Nosso interesse é investigar algoritmos eficientes (com complexidade de tempo polinomial) e que gerem boas soluções, como Heurísticas, Metaheurísticas e Algoritmos de Aproximação. Dentre os algoritmos estudados, implementamos os mais promissores e fazemos uma comparação de seus resultados utilizando instâncias geradas computacionalmente. Por fim, propomos um algoritmo que utiliza a metaheurística GRASP para o problema considerado e mostramos que, para as instâncias de testes geradas, nosso algoritmo obtém melhores resultados / Abstract: In this work we investigate Partitioning Problems of objects for which a similarity relations is defined. Instance to these problems can be represented by graphs where vertices are objects, and the similarity between two objects is represented by a value associated with an edge that connects objects. The problem objective is to partition the objects such that similar objects belong to the same subset of objects. We study clustering algorithms for graphs, where clusters must be determined such that edges connecting vertices of different clusters have low weight while the edges between vertices of a same cluster have high weight. Partitioning and clustering problems have applications in many areas, such as data mining, information retrieval, computational biology, and others. Many versions of these problems are NP-Hard. Our interest is to study eficient algorithms (with polynomial time complexity) that generate good solutions, such as Heuristics, Approximation Algorithms and Metaheuristics. We implemented the most promising algorithms and compared their results using instances generated computationally. Finally, we propose a GRASP based algorithm for the partition and clustering problem and show that, for the generated test instances, our algorithm achieves better results / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5) Previous issue date: 2009 / Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 / Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 / Doutorado / Matematica Discreta e Combinatoria / Doutor em Ciência da Computação

Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:56:08Z (GMT). No. of bitstreams: 1 Sasaki_AndersonToshiyuki_M.pdf: 1449279 bytes, checksum: 851c64c64afd4605cbfb4946ed5f97a4 (MD5) Previous issue date: 2014 / Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ? NP, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC ¿ Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano, apresentamos um FPTAS. Para outra versão mais geral, na qual o conjunto de objetos geométricos é dado por um sistema de inequações polinomiais algébricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS / Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum. Among the variants of this problem, there are those that arise from a geometric configuration in which both the elements of L and the sets contained in R are geometric objects. As such problems are, in general, NP-hard, if P ? NP, it is impossible to find polynomial-time exact algorithms for them. Thus, the use of efficient approximation algorithms to find high quality solutions becomes a good approach. In this dissertation, we study different versions of the Minimum Disk Cover problem (MDC), in which the sets in R are disks, and we seek to develop approximation algorithms. These versions are related to practical problems, such as base station positioning problem for wireless network design and placement of devices in a sensor network. For the case in which the set of geometric objects to be covered is given by a single line segment, we present an FPTAS. For a more general case, where the set of geometric objects is given by a system of algebraic polynomial inequalities, we propose an approximation algorithm which we prove to be a PTAS / Mestrado / Ciência da Computação / Mestre em Ciência da Computação