Verification of knowledge-bases is a critical step to ensure the quality of a knowledge-based system. The success of these systems depends heavily on how qualitative the knowledge is. Manual verification is however cumbersome and error prone, especially for large knowledge-bases. This thesis provides a design theory, based upon the suggested framework by Gregor and Jones (2007). The theory proposes a general design of automated verification tools, which have the abilities of verifying heuristic knowledge in rule-based systems utilizing certainty factors. Included is a verification of completeness and consistency technique customized to this class of knowledge-based systems. The design theory is instantiated in a real-world verification tool development project at Uppsala University. Considerable attention is given to the design and implementation of this artifact – uncovering issues and considerations involved in the development process. For the knowledge management practitioner, this thesis offers guidance and recommendations for automated verification tool development projects. For the IS research community, the thesis contributes with extensions of existing design theory, and reveals some of the complexity involved with verification of a specific rule-based system utilizing certainty factors.

Cette thèse étudie les aspects combinatoires, algorithmiques et la complexité de problèmes de théorie des graphes, et tout spécialement de problèmes liés aux notions de marches, de transitions et de distance dans les graphes. Nous nous intéressons d’abord au problème de traffic monitoring, qui consiste à placer aussi peu de capteurs que possible sur les arcs d’un graphe de façon à pouvoir reconstituer des marches d’objets. La caractérisation d’instances intéressantes dans la pratique nous amène à la notion de transitions interdites, qui renforce le modèle de graphe. Notre travail sur les graphes à transitions interdites comprend aussi l’étude de la notion d’ensemble de transitions connectant, que l’on peut voir comme l’analogue en terme de transitions de la notion d’arbre couvrant. Une partie importante de cette thèse porte sur les graphes géométriques, qui sont des graphes dont les sommets sont des points de l’espace réel et dont les arêtes sont déterminées par les distances géométriques entre les sommets. Ces graphes sont au coeur du célèbre problème de Hadwiger-Nelson et nous sont d’une grande aide dans notre étude de la densité des ensembles qui évitent la distance 1 dans plusieurs types d’espaces normés. Nous développons des outils pour étudier ces problèmes et les utilisons pour prouver la conjecture de Bachoc-Robins sur plusieurs paralléloèdres. Nous nous penchons aussi sur le cas du plan euclidien et améliorons les bornes sur la densité des ensembles évitant la distance 1 et sur son nombre chromatique fractionnaire. Enfin, nous étudions la complexité de problèmes d’homomorphismes de graphes et établissons des théorèmes de dichotomie sur la complexité des homomorphismes localement injectifs vers les tournois réflexifs. / This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs. We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees. A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger- Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number. Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.

There isn t a unique development process suitable for all software projects. Standards and quality models such as ISO/IEC 15504, MPS.BR, CMM and CMMI, recommend the process tailoring to satisfy specific project features. However process tailoring is a complex task because it requires knowledge and expertise of who performs. The incomplete or duplicate process elements selection can generate ambiguities which may disturb the project progress and generate distrust in relation to the tailored process. This dissertation presents a systematic strategy to completeness and internal consistency validation of the elements that are part of the tailored process, call fragments. The aim is to contribute to improving the software development process quality and help the process engineer on the process tailoring task, providing complete and consistent process elements which are prioritized according to the project features. To support the proposed strategy have benn developed: i) ontology to similarity recognition among process; ii) a metamodel for process tailoring; iii) a web toll for complete and consistent process definition. The proposed strategy facilitates the work of the engineer showing which elements are adequate (complete and consistent) to be part of the tailored process and enables the elimination of inconsistences lead to improving the process. / Não existe um modelo de processo de desenvolvimento único para ser adotado para todos os projetos de software. Normas e modelos de qualidade como a norma ISO/IEC 15504, MPS.BR, CMM e o CMMI preconizam que a adaptação de processos seja realizada para satisfazer às necessidades específicas dos projetos. Entretanto, a atividade de adaptar um processo de software é considerada uma tarefa complexa, exigindo conhecimento e experiência de quem a realiza. A seleção de elementos de processo incompletos, ou duplicados podem gerar ambiguidades que podem comprometer o andamento do projeto e gerar desconfiança para com o processo adaptado. Esta dissertação apresenta uma estratégia sistemática para validação da completude e consistência interna dos elementos formadores do processo adaptado, neste trabalho chamados fragmentos. O objetivo é contribuir para a melhoria da qualidade dos processos de desenvolvimento de software adaptados e auxiliar o engenheiro de processos na tarefa de adaptação de processos, fornecendo elementos de processo completos, consistentes e priorizados de acordo com as características do projeto. Para apoiar a proposta, foram desenvolvidas: i) uma ontologia para reconhecimento da similaridade em processos; ii) um metamodelo para adaptação de processos e iii) uma ferramenta web para definição de processos completos e consistentes. A estratégia proposta facilita o trabalho do engenheiro de processos informando para este quais elementos são adequados (completos e consistentes), e possibilita a eliminação de inconsistências levando a melhoria do processo.

