A combinatorial game is a game in which all players have perfect information and there is no element of chance; some well-known examples include othello, checkers, and chess. When people play combinatorial games they develop strategies, which can be viewed as a function which takes as input a game position and returns a move to make from that position. A strategy is winning if it guarantees the player victory despite whatever legal moves any opponent may make in response. The classical complexity of deciding whether a winning strategy exists for a given position in some combinatorial game has been well-studied both in general and for many specific combinatorial games. The vast majority of these problems are, depending on the specific properties of the game or class of games being studied, complete for either PSPACE or EXP. In the parameterized complexity setting, Downey and Fellows initiated a study of "short" (or k-move) winning strategy problems. This can be seen as a generalization of "mate-in-k" chess problems, in which the goal is to find a strategy which checkmates your opponent within k moves regardless of how he responds. In their monograph on parameterized complexity, Downey and Fellows suggested that AW[*] was the "natural home" of short winning strategy problems, but there has been little work in this field since then. In this thesis, we study the parameterized complexity of finding short winning strategies in combinatorial games. We consider both the general and several specific cases. In the general case we show that many short games are as hard classically as their original variants, and that finding a short winning strategy is hard for AW[P] when the rules are implemented as succinct circuits. For specific short games, we show that endgame problems for checkers and othello are in FPT, that alternating hitting set, hex, and the non-endgame problem for othello are in AW[*], and that short chess is AW[*]-complete. We also consider pursuit-evasion parameterized by the number of cops. We show that two variants of pursuit-evasion are AW[*]-hard, and that the short versions of these problems are AW[*]-complete.

The purpose of this dissertation is to develop a new generative grammar, based on the principles of intensional logic. More specifically, the goal is to create a psychologically real grammar model for use in natural language processing. The new grammar consists of a set of context-free rewrite rules tagged with intensional versions. Most generative grammars, such as transformational grammar, lexical functional-grammar and head-driven phrase structure grammar, extend traditional context-free grammars with a mechanism for dealing with contextual information, such as subcategorization of words and agreement between different phrasal elements. In these grammars there is not enough separation between the utterances of a language and the context in which they are uttered. Their models of language seem to assume that context is in some way encapsulated in the words of the language instead of the other way around. In intensional logic, the truth of a statement is considered in the context in which it is uttered, unlike traditional predicate logic in which truth is assigned in a vacuum, regardless of when or where it may have been stated. To date, the application of the principles of intensionality to natural languages has been confined to semantic theory. We remedy this by applying the ideas of intensional logic to syntactic context, resulting in intensional context-free grammar. Our grammar takes full advantage of the simplicity and elegance of context-free grammars while accounting for information that is beyond the sentence itself, in a realistic way. Sentence derivation is entirely encapsulated in the context of its utterance. In fact, for any particular context, the entire language of the grammar is encapsulated in that context. This is evidenced by our proof that the language of an intensional grammar is a set of context-free languages, indexed by context. To further support our claims we design and implement a small fragment of English using the grammar. The English grammar is capable of generating both passive and active sentences that include a subject, verb and up to two optional objects. Furthermore, we have implemented a partial French to English translation system that uses a single language dimension to initiate a translation. This allows us to include multiple languages in one grammar, unlike other systems which must separate the grammars of each language. This result has led this author to believe that we have created a grammar that is a viable candidate for a true Universal Grammar, far exceeding our initial goals. / Graduate / 0984 / 0800 / 0290 / rlittle@uvic.ca

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2009. / Includes bibliographical references.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

