Thesis (Ph. D.)--University of Hong Kong, 2008. / Also available in print.

Thesis (M.S.)--Rochester Institute of Technology, 2008. / Typescript. Includes bibliographical references (leaves 119-137).

Thesis (PhD)--Montana State University--Bozeman, 2008. / Typescript. Chairperson, Graduate Committee: Philip S. Stewart. Includes bibliographical references.

We present PTIME language-preserving techniques for the reduction of non-deterministic tree automata, both for the case of finite trees and for infinite trees. Our techniques are based on new transition removing and state merging results, which rely on binary relations that compare the downward and upward behaviours of states in the automaton. We use downward/upward simulation preorders and the more general but EXPTIME-complete trace inclusion relations, for which we introduce good under-approximations computable in polynomial time. We provide a complete picture of combinations of downward and upward simulation/trace inclusions which can be used in our reduction techniques. We define an algorithm that puts together all the reduction results found for finite trees, and implemented it under the name minotaut, a tool built on top of the well-known tree automata library libvata. We tested minotaut on large collections of automata from program verification provenience, as well as on different classes of randomly generated automata. Our algorithm yields substantially smaller and sparser automata than all previously known reduction techniques, and it is still fast enough to handle large instances. Taking reduction of automata on finite trees one step further, we then introduce saturation, a technique that consists of adding new transitions to an automaton while preserving its language. We implemented this technique on minotaut and we show how it can make subsequent state-merge and transition-removal operations more effective. Thus we obtain a PTIME algorithm that reduces the number of states of tree automata even more than before. Additionally, we explore how minotaut alone can play an important role when performing hard operations like complementation, allowing to obtain smaller complement automata and at lower computation times overall. We then show how saturation can extend this contribution even further. An overview of the tool, highlighting some of its implementation features, is presented as well.

No description available.

We consider the problem of decontaminating a network where all nodes are infected by a virus. The decontamination strategy is performed using a Cellular Automata (CA) model in which each node of the network is represented by the automata cell and thus, the network host status is also mapped to the CA state (contaminated, decontaminating, decontaminated). All hosts are assumed to be initially contaminated and the status of each cell is synchronously updated according to a set of local rules, based on the state of its neighbourhood. Our goal is to find the set of local rules that will accomplish the decontamination in an optimal way. The metrics used to define optimality is the minimization of three metrics: the maximum number of decontaminating cells at each step, the required value of the immunity time of each cell and the number of steps to complete the sanitization algorithm. In our research, we explore the designing of these local decontamination rules by refining the concept of the neighbourhood radius of CA with the addition of two new dimensions: Visibility Hop and Contamination Distance. Additionally, a research tool that help us manage our study have been developed.

We review the characterization of communicating finite-state machines whose behaviors have universally or existentially bounded channels. These results rely on the theory of Mazurkiewicz traces. We investigate the question whether channel bound conditions are decidable for a given communicating finite-state machine.

The successful verification of the behaviour of an Autonomous driving (AD) vehicle is fundamental for the commercialization of this new technology. Formal verification can be used to exhaustively verify the correctness of a system, but it requires a formal model to do so. An exact mathematical definition of the model description of the system is required. Manually defining a model is daunting, error-prone, and intractable for large systems. Automata learning is a branch of Machine learning (ML) that automatically creates a formal model by dynamically interacting with the system. In prior research, automata learning algorithms have been shown to learn a formal model from AD software implemented in MATLAB. However, practical challenges were highlighted in addressing the state-space explosion problem and in obtaining suitable abstractions to deal with large systems. To obtain valuable insights to scale up automata learning for industrial use, this thesis investigates the topic of automatically learning an extended finite automata formalism, called register automata. The SL* algorithm, an extension of the L* algorithm, is used to learn a register automata model of AD software from MATLAB code. The new algorithm creates a register automaton that manages to deal with the data dependencies intrinsically created from the case study between the input variables. Some approximations to the original model were made to obtain the desired solution. The obtained results are presented, from establishing the learning interface, validation of the interface, and from learning the case study. Evidence has been shown that similar problems to those highlighted for DFA learning are encountered. Future works have been discussed to address the same topic and to improve the proposed methodology. / Den framgångsrika verifieringen av beteendet hos ett autonomt körande fordon är grundläggande för kommersialiseringen av denna innovativa teknik. Formella metoder kan förutses som den sista tekniken för att uppnå detta mål. Den exakta matematiska definitionen av modellbeskrivningen för systemet behövs. Tidigare verk kunde inte skapa en metod för att automatiskt beskriva beteendemodellen för SUL. Nuvarande Lateral State Manager varierar komplexiteten som förhindrade användningen av ramverk som LearnLib eller den normala L * -algoritmen. Den stora mängden ingångar och den exponentiella tillväxten av den observerbara tabellen är några av orsakerna som gör att standardalgoritmerna misslyckas. Tidigare löstes problemet delvis och introducerade viss abstraktion till SUL. I denna avhandling föreslår vi en metod baserad på en innovativ algoritm: SL *. Den är utvecklad tack vare förlängningen av LearnLib-ramverket RALib. Den nya algoritmen skapar en registerautomat som klarar av att hantera databeroendet som skapats ur studiens fall. För att få en lösning inom acceptabel tid gjorde vi en ungefärlig tillnärmning till den ursprungliga modellen som vi tror inte påverkar det slutliga resultatet och skapar en modell som kan användas för de ändamål den var tänkt för. / La corretta verifica del comportamento di un veicolo a guida autonoma è fondamentale per la commercializzazione di questa tecnologia. Diversi metodi formali possono essere previsti come una possibile tecnica al fine di raggiungere parte di questo vasto obiettivo. Al fine di utilizzare tali metodi è necessaria l’esatta descrizione matematica del modello comportamentale del sistema. Precedenti studi non sono stati in grado di creare automaticamente un metodo per descrivere il comportamento del sistema sotto esame. Il Lateral State Manager presenta varie complessità che hanno impedito l’uso di framework come LearnLib o dell’algoritmo L_. La grande quantità di input e la crescita esponenziale della tabella delle osservazioni sono alcune delle principali cause che portano i comuni algoritmi al fallimento. In precedenza il problema è stato parzialmente risolto introducendo alcune astrazioni al caso di studio. In questa dissertazione proponiamo un metodo basato su un algoritmo innovativo: SL *. Lo stesso è sviluppato grazie all’estensione del framework LearnLib, chiamato RALib. Il nuovo algoritmo crea degli automi basati sui registri che riescono a gestire la dipendenza tra i dati intrinsecamente creati dal caso di studio. Per ottenere una soluzione in tempi accettabili si sono rese necessarie alcune approssimazioni del modello originale che riteniamo non influiscano sul risultato finale, creando un modello che possa essere utilizzato per gli scopi per cui è stato pensato.

