UDC 519.713.1
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 ancheb@gmail.com
|
|
CONSTRUCTING THE MAXIMUM PREFIX-CLOSED SUBSET FOR A SET
OF — ω - WORDS DEFINED BY A — ω - REGULAR EXPRESSION
Abstract. We present a method for 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.
We associate every vertex of this graph with a linear equation over sets of — ω - words.
Thus, the graph of elementary extensions determines a system of linear equations.
As a result of its solution, 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, i.e., the vertices
from which constructing the graph starts, is the maximum prefix-closed subset of the given set R.
We propose a method for constructing such a graph, called the method of incomplete intersections,
and propose how to solve the system of equations determined by the graph of elementary extensions.
Keywords: — ω - word, — ω - regular expression,
prefix-closed set of — ω - words, graph of elementary extensions,
linear equations over — ω - regular sets.
full text
REFERENCES
- Chebotarev A.N. Synthesis of automata specified in the logical languages LP and LF. Kibernetika i sistemnyj analiz. 2018. Vol. 54, N 4. P. 16–31. URL: http://www.kibernetika.org/volumes/2018/numbers/04 .
- Thiemann P., Sulzmann M. From -regular expressions to B?chi automata via partial derivatives. In: Language and Automata Theory and Applications. LATA 2015. Dediu A.H., Formenti E., MartЗn-Vide C., Truthe B. (Eds). Lecture Notes in Computer Science. Cham: Springer, 2015. Vol. 8977. P. 287–298. https://drops.dagstuhl.de/opus/volltexte/2016.
- Chebotaryov A.M. Construction of a w-regular expression given by a graph of elementary continuations. Kibernetyka ta systemnyi analiz. 2022. Vol. 58, N 2. P. 3–9.
- Thomas W. Star-free regular sets of -sequences. Information and Control. 1979. Vol. 42, Iss. 2. P. 148–156.
- Diekert V., Gastin P. First-order definable languages. In: Logic and Automata: History and Perspectives. Flum J., Grdel E., Wilke T. (Eds.). Amsterdam University Press, 2007. P. 261–306.
- Pin J.-E., Perrin D. Infinite words: Automata, semigroups, logic and games. Pure and Applied Mathematics Series. Vol. 141. Amsterdam: Academic Press, 2004. 550 p.
- Chebotarev A.N. Intersection of -regular expressions. Cybernetics and Systems Analysis. Vol. 57, N 5. P. 676–684 (2021). https://doi.org/10.1007/s10559-021-00393-3.
- Calbrix H., Nivat M., Podelsky A. Ultimately periodic words of rational -languages. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer, 1994. Vol. 802. P. 554–566.
- Angluin D., Fisman D. Learning regular omega languages. Theor. Comput. Sci. 2016. Vol. 650. P. 57–72. https://doi.org/10.1016/j.tcs.2016.07.031.
- Staiger L. On -power languages. in: New Trends in Formal Languages. Paun G., Salomaa A. (Eds.). Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer, 1997. Vol. 1218. P. 377–394. https://doi.org/10.1007/3-540-62844-4_27.
