No description available.

The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. Our research studies formal systems working not just on strings, but on more complex structures such as trees and graphs, in particular syntax trees and semantic graphs. The field of mildly context-sensitive languages concerns attempts to find a useful class of formal languages between the context-free and context-sensitive. We study formalisms defining two candidates for this class; tree-adjoining languages and the languages defined by linear context-free rewriting systems. For the former, we specifically investigate the tree languages, and define a subclass and tree automaton with linear parsing complexity. For the latter, we use the framework of parameterized complexity theory to investigate more deeply the related parsing problems, as well as the connections between various formalisms defining the class. The field of semantic modelling aims towards formally and accurately modelling not only the syntax of natural language statements, but also the meaning. In particular, recent work in semantic graphs motivates our study of graph grammars and graph parsing. To the best of our knowledge, the formalism presented in Paper III of this thesis is the first graph grammar where the uniform parsing problem has polynomial parsing complexity, even for input graphs of unbounded node degree.

Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étude. / Graph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study.

Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque j<i.Dans cette exposé, nous présentons des résultats connus à propos de la S-coloration de packing. Nous apportons de nouveaux résultats à propos de la S-coloration de packing, pour des classes de graphes telles que les chemins, les cycles et les arbres. Nous étudions en détail la complexité du problème de complexité associé à la S-coloration de packing, noté S -COL. Pour certaines instances de S -COL, nous caractérisons des dichotomies entre problèmes NP-complets et problèmes résolubles en tempspolynomial. Nous nous intéressons aux différentes grilles infinies, les grilles hexagonale, carrée, triangulaire et du roi et nous déterminons des propriétés de subdivisions d’un i-packing en plusieurs j-packings, avec j>i. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5. / Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each j<i.In this presentation, we present results about S-packing coloring. We prove new results about the S-coloring of graphs including paths, cycles and trees. We study the complexity problem associated to the S-packing coloring, this problem is denoted S-COL. For some instances of S-COL, we characterize dichotomy between NP-complete problems and problems solved by a polynomial time algorithm. We study also different lattices, the hexagonal, square, triangular and king lattices. We determine properties on the subdivision of an i-packing in several j-packings, for j>i. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.

