This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics: <ul><li> Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof. </li><li> The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level. </li><li> While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues. </li><li> In several chapters, new algorithms and interesting new variants of existing algorithms are presented. </li><li> It gives new presentations of many existing algorithms — all in a common format with common examples. </li><li> There are extensive links to the existing literature. </li></ul> / Thesis (PhD)--University of Pretoria, 2010. / Computer Science / unrestricted

Les programmes informatiques prennent une place de plus en plus importante dans nos vies. Certains de ces programmes, comme par exemple les systèmes de contrôle de centrales électriques, d'avions ou de systèmes médicaux sont critiques : une panne ou un dysfonctionnement pourraient causer la perte de vies humaines ou des dommages matériels ou environnementaux importants. Les méthodes formelles visent à offrir des moyens de concevoir et vérifier de tels systèmes afin de garantir qu'ils fonctionneront comme prévu. Au fil du temps, ces systèmes deviennent de plus en plus évolués et complexes, ce qui est source de nouveaux défis pour leur vérification. Il devient nécessaire de développer ces systèmes de manière modulaire afin de pouvoir distribuer la tâche d'implémentation à différentes équipes d'ingénieurs. De plus, il est important de pouvoir réutiliser des éléments certifiés et les adapter pour répondre à de nouveaux besoins. Aussi les méthodes formelles doivent évoluer afin de s'adapter à la conception et à la vérification de ces systèmes modulaires de taille toujours croissante. Nous travaillons sur une approche algébrique pour la conception de systèmes corrects par construction. Elle définit un formalisme pour exprimer des spécifications de haut niveau et permet de les raffiner de manière incrémentale en des spécifications plus concrètes tout en préservant leurs propriétés, jusqu'à ce qu'une implémentation soit atteinte. Elle définit également plusieurs opérations permettant de construire des systèmes complexes à partir de composants plus simples en fusionnant différents points de vue d'un même système ou en composant plusieurs sous-systèmes ensemble, ainsi que de décomposer une spécification complexe afin de réutiliser des composants existants et de simplifier la tâche d'implémentation. Le formalisme de spécification que nous utilisons est basé sur des spécifications modales. Intuitivement, une spécification modale est un automate doté de deux types de transitions permettant d'exprimer des comportements optionnels ou obligatoires. Raffiner une spécification modale revient à décider si les parties optionnelles devraient être supprimées ou rendues obligatoires. Cette thèse contient deux principales contributions théoriques basées sur une extension des spécifications modales appelée " spécifications à ensembles d'acceptation ". La première contribution est l'identification d'une sous-classe des spécifications à ensembles d'acceptation, appelée " spécifications à ensembles d'acceptation convexes ", qui permet de définir des opérations bien plus efficaces tout en gardant un haut niveau d'expressivité. La seconde contribution est la définition d'un nouveau formalisme, appelé " spécifications à ensembles d'acceptation marquées ", qui permet d'exprimer des propriétés d'atteignabilité. Ceci peut, par exemple, être utilisé pour s'assurer qu'un système termine ou exprimer une propriété de vivacité dans un système réactif. Les opérations usuelles sont définies sur ce nouveau formalisme et elles garantissent la préservation des propriétés d'atteignabilité. Cette thèse présente également des résultats d'ordre plus pratique. Tous les résultats théoriques sur les spécifications à ensembles d'acceptation convexes ont été prouvés en utilisant l'assistant de preuves Coq. L'outil MAccS a été développé pour implémenter les formalismes et opérations présentés dans cette thèse. Il permet de les tester aisément sur des exemples, ainsi que d'étudier leur efficacité sur des cas concrets. / Software programs are taking a more and more important place in our lives. Some of these programs, like the control systems of power plants, aircraft, or medical devices for instance, are critical: a failure or malfunction could cause loss of human lives, damages to equipments, or environmental harm. Formal methods aim at offering means to design and verify such systems in order to guarantee that they will work as expected. As time passes, these systems grow in scope and size, yielding new challenges. It becomes necessary to develop these systems in a modular fashion to be able to distribute the implementation task to engineering teams. Moreover, being able to reuse some trustworthy parts of the systems and extend them to answer new needs in functionalities is increasingly required. As a consequence, formal methods also have to evolve in order to accommodate both the design and the verification of these larger, modular systems and thus address their scalability challenge. We promote an algebraic approach for the design of correct-by-construction systems. It defines a formalism to express high-level specifications of systems and allows to incrementally refine these specifications into more concrete ones while preserving their properties, until an implementation is reached. It also defines several operations allowing to assemble complex systems from simpler components, by merging several viewpoints of a specific system or composing several subsystems together, as well as decomposing a complex specification in order to reuse existing components and ease the implementation task. The specification formalism we use is based on modal specifications. In essence, a modal specification is an automaton with two kinds of transitions allowing to express mandatory and optional behaviors. Refining a modal specification amounts to deciding whether some optional parts should be removed or made mandatory. This thesis contains two main theoretical contributions, based on an extension of modal specifications called acceptance specifications. The first contribution is the identification of a subclass of acceptance specifications, called convex acceptance specifications, which allows to define much more efficient operations while maintaining a high level of expressiveness. The second contribution is the definition of a new formalism, called marked acceptance specifications, that allows to express some reachability properties. This could be used for example to ensure that a system is terminating or to express a liveness property for a reactive system. Usual operations are defined on this new formalism and guarantee the preservation of the reachability properties as well as independent implementability. This thesis also describes some more practical results. All the theoretical results on convex acceptance specifications have been proved using the Coq proof assistant. The tool MAccS has been developed to implement the formalisms and operations presented in this thesis. It allows to test them easily on some examples, as well as run some experimentations and benchmarks.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-07-12T14:15:46Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE_JOSE_DIHEGO_DA_SILVA_OLIVEIRA_CIN_UFPE_2016.pdf: 1113539 bytes, checksum: 124effe0f62c8dd44008517c1e0045ee (MD5) / Made available in DSpace on 2017-07-12T14:15:46Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TESE_JOSE_DIHEGO_DA_SILVA_OLIVEIRA_CIN_UFPE_2016.pdf: 1113539 bytes, checksum: 124effe0f62c8dd44008517c1e0045ee (MD5) Previous issue date: 2016-03-04 / As computer systems become ubiquitous, the demand for rigorous and compositional development methods increase dramatically. In the component-based model driven development (CB-MDD) approach, complex systems (sometimes intractable by humans) are build from simple elements, called components. To achieve the CB-MDD goals towards becoming a rigorously development discipline, components and composition rules must be formalised. Moreover, as requirements continuously evolve, there must be mechanisms to refine and safely extend component-based systems. The BRIC component model formalises the CB-MDD core concepts and supports a constructive design based on composition rules that preserves behavioural properties, but do not provide support for component model evolution. In this work we propose inheritance and refinement relations for BRIC. We define a congruent semantics for this model that considers component structure and behaviour. We define refinement as a preorder relation, which is monotonic with respect to the BRIC composition rules. We enhance this component model with support for extensibility via inheritance. The proposed relations allow extension of functionality, whilst preserving service conformance, which we define by means of a convergence notion. We also establish an algebraic connection between component extensibility and refinement. As far as we are aware this is the first time componente inheritance relations are developed for a formal and sound CB-MDD approach. We also integrate the aspect-oriented paradigm into BRIC. We contribute with an approach to capture, specify and use aspects to safely evolve component-based systems. We establish that components extended by aspects preserve the proposed convergence relation that guarantees service conformance. Furthermore, we establish a connection between componente inheritance and aspects, presenting inheritance as a mechanism to define families of componentes and aspects to capture orthogonal concerns over them. The practical relevance of the proposed relations is illustrated by three case studies. One is an autonomous healthcare system, which evolve by the addition of new functionalities via inheritance and by the modularisation of its crosscutting concerns in a reusable and maintainable manner with aspects. Another case study is a bank system, whose functionalities are progressively realised and extended by refinement and inheritance, respectively. Finally, we model a P2P system extended by inheritance to reduce the network traffic. / Na medida em que os sistemas computacionais se tornam mais pervasivos, a demanda por métodos de desenvolvimento rigorosos e composicionais cresce dramaticamente. No desenvolvimento baseado em componentes (CB-MDD), sistemas complexos (muitas vezes humanamente intangíveis) são construídos a partir de elementos mais simples, chamados componentes. Para atingir os objetivos desta abordagem na direção de torná-la uma disciplina formal de desenvolvimento, componentes e regras de composição devem ser formalizados. Além disso, considerando que os requisitos de um sistema estão em constante evolução, necessitamos de mecanismos para refinar e estender de forma confiável tais sistemas. O modelo de componentes BRIC formaliza os conceitos chave da abordagem CB-MDD, além de garantir corretude por construção se baseando em regras de composição que preservam propriedades comportamentais. BRIC, porém, por não possuir relações de extensão, não suporta evolução de modelos baseados em componentes. Neste trabalho propomos relações de herança e refinamento para BRIC. Definimos uma semântica congruente que considera tanto a estrutura quanto o comportamento de componentes. Definimos refinamento como uma relação de pré-ordem, a qual é monotônica em relação as regras de composição de BRIC. Estendemos este modelo de componentes com suporte a extensibilidade via herança. As relações propostas permitem extensão de funcionalidade, ao mesmo tempo em que preservam conformidade de serviços, a qual é definida em termos de uma noção de convergência. Estabelecemos também uma conexão algébrica entre extensibilidade de componentes e refinamento. Até onde estamos cientes, este trabalho é pioneiro no desenvolvimento de noções de herança de componentes para uma abordagem CB-MDD formal e consistente. Também integramos o paradigma orientado a aspectos em BRIC. Contribuímos com uma abordagem para capturar, especificar e adotar aspectos no desenvolvimento confiável de sistemas baseados em componentes. Estabelecemos que componentes estendidos por aspectos preservam convergência, o que garante conformidade de serviços. Além disso, desenvolvemos uma conexão entre herança e aspectos, apresentando herança como um mecanismo para definir famílias de componentes e aspectos para capturar conceitos ortogonais sobre as mesmas. Ilustramos a relevância prática das relações propostas através de três estudos de caso. No primeiro, modelamos um sistema autônomo de cuidados médicos, estendido pela adição de novas funcionalidades via herança e pela modularização de conceitos transversais de forma reusável e manutenível via aspectos. Na sequência, modelamos um sistema bancário, cujas funcionalidades são progressivamente implementadas e estendidas pelo uso de herança e refinamento. Finalmente, modelamos um sistema P2P cujo tráfico é reduzido por extensão via herança.