Made available in DSpace on 2014-07-29T15:04:47Z (GMT). No. of bitstreams: 1 Dissertacao Fabiana Ribeiro.pdf: 514869 bytes, checksum: 6bb71953139e7fc8f2ccc49941ea41fe (MD5) Previous issue date: 2007-02-28 / The completeness has guided change processes, in the formation of the nurse. So, it is important to know the initiatives in courses of Graduation in Nursing, with the focus in this principle. It is about a descriptive-exploratory study, that aims to analyze the conceptions of completeness that are present in the speeches of the professors, and the strategies used for the apprehension of completeness for the pupils. Professors from three Institutions of Higher Education (HE) existing in the State of Goiás that had integrated at least a resume, in the year of 2005 participated of this study.The collection of data was carried out in the respective institutions, between April and September of 2006, after previous appointment. Eleven professors of the feminine gender composed the study. They were at between 40 and 55 years old, with teaching experience that varies from 15 to 32 years and the majority has After- Graduation Stricto-Sensu course. The interviews and the plans of teching of the representative professors of the áreas of Sciences of the Nursing (Beddings of Nursing, Assistance of Nursing, Administration of Nursing and Education of Nursing) has been analyzed according to Bardin (2003). By means of the analysis, three conceptions of completeness had emerged: Completeness of the Care: of the singular to the global one; Completeness of the Care: the ways for the SUS and Completeness of the Care: strategies for the learning. The directions of the completeness of the care had revealed innovative, to the measure that value the singular, global and the ways for the SUS. They reveal the directions, giving the care to the human being in its social reality, with its specificities and subjectivities, considering the social nets of care and where they are inserted. They have tried to develop learn to learn and make, and learn to be and to live together as strategies for the learning, creating possibilities for the students to apprehend all the directions manifested by the professors. We waint that the results, of this research, can contribute for the reflection of the professors of the HE on the direction of the completeness of the care, in the area of education, as well as, to reorient the formation process, giving potency to the human resources and to the strategies that have already been used in the direction of the continuous construction of completeness of the care, in the health area. / A integralidade tem norteado processos de mudanças, na formação do enfermeiro. Assim, é importante conhecer as iniciativas em cursos de Graduação em Enfermagem, com foco nesse princípio. Trata-se de um estudo descritivoexploratório, com objetivos de analisar as concepções de integralidade presentes, nos discursos dos docentes, e as estratégias utilizadas para a apreensão de integralidade pelos alunos. Participaram docentes de três Instituições de Ensino Superior (IES) existentes no Estado de Goiás, que haviam integralizado pelo menos um currículo, no ano de 2005. A coleta de dados ocorreu nas respectivas instituições, entre abril e setembro de 2006, após agendamento prévio. Compuseram o estudo onze docentes do gênero feminino, com idade entre 40 e 55 anos, com experiência em docência, variando de 15 a 32 anos e a maioria portadora de Pós-Graduação Stricto-Sensu. As entrevistas e os planos de ensino dos docentes representantes das áreas das Ciências da Enfermagem (Fundamentos de Enfermagem, Assistência de Enfermagem, Administração de Enfermagem e Ensino de Enfermagem) foram analisados segundo Bardin (2003). Por meio da análise, emergiram três concepções de integralidade: Integralidade do Cuidado: do singular ao global; Integralidade do Cuidado: os caminhos para o SUS e Integralidade do Cuidado: estratégias para a ensinagem. Os sentidos da integralidade do cuidado mostraram-se inovadores, à medida que valorizam o singular, o global e os caminhos para o SUS. Manifestam os sentidos, prestando o cuidado ao ser humano na sua realidade social, com as suas especificidades e subjetividades, considerando as redes de cuidado e sociais em que estão inseridos. Como estratégias para a ensinagem, buscam desenvolver o aprender a aprender e fazer e aprender a ser e viver junto, possibilitando meios para que os educandos apreendam todos os sentidos manifestos pelos docentes. Esperamos que os resultados, desta pesquisa, possam contribuir para a reflexão dos docentes das IES sobre o sentido da integralidade do cuidado, na área de ensino, assim como, reorientar o processo de formação, potencializando os recursos humanos e estratégias já utilizadas, rumo à construção contínua de integralidade do cuidado, na área de saúde.

Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph.