[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos. Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a scalar function defined on it. This applies in both the classical theory and a discrete version of it defined by Forman in 1995. Those Morse theories permit to characterize a topological space from functions defined on it, but also to study functions based on topological constructions it implies, such as the Morse-Smale complex. While discrete Morse theory applies on general cell complexes in an entirely combinatorial manner, which makes it suitable for computation, the functions it considers are not sampling of continuous functions, but special matchings in the graph encoding the cell complex adjacencies, called Morse matchings. When using this theory to study a topological space, one looks for optimal Morse matchings, i.e. one with the smallest number of critical elements, to get highly succinct topological information about the complex. The first part of this thesis investigates the parameterized complexity of finding such optimal Morse matching. On the one hand the Erasability problem, a closely related problem to finding optimal Morse matchings, is proven to be W[P]-complete. On the other hand, an algorithm is proposed for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter tractable in the tree-width of its dual graph. When using discrete Morse theory to study a scalar function defined on the space, one looks for a Morse matching that captures the geometric information of that function. The second part of this thesis introduces a construction of Morse matchings based on stable matchings. The theoretical guarantees about the relation of such matchings to the geometry are established through surprisingly simple proofs that benefits from the local characterization of the stable matching. The construction and its guarantees work in any dimension. Finally stronger results are obtained if the function is discrete smooth on the complex, a notion defined in this thesis.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-16T13:58:48Z No. of bitstreams: 1 STEFANI SILVA PIRES - DISSERTAÇÃO PGCC 2010..pdf: 819684 bytes, checksum: 625f468cb174d699bf5b98131d1adf61 (MD5) / Made available in DSpace on 2018-08-16T13:58:48Z (GMT). No. of bitstreams: 1 STEFANI SILVA PIRES - DISSERTAÇÃO PGCC 2010..pdf: 819684 bytes, checksum: 625f468cb174d699bf5b98131d1adf61 (MD5) Previous issue date: 2010-08-19 / Este trabalho apresenta uma técnica de análise de causa-raiz para sistemas elétricos de potência. A análise de causa-raiz é uma forma de auxiliar o operador na compreensão da ocorrênciadefalha,interpretandoasocorrênciascomefeito"cascata"entreoselementosda rede. A técnica proposta utiliza o raciocínio baseado em regras, onde regras parametrizadas constroem um modelo de propagação com os diagnósticos de uma ocorrência de falha. A técnica permite apontar o elemento causador da ocorrência, e detalhar a sua propagação para os demais elementos em um modelo de causa-efeito. A utilização de regras parametrizadas traz grandes vantagens ao processo, permitindo que a técnica seja adaptável a alterações na topologia do sistema, e contribuindo para sua escalabilidade. Um estudo de caso foi elaborado para sua avaliação, no contexto da Companhia Hidro Elétrica do São Francisco (CHESF), onde foi desenvolvido um protótipo que implementa a técnica, e levantados um conjunto de regras parametrizadas e um conjunto de cenários de falha utilizando uma ferramenta de simulação de um ambiente real, o Simulop. Utilizamos também na avaliação, um conjunto de regressões, que são dados históricos armazenados pela CHESF. As regressões foramimportantesnaprimeirafasededefiniçãodatécnica,masapresentamproblemascomo afaltadedados,ecomportamentosinesperadosdosistema,ondeamargemdeacertodatécnica foi de 74%. Para o conjunto de cenários levantados com oSimulop, a técnica proposta conseguiu realizar com sucesso o processo de análise de causa-raiz, identificando a causaraiz da ocorrência em 100% dos cenários de falha, e detalhando sua propagação para todos os outros elementos da rede envolvidos em 89% dos cenários, onde a margem de erro é composta de cenários cuja propagação foi identificada apenas parcialmente, devido à falta de regras que contemplassem os cenários. Dessa forma, a técnica proposta se mostrou uma abordagem viável para a análise de causa-raiz em sistemas elétricos. A margem de acerto reduzida nas regressões, indica que, para ser aplicada em um ambiente operacional real, faz-se necessária a elaboração de um conjunto de regras mais abrangente e que possa contornar esses problemas. / This paper presents a root cause analysis technique for electric power systems. The root cause analysis is a way to assist the operator in understanding the occurrence of failure, interpreting the events cascade occurrences. The proposed technique uses a rule based reasoning, where parameterized rules construct a propagation model with diagnosis of an occurrence of failure. The technique allows to point out the element that causes the occurrence, and detailing its propagation to other elements in a cause and effect model. The use of parameterized rules brings major benefits to the process, allowing the technique to be adaptable to changes in system topology, and contributing to its scalability A case study was prepared for evaluation in the context of the Companhia Hidro Elétrica do São Francisco (CHESF). We developed a prototype that implements the technique, and raised a set of parameterized rules and a set of failure scenarios using a tool to simulate a real environment, the Simulop. We also used in the evaluation process, a set of regressions, which are historical data stored by CHESF. The regressions were important in the first phase of the technique, but they have problems such as lack of data, and unexpected behavior of the system, where the accuracy of the technique was 74%. For the set of scenarios created with Simulop, the proposed technique has achieved success in the root cause analysis process, identifying the root cause of the occurrence in 100% of failure scenarios, and detailing their propagation to all other equipments involved in 89% of scenarios, where the margin of error is composed of scenarios whose propagation has been identified only in part due to the lack of rules that contemplate these scenarios. Thus, the proposed technique proved to be a viable approach to root cause analysis in electrical systems. The reduced margin of success in the regressions , indicates that, to be applied to an operational environment, it is necessary to elaborate a comprehensive set of rules that can deal these problems.