Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff / This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games

It has been widely hypothesized that while doing arithmetic, individuals use two distinct routes for phonological output. A direct route is used for exact arithmetic which is language dependent, while an indirect route is used during arithmetic approximation and thought to be language independent. The arithmetic double route has been incorporated on the triple- code model that consists of visual arabic code for identifying strings of digits, magnitude code for knowledge in numeral quantities, and verbal code for rote arithmetic fact. Our goal is to investigate whether language experience has an effect on the processing of exact/approximation math using bilingual participants who have access to two languages, using a theoretical arithmetic processing model, which has been validated across many studies. We have measured the two groups (monolinguals/bilinguals) processing speed for completing the two tasks (Exact/Approximation) in two codes (Arabic digit/Verbal). We hypothesized a faster reaction time in exact arithmetic task in compared to approximation in accordance with the triple-code model. We alsoexpected a main effect for the task (Exact vs.Approximation) independent of the input code when the stimulus was presented in either Arabic digit and/or verbal codes. Our results show exact arithmetic is faster than approximation of arithmetic facts in all codes supporting earlier theories. Also, there was no significant difference in processing speed between monolinguals and bilinguals when performing the arithmetic task in either Arabic and/or verbal codes. In addition, our investigation suggests a modification to the triple-code model when interpreting arithmetic facts in verbal code due to interference of two languages with bilingual participants. Additions to the model can be suggested when the stimulus is expressed in verbal code for visual identification, which may cause interference in bilinguals leading to a first language advantage due to language experience. / Includes bibliography. / Thesis (M.A.)--Florida Atlantic University, 2015. / FAU Electronic Theses and Dissertations Collection

Il existe de nombreuses approches développées par la communauté Implicit Computational Complexity (ICC) permettant d'analyser les ressources nécessaires à la bonne exécution des algorithmes. Dans cette thèse, nous nous intéressons plus particulièrement au contrôle des ressources à l'aide d'interprétations sémantiques. Après avoir rappelé brièvement la notion de quasi-interprétation ainsi que les différentes propriétés et caractérisations qui en découlent, nous présentons les différentes avancées obtenues dans l'étude de cet outil : nous étudions le problème de la synthèse qui consiste à trouver une quasi-interprétation pour un programme donné, puis, nous abordons la question de la modularité des quasi-interprétations. La modularité permet de diminuer la complexité de la procédure de synthèse et de capturer un plus grand nombre d'algorithmes. Après avoir mentionné différentes extensions des quasi-interprétations à des langages de programmation réactifs, bytecode ou d'ordre supérieur, nous introduisons la sup-interprétation. Cette notion généralise la quasi-interprétation et est utilisée dans des critères de contrôle des ressources afin d'étudier la complexité d'un plus grand nombre d'algorithmes dont des algorithmes sur des données infinies ou des algorithmes de type diviser pour régner. Nous combinons cette notion à différents critères de terminaison comme les ordres RPO, les paires de dépendance ou le size-change principle et nous la comparons à la notion de quasi-interprétation. En outre, après avoir caractérisé des petites classes de complexité parallèles, nous donnons quelques heuristiques permettant de synthétiser des sup-interprétations sans la propriété sous-terme, c'est à dire des sup-interprétations qui ne sont pas des quasi-interprétations. Enfin, dans un dernier chapitre, nous adaptons les sup-interprétations à des langages orientés-objet, obtenant ainsi différents critères pour contrôler les ressources d'un programme objet et de ses méthodes / There are several approaches developed by the Implicit Computational Complexity (ICC) community which try to analyze and control program resources. In this document, we focus our study on the resource control with the help of semantics interpretations. After introducing the notion of quasi-interpretation together with its distinct properties and characterizations, we show the results obtained in the study of such a tool: We study the synthesis problem which consists in finding a quasi-interpretation for a given program and we tackle the issue of quasi-interpretation modularity. Modularity allows to decrease the complexity of the synthesis procedure and to capture more algorithms. We present several extensions of quasi-interpretations to reactive programming, bytecode verification or higher-order programming. Afterwards, we introduce the notion of sup-interpretation. This notion strictly generalizes the one of quasi-interpretation and is used in distinct criteria in order to control the resources of more algorithms, including algorithms over infinite data and algorithms using a divide and conquer strategy. We combine sup-interpretations with distinct termination criteria, such as RPO orderings, dependency pairs or size-change principle, and we compare them to the notion of quasi-interpretation. Using the notion of sup-interpretation, we characterize small parallel complexity classes. We provide some heuristics for the sup-interpretation synthesis: we manage to synthesize sup-interpretations without the subterm property, that is, sup-interpretations which are not quasi-interpretations. Finally, we extend sup-interpretations to object-oriented programs, thus obtaining distinct criteria for resource control of object-oriented programs and their methods

This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of application-oriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edge-graceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we investigate the cases (m, k) = (3; 5) and (m, k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k, m = 3 and m = 4. We also describe a procedure to construct a super-edge-graceful tree with any number of edges. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2014. / FAU Electronic Theses and Dissertations Collection

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1979. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / by Daniel U. Friedman. / M.S.

Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. The families of highly regular structures, for example Steiner 2-designs, strongly regular graphs and primitive coherent configurations, have been perceived as difficult cases for graph isomorphism. These highly regular structures arise naturally as obstacles for both the classical group theory and combinatorial approaches for the graph isomorphism problem. In this thesis we investigate the isomorphism problem of highly regular structures. We present new results to understand the combinatorial structure of highly regular structures, and propose some new algorithms to compute the canonical forms (and thus isomorphism testing) of highly regular structures based on the structural theorems. We also give an algorithm solving the isomorphism problem of two unknown graphs in the property testing setting. Our new algorithm has sample complexity matching the information theoretical lower bound up to some multiplicative subpolynomial factor.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...

A simple stochastic game (SSG) is a game defined on a directed multigraph and played between players MAX and MIN. Both players have control over disjoint subsets of vertices: player MAX controls a subset VMAX and player MIN controls a subset VMIN of vertices. The remaining vertices fall into either VAVE, a subset of vertices that support stochastic transitions, or SINK, a subset of vertices that have zero outdegree and are associated with a payoff in the range [0, 1]. The game starts by placing a token on a designated start vertex. The token is moved from its current vertex position to a neighboring one according to certain rules. A fixed strategy σ of player MAX determines where to place the token when the token is at a vertex of VMAX. Likewise, a strategy τ of player MIN determines where to place the token when the token is at a vertex of VMIN. When the token is at a vertex of VAVE, the token is moved to a uniformly at random chosen neighbor. The game stops when the token arrives on a SINK vertex; at this point, player MAX gets the payoff associated with the SINK vertex. A fundamental question related to SSGs is the SSG value problem: Given a SSG G, is there a strategy of player MAX that gives him an expected payoff at least 1/2 regardless of the strategy of player MIN? This problem is among the rare natural combinatorial problems that belong to the class NP ∩ coNP but for which there is no known polynomial-time algorithm. In this thesis, we survey known algorithms for the SSG value problem and characterize them into four groups of algorithms: iterative approximation, strategy improvement, mathematical programming, and randomized algorithms. We obtain two new algorithmic results: Our first result is an improved worst-case, upper bound on the number of iterations required by the Homan-Karp strategy improvement algorithm. Our second result is a randomized Las Vegas strategy improvement algorithm whose expected running time is O(20:78n).

Abstract not available