Constructing a \(-\omega\)-regular expression specified by a graph of elementary extensions. (English. Ukrainian original) Zbl 07630497
Cybern. Syst. Anal. 58, No. 2, 165-170 (2022); translation from Kibern. Sist. Anal. 58, No. 2, 3-9 (2022).
Summary: In synthesis of a \(\Sigma \)-automaton specified in the LP language, the problem arises how to represent the set of \(- \omega \)-words defined by a formula \(F (t)\) in the form of a \( -\omega \)-regular expression. Constructing this representation is based on the correspondence between structural components of formulas and \( -\omega \)-regular expressions. To provide such a correspondence, two additional operations on \( -\omega \)-regular sets relating to the operation of quantification in the formulas are introduced. The problem is reduced to calculating the \( -\omega \)-regular expressions defined by these operations. This calculation relies on the construction of a graph of elementary extensions, in which certain set of infinite paths corresponds to all \(- \omega \)-words that belong to the \( -\omega \)-set to be calculated. A method for constructing a \( -\omega \)-regular expression specified by such a graph is proposed in the paper. This method is based on solving a system of linear equations over \( -\omega \)-regular sets.
Keywords:
\( \omega \)-word; \( -\omega \)-regular expression; prefix-closed set of \( -\omega \)-words; graph of elementary extensions; linear equations over \( -\omega \)-regular setsReferences:
| [1] | A. N. Chebotarev, “From LP formulas of the form F (t ) to -ω-regular expressions,” Cybern. Syst. Analysis, Vol. 56, No. 5, 689-700 (2020). https://doi.org/doi:10.1007/s10559-020-00286-x. · Zbl 1477.68149 |
| [2] | P. Thiemann and M. Sulzmann, “From ω-regular expressions to Buchi 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. https://doi.org/doi:10.1007/978-3-319-15579-1_22. · Zbl 1451.68162 |
| [3] | A. N. Chebotarev, “Intersection of -ω-regular expressions,” Cybern. Syst. Analysis, Vol. 57, No. 5, 676-684 (2021). https://doi.org/doi:10.1007/s10559-021-00393-3. · Zbl 1484.68078 |
| [4] | 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, Berlin-Heidelberg, Springer (1997), pp. 377-394. https://doi.org/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.
