×

Constructing the maximum prefix-closed subset for a set of \(-\omega \)-words defined by a \(-\omega \)-regular expression. (English. Ukrainian original) Zbl 07806783

Cybern. Syst. Anal. 59, No. 6, 880-889 (2023); translation from Kibern. Sist. Anal. 59, No. 6, 19-29 (2023).
Summary: In this paper, we present a method of constructing the maximum prefix-closed subset of a set of \( -\omega \)-words \(R\) defined by a \(- \omega \)-regular expression. This method is based on constructing a labeled graph called a graph of elementary extensions whose vertices are some \(- \omega \)-regular subsets of the set \(R\). With every graph vertex, we associate a linear equation over sets of \( -\omega \)-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 \( -\omega \)-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.

MSC:

68Qxx Theory of computing
03Dxx Computability and recursion theory
03Bxx General logic
Full Text: DOI

References:

[1] Chebotarev, AN, Synthesis of ω-automata specified in the first order logical languages LP and LF, Cybern. Syst. Analysis, 54, 4, 527-540 (2018) · Zbl 1400.68122 · doi:10.1007/s10559-018-0054-8
[2] P. Thiemann and M. Sulzmann, “From ω-regular expressions to Büchi automata via partial derivatives,” in: A. H. Dediu, E. Formenti, C. Martín-Vide, and B. Truthe (eds.), Language and Automata Theory and Applications, LATA 2015, Lecture Notes in Computer Science, Vol. 8977, Springer, Cham (2015), pp. 287-298. doi:10.1007/978-3-319-15579-1_22. · Zbl 1451.68162
[3] C. Löding, A. Tollkötter, “Transformations between regular expressions and ω-automata,” in: P. Faliszewski, A. Muscholl and R. Niedermeier (eds.), Leibniz International Proceedings in Informatics (LIPIcs), Proc. 41th Intern. Symp. on Mathematical Foundation of Computer Science (MFCS 2016) (Krakow, Poland, Aug 22-26, 2016), Vol. 58, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016), pp. 88:1-88:13. doi:10.4230/LIPIcs.MFCS.2016.88. · Zbl 1398.68319
[4] Chebotarev, AN, Constructing a - ω-regular expression specified by a graph of elementary extensions, Cybern. Syst. Analysis, 58, 2, 165-170 (2022) · Zbl 07630497 · doi:10.1007/s10559-022-00447-0
[5] Thomas, W., Star-free regular sets of ω-sequences, Inf. Control., 42, 2, 148-156 (1979) · Zbl 0411.03031 · doi:10.1016/S0019-9958(79)90629-6
[6] V. Diekert and P. Gastin, “First-order definable languages,” in: J. Flum, E. Grädel, and T. Wilke (eds.), Logic and Automata: History and Perspectives, Amsterdam University Press (2007), pp. 261-306. · Zbl 1234.03024
[7] Perrin, D.; Pin, J-E, Infinite Words: Automata, Semigroups, Logic and Games, Pure and Applied Mathematics Series (2004), Amsterdam: Elsevier, Amsterdam · Zbl 1094.68052
[8] Chebotarev, AN, Intersection of ω-regular expressions, Cybern. Syst. Analysis, 57, 5, 676-684 (2021) · Zbl 1484.68078 · doi:10.1007/s10559-021-00393-3
[9] Calbrix, H.; Nivat, M.; Podelski, A.; Main, MG; Melton, AC; Mislove, MW; Schmidt, D.; Brookes, SD, Ultimately periodic words of rational ω-languages, MFPS 1993, 554-566 (1994), Heidelberg: Springer, Heidelberg · Zbl 1509.68128
[10] Angluin, D.; Fisman, D., Learning regular omega languages, Theor. Comput. Sci., 650, 57-72 (2016) · Zbl 1362.68118 · doi:10.1016/j.tcs.2016.07.031
[11] L. Staiger, “On ω-power languages,” in: G. Păun and A. Salomaa (eds.), New Trends in Formal Languages, Lecture Notes in Computer Science, Vol. 1218, Springer, Berlin-Heidelberg, (1997), pp. 377-394. doi:10.1007/3-540-62844-4_27.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.