This thesis concerns decision procedures for fragments of linear arithmetic and their application to model-checking one-counter automata. The first part of this thesis covers the complexity of decision problems for different types of linear arithmetic, namely the existential subset of the first-order linear theory over the p-adic numbers and the existential subset of Presburger arithmetic with divisibility, with all integer constants and coefficients represented in binary. The most important result of this part is a new upper complexity bound of <b>NEXPTIME</b> for existential Presburger arithmetic with divisibility. The best bound that was known previously was <b>2NEXPTIME</b>, which followed directly from the original proof of decidability of this theory by Lipshitz in 1976. Lipshitz also gave a proof of <b>NP</b>-hardness of the problem in 1981. Our result is the first improvement of the bound since this original description of a decision procedure. Another new result, which is both an important building block in establishing our new upper complexity bound for existential Presburger arithmetic with divisibility and an interesting result in its own right, is that the decision problem for the existential linear theory of the p-adic numbers is in the Counting Hierarchy <b>CH</b>, and thus within <b>PSPACE</b>. The precise complexity of this problem was stated as open by Weispfenning in 1988, who showed that it is in <b>EXPTIME</b> and <b>NP</b>-hard. The second part of this thesis covers two problems concerning one-counter automata. The first problem is an LTL synthesis problem on one-counter automata with integer-valued and parameterised updates and with equality tests. The decidability of this problem was stated as open by G&ouml;ller et al. in 2010. We give a reduction of this problem to the decision problem of a subset of Presburger arithmetic with divisibility with one quantifier alternation and a restriction on existentially quantified variables. A proof of decidability of this theory is currently under review. The final result of this thesis concerns a type of one-counter automata that differs from the previous one in that it allows parameters only on tests, not actions, and it includes both equality and disequality tests on counter values. The decidability of the basic reachability problem on such one-counter automata was stated as an open problem by Demri and Sangnier in 2010. We show that this problem is decidable by a reduction to the decision problem for Presburger arithmetic.