Dans une composition de services Web basée protocole, un ensemble de services composants se collaborent pour donner lieu à un service Composite. Chaque service est représenté par un automate à états finis (AEF). Au sein d’un AEF, chaque transition exprime l’exécution d’une opération qui fait avancer le service vers un état suivant. Une exécution du composite correspond à une séquence de transitions où chacune est déléguée à un des composants. Lors de l’exécution du composite, un ou plusieurs composants peuvent devenir indisponibles. Ceci peut produire une exécution incomplète du composite, et de ce fait un recouvrement est nécessaire. Le recouvrement consiste à transformer l’exécution incomplète en une exécution alternative ayant encore la capacité d’aller vers un état final. La transformation s'effectue en compensant certaines transitions et exécutant d’autres. Cette thèse présente une étude formelle du problème de recouvrement dans une composition de service Web basée protocole. Le problème de recouvrement consiste à trouver une meilleure exécution alternative parmi celles disponibles. Une meilleure alternative doit être atteignable à partir de l’exécution incomplète avec un nombre minimal de compensations visibles (vis-à-vis le client). Pour une exécution alternative donnée, nous prouvons que le problème de décision associé au calcul du nombre de transitions invisiblement compensées est NP-Complet. De ce fait, nous concluons que le problème de décision associé au recouvrement appartient à la classe ΣP2. / In a protocol-based Web service composition, a set of available component services collaborate together in order to provide a new composite service. Services export their protocols as finite state machines (FSMs). A transition in the FSM represents a task execution that makes the service moving to a next state. An execution of the composite corresponds to a sequence of transitions where each task is delegated to a component service. During composite run, one or more delegated components may become unavailable due to hard or soft problems on the Network. This unavailability may result in a failed execution of the composite. We provide in this thesis a formal study of the automatic recovery problem in the protocol-based Web service composition. Recovery consists in transforming the failed execution into a recovery execution. Such a transformation is performed by compensating some transitions and executing some others. The recovery execution is an alternative execution of the composite that still has the ability to reach a final state. The recovery problem consists then in finding the best recovery execution(s) among those available. The best recovery execution is attainable from the failed execution with a minimal number of visible compensations with respect to the client. For a given recovery execution, we prove that the decision problem associated with computing the number of invisibly-compensated transitions is NP-complete. Thus, we conclude that deciding of the best recovery execution is in ΣP2.

