Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
-->

UDC 519.713.1

A.N. CHEBOTEREV,
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
ancheb@gmail.com


CONSTRUCTING A –ω-REGULAR EXPRESSION
SPECIFIED BY AN ELEMENTARY EXTENSIONS GRAPH

Abstract. In synthesis of a –ω-automaton specified in the LP language, the problem arises how to represent the set of –ω-words defined by a formula F(t) in the form of a –ω-regular expression. Construction of this representation is based on the correspondence between structural components of the formulas and –ω-regular expressions. To provide such a correspondence, two additional operations on –ω-regular sets relating to the operation of quantification in the formulas were introduced. The problem was reduced to calculating the –ω-regular expressions defined by these operations. This calculation relies on the construction of an elementary extensions graph, in which certain set of infinite paths corresponds to all –ω-words that belong to the –ω-set to be calculated. A method for constructing a –ω-regular expression specified by such a graph is proposed in the paper. This method is based on the solution of a system of linear equations over –ω-regular sets.

Keywords: : –ω-word, –ω-regular expression, prefix-closed set of –ω-words, elementary extensions graph, linear equations over –ω-regular sets.


FULL TEXT

REFERENCES

  1. Chebotarev A.N. From LP formulas of the form F(t) to –ω-regular expressions. Kibernetika i sistemnyj analiz. 2020. Vol. 56, N 5. P. 3–17.

  2. Thiemann P., Sulzmann M. From –ω-regular expressions to Buchi automata via partial derivatives. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer-Verlag, 2015. Vol. 8977. P. 287–298.

  3. Chebotarev A.N. Intersection of –ω-regular expressions. Kibernetyka ta systemnyi analiz. 2021. Vol. 57, N 5. P. 12–21.

  4. Staiger L. On ω-power languages. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer-Verlag, 1997. Vol. 1218. P. 377–394.




© 2022 Kibernetika.org. All rights reserved.