Nesta tese apresentamos a abordagem da Mecânica Estatística para o clássico problema de otimização denominado problema da partição numérica (PPN), que é definido como: Dada uma seqüência de N números reais positivos {a1, a2, a3,....aN}, o problema consiste em particioná-los em dois conjuntos complementares, A e Ac, tais que o valor absoluto da diferença da soma dos ais nos dois conjuntos seja minimizada. No caso em que os aj\'s são variáveis aleatórias estatisticamente independentes distribuídas uniformemente no intervalo unitário, este problema NP-completo equivale ao problema de encontrar o estado fundamental de um modelo de Ising antiferromagnético aleatório de alcance infinito. Conseqüentemente, a análise probabilística do PPN pode ser realizada com as ferramentas da Mecânica Estatística de sistemas desordenados. Neste trabalho empregamos a aproximação recozida (annealed) para derivar uma expressão analítica para o limitante inferior do valor médio da diferença para partições tanto com vínculo de cardinalidade quanto sem vínculo para grandes valores de N. Além disso, calculamos analiticamente a fração de estados metaestáveis, isto é, estados que possuem a menor energia mediante todos os vizinhos (estados que diferem pela troca de um único spin). Concluímos a análise da abordagem direta, cujas instâncias . / In this thesis we present a statistical mechanics approach to a classical optimization problem called the number partitioning problem (NPP), which is stated as follows. Given a sequence of N positive real numbers , the number partitioning problem consists of partitioning them into two sets A and its complementary set Ac such that the absolute value of the difference of the sums of aj over the two sets is minimized. In each case in which the aj\'s are statistically independent random variables uniformly distributed in the unit interval, this NP-complete problem is equivalent to the problem of finding the ground state of an infinite range, random antiferromagnetic Ising model. Hence the probabilistic analysis of the NPP can be carried out within the framework of the standard statistical mechanics of disordered systems. In this vein we employ the annealed approximation to derive analytical lower bounds to the average value of the difference for the best-constrained and unconstrained partitions in the large N limit. Furthermore, we calculate analytically the fraction of metastable states, i.e. states that are stable against all single spin flips. We conclude the analysis of the so-called direct approach, in which the instances {ai} are fixed and the partitions are variable, with the analytical study of the linear programming relaxation of this NP-complete integer programming. In the second part of this thesis we propose and explore an inverse approach to the NPP, in which the optimal partitions are fixed and the instances are variable. Specifically, using the replica framework we study analytically the instance space of the number partitioning problem. We show that, regardless of the distribution of the instance entries, there is an upper bound &#945cN to the number of perfect random partitions (i.e. partitions for which that difference is zero). In particular, in the case where the two sets have the same cardinality (balanced partitions) we find &#945c =1/2. Moreover, in the case of unbalanced partitions, we show that perfect random partitions exist only if the difference between the cardinalities of the two sets scales like m N-1/2}.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T05:20:45Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_M.pdf: 1592906 bytes, checksum: 7d6d43104cbdeb2ad46a93e6ef11ae23 (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação consideramos o problema do k-Servidor. Neste problema temos k servidores em um espaço métrico e nosso objetivo e atender a uma seqüência de requisições, de modo a minimizar a distancia total percorrida pelos servidores. Dedicamos especial atenção a conjectura do k-Servidor: qualquer espaço métrico admite um algoritmo k-competitivo para o problema do k-Servidor. Este e um dos problemas mais importantes em aberto da area de computação online. O algoritmo da função trabalho, proposto por Chrobak e Larmore, e especialmente relevante para a conjectura. Isto porque foi provado que este algoritmo e k-competitivo para diversos casos particulares do problema do k-Servidor. Alem disso, acredita-se que este algoritmo e de fato k-competitivo para todo espaço métrico. Por isto, o entendimento deste algoritmo e central neste trabalho. Para analisar o algoritmo da função trabalho são utilizados diversos resultados auxiliares desenvolvidos por vários autores. Neste trabalho tentamos apresentar de forma coesa uma coletânea destes resultados. A partir desta mostramos uma prova do teorema de Koutsoupias e Papadimitriou: o algoritmo da função trabalho e (2k - 1)-competitivo para todo espaço métrico. Este e o resultado mais importante relacionado ao problema do k-Servidor. Alem disso, mostramos que a conjectura do k-Servidor vale para alguns casos particulares do problema / Abstract: In this work we study the k-server problem. In this problem, we have k servers on a metric space that must attend a sequence of requests with the goal of minimizing the total distance moved by the servers. We dedicate special attention to the k-server conjecture: any metric space allows for a k-competitive k-server algorithm. This is one of the most important open problems in online computing. The work function algorithm, proposed by Chrobak and Larmore, is very relevant to the conjecture. It has been proved that this algorithm is k-competitive for several special cases of the k-server problem. Furthermore, most researchers believe that the algorithm is indeed k-competitive for any metric space. Thus, a deeper understanding of this algorithm plays a special role in this work. To analyze the work function algorithm, we use many auxiliary results developed by several authors. In this work we tried to present a collection of these results in a concise way. From this, we present a proof of Koutsoupias and Papadimitriou's theorem: the work function algorithm is (2k - 1)-competitive for any metric space. This is the most important result related to the k-server problem. Moreover, we show that the k-server conjecture holds in some special cases / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Orientador: Celia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-08-06T12:11:33Z (GMT). No. of bitstreams: 1 Campos_ChristianeNeme_D.pdf: 1048367 bytes, checksum: e8270db6704873ddaf2043927ca93e99 (MD5) Previous issue date: 2006 / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

This thesis formalizes a model of bounded rationality in extensive-form games called game-playing schemata. In this model, the strategies are repre- sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multi-player extensive-form game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPAD-hard. Moreover, for a class of efficiently representable strategies, computing MAXPAY-EFCE can be done in polynomial time. 1