Ce travail étudie les variétés pseudo-riemanniennes compactes localement homogènes à travers le prisme des (G,X)-structures, introduites par Thurston dans son programme de géométrisation. Nous commençons par présenter la problématique générale et discutons notamment du rapport entre la complétude géodésique de ces variétés et une autre notion de complétude propre aux (G,X)-structures. Nous donnons également dans le chapitre 1 une nouvelle preuve d’un théorème de Bromberg et Medina qui classifie les métriques lorentziennes invariantes à gauche sur SL(2,R) dont le flot géodésique est complet. Conjecturalement, toute (G,X)-structure pseudo-riemannienne sur une variété compacte est complète. Nous prouvons ici que cela est vrai pour certaines géométries, sous l’hypothèse que la (G,X)-structure est a priori kleinienne. On en déduit que, pour ces géométries, la complétude est une condition fermée. Lorsque X est un groupe de Lie de rang 1 muni de sa métrique de Killing, ce résultat complète un théorème de Guéritaud–Guichard–Kassel–Wienhard selon lequel la complétude est une condition ouverte. Nous nous tournons ensuite vers l’étude des représentations d’un groupe de surface à valeurs dans les isométries d’une variété riemannienne M complète simplement connexe de courbure sectionnelle inférieure à -1. Étant donnée une telle représentation ρ, nous montrons que l’ensemble des représentations fuchsiennes j telles qu’il existe une application (j,ρ)-équivariante et contractante de H2 dans M est un ouvert non vide et contractile de l’espace de Teichmüller (sauf lorsque ρ est elle-même fuchsienne). Ce résultat nous permet de décrire l’espace des métriques lorentziennes de courbure constante -1 sur un fibré en cercle au-dessus d’une surface compacte. Nous montrons que cet espace possède un nombre fini de composantes connexes classifiées par un invariant que nous appelons longueur de la fibre. Nous prouvons également que le volume total de ces métriques ne dépend que de la topologie du fibré et de la longueur de la fibre. / In this work, we study closed locally homogeneous pseudo-Riemannian manifolds through the notion of (G,X)-structure, introduced by Thurston in his geometrization program. We start by presenting the general problem. In particular, we discuss the link between geodesical completeness of those manifolds and another notion of completeness specific to (G,X)-structures. In chapter 1, we also give a new proof of a theorem by Bromberg and Medina which classifies left invariant Lorentz metrics on SL(2,R) that are geodesically complete. Conjecturally, every pseudo-riemannian (G,X)-structure on a closed manifold is complete. Here we prove that it holds for certain geometries, provided that the (G,X )-structure is a priori Kleinian . This implies that, for such geometries, completeness is a closed condition. When X is a Lie group of rank 1 handled with its Killing metric, this result complements a theorem of Guéritaud–Guichard–Kassel–Wienhard, acording to which completeness is an open condition. We then turn to the study of representations of surface groups into the isometry group of a complete simply connected Riemannian manifold M of curvature less than or equal to -1. Given such a representation ρ, we prove that the set of Fuchsian representations j for which there exists a (j,ρ)-equivariant contracting map from H2 to M is a non-empty open contractible subset of the Teichmüller space (unless ρ itself is Fuchsian). This result allows us to describe the space of Lorentz metrics of constant curvature -1 on a circle bundle over a closed surface. We show that this space has finitely many connected components, classified by an invariant that we call the length of the fiber. We also prove that the total volume of those metrics only depends on the topology of the bundle and on the length of the fiber.

Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un même sous-graphe), dans lesquels nous étudierons différents types de problèmes liés à l’existence de sous-graphes sans conflit, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de \mathcal{N P}-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle hamiltonien) sans conflits. / We will look at graphs with conflicts (conflict is a pair of edges can not simultaneously be part of the same subgraph), in which we will study different types of problems related to the existence of subgraphs without conflict. The nature of the problems is both combinatorial and algorithmic. Our guideline is the notion of connectivity. We will see several results, simple without conflict, are no longer when adding conflicts. We will present exact algorithms (not polynomial), \mathcal{N P}-completeness results and sufficient conditions ensuring the existence of certain objects (spanning tree, path and Hamiltonian cycle) without conflict.

