On a subclass of the regular language class (“strongly connected” languages): definitions and corresponding canonical automata

Boris Melnikov

Abstract


In our previous publications, we considered a simplified version of the definition of omega-automata that define omega-languages compared to the classics. However, despite this “simplification”, such a definition makes it possible to specify the subclasses of the class of omega-languages that we need in a lot of problems, to describe the corresponding algorithms for equivalent transformations of the omegaautomata we have defined, etc. At the same time, we have already considered a group of questions related to omega automata and the corresponding omega computations, but which, with some reformulation, can also be attributed to ordinary nondeterministic finite automata. We have defined iterating and strongly connected omega automata; however, based on the definitions and properties of such automata discussed in previous papers, we can conclude that almost the same concepts can be applied to ordinary NFAs. In this regard, in this paper we define strongly connected automata as a subset of ordinary NFAs. Based on this concept, we define strongly connected languages, and then show their relation to the invariants available in the class of regular languages: canonical, basis, and universal finite automata. In particular, we show that for a strongly connected language and its mirror image, all 4 variants of the strong connectivity condition of the corresponding canonical automata are possible. In this paper, as well as in the proposed continuations, we shall consider subclasses of strongly connected languages, present algorithms for equivalent transformation of corresponding strongly connected automata, describe some special subclasses of the class of strongly connected languages and some properties of these subclasses. They will give the possibility to describe algorithms of equivalent transformations for the above-mentioned variant of omega-automata.

Full Text:

PDF (Russian)

References


Melnikov B., Melnikova A. Some more on omega-finite automata and omega-regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. – 2020. – Vol. 8. No. 8. – P. 1–7.

Büchi J. On a decision method in restricted second order arithmetic // In: Proceedings of International Congress on Logic, Method, and Philosophy of Science. – Stanford, Stanford University Press, 1962. – P. 425–435.

Khoussainov B., Nerode A. Automata Theory and its Applications // Progress in Computer Science and Applied Logic, Vol. 21. – Springer, Berlin, 2001.

Harary F. Теория графов // М.: Мир, 1973. Graph Theory. Addison Wesley (Boston), 1969, 274 p.

Melnikov B. 2ω-finite automata and sets of obstructions of their languages // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 1999. – Vol. 6. No. 3. – P. 565–576.

Skornyakov L. (Ed.) General Algebra. Vol. 2 // Moscow: Nauka, 1991. (in Russian)

Melnikov B. The star-height of a finite automaton and some related questions // International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 7. – P. 1–5.

Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundations of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–272.

Melnikov B., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 2. – P. 475–485.

Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 1. – P. 135–150.

Melnikov B., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // Proceedings – 5th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP-2012. – 2012. – P. 194–201.

Melnikov B., Dolgov V. Some more algorithms for Conway’s universal automaton // Acta Universitatis Sapientiae, Informatica. – 2014. – Vol. 6. No. 1. – P. 5–20.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 10. – P. 9–17.

Dolgov V., Melnikov B. The construction of a universal finite automaton. I. From the theory to the practical algorithms // Bulletin of the Voronezh state University. Series: Physics. Mathematics. – 2013. – No. 2. – P. 173–181. (in Russian)

Dolgov V., Melnikov B. The construction of a universal finite automaton. II. Examples of the work of the algorithms // Bulletin of the Voronezh state University. Series: Physics. Mathematics. – 2014. – No. 1. – P. 78–85. (in Russian)

Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata, Amsterdam University Press. – 2008. – P. 457–504.

Dedekind R. Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // Gesammelte Werke 2, Braunschweig. – 1897. – S. 103–148. (in German)

Korshunov A. On the number of monotone Boolean functions //Problems of Cybernetics. – 1981. – Vol. 38. – P. 5–108. (in Russian)

Salomaa A. Jewels of formal language theory // Maryland, USA: Computer Science Press, Inc., 1981.

Vinogradov I. (Ed.) Mathematical Encyclopedia. Vol. 2 // Moscow: Sovetskaya Encyclopedia, 1979. (in Russian)

Prohorov Yu. (Ed.) Mathematical Encyclopedic Thesaurus // Moscow:Sovetskaya Encyclopedia, 1988. (in Russian)


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162