In the field of formal verification of real-time systems, major developments have been recorded in the last fifteen years. It is about logics, automata, process algebra, programming languages, etc. From the beginning, a formalism has played an important role: timed automata and their natural extension,hybrid automata. Those models allow the definition of real-time constraints using real-valued clocks, or more generally analog variables whose evolution is governed by differential equations. They generalize finite automata in that their semantics defines timed words where each symbol is associated with an occurrence timestamp. The decidability and algorithmic analysis of timed and hybrid automata have been intensively studied in the literature. The central result for timed automata is that they are positively decidable. This is not the case for hybrid automata, but semi-algorithmic methods are known when the dynamics is relatively simple, namely a linear relation between the derivatives of the variables. With the increasing complexity of nowadays systems, those models are however limited in their classical semantics, for modelling realistic implementations or dynamical systems. In this thesis, we study the algorithmics of complex semantics for timed and hybrid automata. On the one hand, we propose implementable semantics for timed automata and we study their computational properties: by contrast with other works, we identify a semantics that is implementable and that has decidable properties. On the other hand, we give new algorithmic approaches to the analysis of hybrid automata whose dynamics is given by an affine function of its variables.

In this dissertation we study groups of automorphisms of rooted trees arising from the transformations of the boundaries of these trees. The boundary of every regular rooted tree can be endowed with various algebraic structures. The transformations of these algebraic structures under certain conditions induce endomorphisms or automorphisms of the tree itself that can be described using the language of Mealy automata. This connection can be used to study boundarytransformations using the propertiesof the induced endomorphisms, or vice versa. We concentrate on two ways to interpret the boundary of the rooted d-regular tree. In the first approach discussed in detail in Chapter 3 we treat it as the ring Zd of d-adic integers. This is achieved by naturally identifying the nth level of the rooted d-ary tree with the ring Z/(dnZ). Under this interpretation we study transformations of Zd induced by polynomials in Z[x]. We show that they always induce endomorphisms of the tree, completely describe these endomorphisms using the language of automata and show that all of their sections are again induced by polynomials in Z[x] of the same degree. In the case of permutational polynomials acting on Zd by bijections the induced endomorphisms are automorphisms of the tree. For d = 2 such polynomials were completely characterized by Rivest in [Riv01]. As our main application we utilize the result of Rivest to derive the conditions on the coefficients of a permutational polynomial f(x) ∈ Z[x] that are necessary and sufficient for f to induce a level transitive automorphism of the binary tree, which is equivalent to the ergodicity of the action of f(x) on Z2 with respect to the normalized Haar measure. Such polynomials have applications in cryptography and are used in certain generators of random numbers. In the second approach, to be discussed in Chapter 4, we treat the boundary of the rooted binary tree as the ring (Z/2Z)[[t]] of formal power series over Z/2Z. This view allowed us to completely describe the structure of a certain group generated by a 4-state 2-letter bireversible automaton. Namely, we show that it is isomorphic to the lamplighter group (Z/2Z)2 ≀ Z of rank two. We show that the action of the generators of this group on the boundary of the tree can be induced by affine transformations of (Z/2Z)[[t]]. To our best knowledge, this is the first realization of the rank 2 lamplighter group by a bireversible automaton.