The transportation industry is responsible for 26% of all emission of greenhouse gases in the European Union. Many steps are being taken to minimise greenhouse gas emissions. The most effective way to reduce the emission of greenhouse gases is by transitioning to biofuels. The combustion engines in most vehicles perform below their potential efficiency when running on biofuels due to the reduced energy density. The characteristics of the injection into the combustion chamber can be adjusted if the fuel type being injected is known. In Diesel engines, Fatty Acid Methyl Esters (FAME) is one of the most used biofuels. The higher weight density and lower energy density of FAME compared to Diesel result in lower power output when used in a Diesel engine. Detecting the fuel composition in the engine would allow for adaptation to the injection characteristics and bring back the engine’s efficiency to its full potential independent of the fuel composition. The most significant issue with fuel composition prediction is that no work has been done in this field using machine learning. There are several hundreds of features inside the control system of a truck. The selection of which features contribute to the prediction of fuel composition is important and challenging. The prediction should be computationally inexpensive and relatively accurate to facilitate in-time prediction. Using a feature selection method based on Shapley additive explanations (SHAP) applied to an expert network enables feature selection perfectly tailored for finding the optimal features that combined will provide accurate predictions with minimal computational resources. This feature selection method has been tested before but with limited analysis and adaptation. We apply various feature selection methods and propose a new feature selection method coined SHAP-C, which outperforms all other feature selection methods we have tested for this particular scope of application. The results show that with a minimal network of two input features and six hidden nodes, the fuel composition can be predicted with a 98.82% accuracy using a total of 75 floating-point operations. The low computational complexity allows for real-time predictions in the control system of a truck, which can be used to modulate the injection characteristics into the engine’s combustion chamber. The network used to identify the fuel composition has been trained with data from a single truck. The results are therefore not generalised across trucks. This adjustment based on fuel composition would allow a truck to run optimally independent of the fuel composition. / Transportindustrin är ansvarig för 26% av alla utsläpp i den Europeiska Unionen. Många steg tas för att minimera utsläpp av växthusgaser. En av de mest effektiva metoderna för att minska utsläppen är biobränslen. Förbränningsmotorer i de flesta fordon underpresterar när de använder biobränslen som källa för energi. Karaktäristiken av injektionen i förbränningskammaren kan justeras om bränsletypen är känd. I dieselmotorer är fettsyrametylestrar en av de mest använda biobränslena. Den högre densiteten i vikt och den lägre densiteten i energi resulterar i en låg effekt när biobränslet används i en dieselmotor. Detektering av bränslekomposition i bränslesystemet skulle möjliggöra en adaptiv injektion av bränsle för att optimera effektiviteten av motorn. Det största problemet med bränsledetektering är att inget arbete har gjorts inom maskininlärning i detta område. Det finns hundratals olika mätvärden inuti kontrollsystemet av en lastbil. Valet av vilket mätvärde som bidrar till en träffsäker beräkning av bränslekomposition är mycket viktigt. Beräkningen måste vara beräkningsmässigt billig, snabb och träffsäker. Därför måste en skräddarsydd lösning byggas för att finna de bästa mätvärden med minimal beräkningskostnad för att kunna beräkna bränsletyp i realtid. Användningen av en mätvärdesväljande metod baserad på SHAP och ett expert-nätverk tillåter ett val av mätpunkter som är perfekt anpassat för att finna vilka mätpunkter är optimala för att träffsäkert och beräkningsbilligt ta fram bränslekompositionen. Detta val av mätvärden har testats förut men klassades som opålitligt på grund av den slumpmässiga naturen av neurala nätverk. Denna brist har överkommits genom att träna ett stort antal expertnätverk och använda resultatet från genomsnittet över alla modeller, vilket eliminerar den stokastiska naturen av problemet. Resultaten visar att med hjälp av ett litet nätverk med två mätpunkter och sex dolda noder, kan bränslekompositionen beräknas med en träffsäkerhet av 98.82% med endast 75 flyttalsoperationer. Detta tillåter för realtids beräkning av bränslekomposition i kontrollsystemet till en lastbil, vilket i sin tur kan modulera injektionskaraktäristiken av bränsle till förbränningskammaren i motorn. Denna justering baserat på bränslekompositionen tillåter en lastbil att köras optimalt oavsätt komposition av bränsle.