An Improved Construction of Büchi Automata for Scientific Applications

Abstract

Omega automata or infinite words automata is a finite machine that works on words or strings of infinite length. There is no acceptance condition as we have for NFA or DFA because of the words or strings of infinite length. Omega automata can be classified into five categories based on acceptance criteria: Büchi, Co-Büchi, Muller, Rabin, and Streett automata. All of these listed omega automata have equal power but different acceptance conditions. Omega automata play an essential part in verifying and synthesizing reactive systems. Omega automata is characterized by two aspects acceptance condition and determinism. This thesis investigates the various classes of omega automata and their applications by implementing multiple algorithms and models. The main objective is to generate an algorithm for transforming omega regular expression to Büchi automata. This dissertation is dedicated to designing and expanding an algorithm that converts an omega regular expression to its corresponding omega automata using a minimal approach. The proposed algorithm improved the traditional canonical derivatives approach and introduced the canonical factors reducing the no. of states in the resultant Büchi automaton. Ilie & Yu’s approach for generating the Büchi automaton from -regular expressions was also revised. Additionally, we employed the Büchi automaton model to illustrate the stages of cancer progression. Furthermore, this thesis proposes a model that elucidates the process of tumor formation by focusing on the activation/deactivation of the tumor suppressor gene as a result of a mutation in the DNA nucleotide sequence, employing Büchi automata. The model comprehensively explains the DNA mutation process and the origin of mutated cells, which are subsequently followed by cellular proliferation. We have also applied the concept of a Quantum Support Vector machine on the Breast Cancer Wisconsin Data using Pennylane Default Simulator, Quantum Amazon Simulator State Vector, and Quantum Amazon Simulator Density Matrix. A comparative study of amplitude encoding, angle encoding, Z-Feature Map, ZZ-Feature Map, and poly feature map was conducted.