En prenant comme point de départ l'interprétation de l'épopée homérique par Erich Auerbach, ce mémoire se consacre à la notion d'immersion fictionnelle, non sous son versant psychologique de phénomène contingent de la conscience imageante, mais sous son versant imaginaire, en tant que mythe sociétal d'immédiateté déterminant des stratégies esthétiques et médiatiques concrètes, que j'articule autour des poétiques contemporaines de construction de mondes (world building). L'enjeu est de saisir les répercussions esthétiques de ce fantasme d'une représentation qui occulterait à la fois sa médiateté et le réel-sensible, à une époque où la transfictionnalité et la transmédiaticité s'élèvent tranquillement comme modes narratifs dominants de notre culture occidentale contemporaine. Avec cette conviction que le terme d'immersion doit être replacé dans le cadre de ses effets, le premier chapitre s'affairera à démêler quelques difficultés théoriques que pose la notion en la problématisant sous l'égide des questions ontologiques de vérité et de la position phénoménologique de Sartre sur l'imaginaire. Tout en posant les outils théoriques nécessaires aux analyses subséquentes, le deuxième chapitre approfondit cette problématisation en empruntant aux théories modales des mondes possibles un cadre conceptuel opératoire, qui amènera, notamment grâce au concept formalisé de «~monde~», à concevoir la fiction comme un mouvement de distanciation. Appuyé par la lecture du roman tolkienien, le troisième chapitre tourne le fantasme d'immersion du côté d'une pulsion encyclopédique de complétude, concrétisée par des stratégies textuelles d'accumulation informationnelle et de virtualisation de données diégétiques laissées en suspens -- effets d'actualité que je qualifie d'extra-narratifs en les présentant en contraste des principes prescriptifs du \emph{muthos} aristotélicien formant une chaîne causale téléologique fondée sur une loi d'économie narrative. Le quatrième et dernier chapitre, articulé autour de la notion encore trop peu étudiée de canonicité, observe les poétiques de construction de mondes telles qu'elles se désamorcent elles-mêmes, dans le contexte des univers partagés, en engendrant des incohérences logiques donnant lieu à la tenue d'un discours auctorial-éditorial régissant les vérités fictionnelles comme moyen de maintenir l'immersivité de la représentation. L'analyse générique des comic-books de superhéros et une enquête sur la gestion éditoriale de l'univers de Star Wars permettront d'identifier les multiples modalités de délimitation de la frontière entre canon et apocryphe. En conclusion, je reviens brièvement sur la notion d'immersion, ainsi exemplifiée, en la resémiotisant comme une médiation compétitive de mise en présence de l'être. / Starting from Erich Auerbach's interpretation of the Homeric epic, this master's dissertation studies the notion of fictional immersion, not in its psychological aspect of a contingent phenomena of human consciousness, but rather in its collective imaginary sense, as a societal myth of immediacy generating concrete aesthetic and media strategies that I investigate from the standpoint of contemporary poetics of world building. The objective is to apprehend the aesthetic repercussions of this desire for a mediation that would conceal both the real and its own mediacy, in a time where transfictionality and transmedia storytelling are becoming more and more the dominant narrative modes of our contemporary western culture. Under the conviction that immersion must be looked at as a set of cultural strategies, the first chapter unravels some theorical difficulties bounded to the term by problematizing it towards ontological questions of truth and Sartre's phenomenological stance on the imaginary. While laying a necessary theorical toolset for subsequent analyses, the second chapter examines these problems by borrowing to possible worlds modal theories a set of working concepts, which will lead to the assumption that fiction is a movement of distanciation, notably with the aide of the formal concept of ``world''. Through a reading of the tolkienian novel, the third chapter directs the desire for immersion towards an encyclopedic impulsion for completeness, embodied by textual strategies such as informational proliferation and allusion to virtual diegetic data -- strategies leaving an impression of the actual that I describe as extra-narrative in contrast to Aristote's \emph{muthos} forming a teological causal chain based on a principle of an unitary narrative. The fourth and final chapter, articulated around the still too little studied notion of canonicity, observes poetics of world building as they neutralize themselves, particularly with shared universes, by generating logical inconsistencies giving birth to authorial and editorial discourses stating fictional truths as a way of maintaining the mediation's immersivity. The analysis of the superhero comics genre and an inquiry of the editorial management of the Star Wars universe will exemplify the multiple modalities of this delimitation between the canon and the apocryphal. As a conclusion, I briefly come back to the notion of immersion itself by redescribing it as a competitive mediation of presence.

Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)