Exploring the Connections of Finite Group Automata, Group Machines and Group Machine Recognizer: Analyzing Their Characteristics
G. Sathiyasorubini, Venkatesan R. · Mathematics and Statistics · 2024
This paper presents a comprehensive examination of the underlying structures and behaviours of finite group automata and group machines, delving into their intricate relationships and properties. Researchers have developed a comprehensive structure for finite group automata applicable to any finite group. Their work utilizes state complexity (SC) and accepting state complexity (ASC) as key metrics. They have also computed syntactic and quotient complexities (SNC and QC) specifically for cyclic groups. While the primary emphasis lies on cyclic groups, their versatile methodology establishes a foundation for broadening these complexity analyses to encompass other categories of finite groups. Building upon existing research on finite group automata, this study investigates the structures of group machines, group machine recognizers, and their properties, including strong connectivity, cyclicality, perfection, bideterminism, and permutation behaviours. Our analysis reveals the interconnected nature of group machines and group machine recognizers, shedding light on their distinct characteristics. A key finding of this research is that all group machines are finite group automata, although the converse is not always true. By differentiating these structures based on their properties, we can effectively handle machines according to their characteristics. This study contributes to the advancement of research in this field by providing a thorough understanding of the fundamental structures and behaviours of finite group automata and group machines, ultimately enriching the theoretical foundations of computational models.