Constructing the Maximum Prefix-Closed Subset for a Set of –ω-Words Defined by a –ω-Regular Expression

• Published in: Cybernetics and systems analysis 2023-11, Vol.59 (6), p.880-889
• Main Author: Chebotarev, A. N.
• Format: Article
• Language: English
• Subjects: Apexes; Artificial Intelligence; Control; Graph theory; Linear equations; Mathematical analysis; Mathematics; Mathematics and Statistics; Processor Architectures; Software Engineering/Programming and Operating Systems; Systems Theory
• ISSN: 1060-0396; 1573-8337
• DOI: 10.1007/s10559-023-00623-w

In this paper, we present a method of constructing the maximum prefix-closed subset of a set of – ω -words R defined by a – ω -regular expression. This method is based on constructing a labeled graph called a graph of elementary extensions whose vertices are some – ω -regular subsets of the set R. With every graph vertex, we associate a linear equation over sets of – ω -words. Thus, the graph of elementary extensions determines a system of linear equations. As a result of solving this system of equations, for each vertex of the graph, we obtain the maximum prefix-closed with respect to R subset of the set of – ω -words corresponding to this vertex. The union of such subsets that correspond to all initial vertices of the graph, that is, the vertices constructing the graph starts with, is a maximum prefix-closed subset of the given set R . A method of constructing such a graph is proposed, which we called a method of incomplete intersections. We also present a method to solve the system of equations determined by the graph of elementary extensions.