Print Email Facebook Twitter Translating Automata: Comparing Automata Based on Intrinsic Characteristics Title Translating Automata: Comparing Automata Based on Intrinsic Characteristics Author Houtman, Marco (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Verwer, S.E. (mentor) Tax, D.M.J. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science Date 2022-12-19 Abstract Established research that is done on finding similarities between two finite automata, or finite state machines, is based on matching symbols that are shared between the two automata. In our research, we define a scenario in which the shared alphabet is either partially or completely obscured due to translations. We emulate a scenario where 2 probabilistic deterministic finite automata (PDFA) are created based on the same process, but with different definitions for each step of the process. We introduce three methods that make use of different properties in the automata to establish a translation between the two PDFA that have mismatched alphabets. The first two methods: Total frequency distribution, and depth frequency distribution match symbols based on their relative similarities. Our third method, state frequency comparison, calculates a similarity between two states based on their inherent structure and matches symbol translations based on the established state similarities. In our results we show that when comparing automata to itself where a number of symbols are translated, all three methods score high on accuracy, returning similarity scores over 80% when 50% of the symbols are translated. The addition of random traces reduces the similarity scores of all three methods, indicating that the robustness of the methods can be improved. In a set of 90 comparisons, 7 comparisons were chosen as the most similar automata pairs. Each of the proposed methods manages to determine 5 of the most similar automata within their top 10 approximations. Finally, a number of clusterings of 10 automata were created with help of a relative similarity table containing 100 comparisons. For one of the datasets the method state frequency comparison manages to create a similarity table that generates clusters that are identical to the original clusters for cluster sizes 2,3 and 4, returning a rand index of 0.88 for cluster size 5. Subject Finite AutomatonAutomaton ComparisonPDFA To reference this document use: http://resolver.tudelft.nl/uuid:a64b3239-6ad8-4fea-aec9-346d0da18d13 Part of collection Student theses Document type master thesis Rights © 2022 Marco Houtman Files PDF Translating_Automata_Comp ... istics.pdf 1.78 MB Close viewer /islandora/object/uuid:a64b3239-6ad8-4fea-aec9-346d0da18d13/datastream/OBJ/view