Some more on omega-finite automata and omega-regular languages. Part I: The main definitions and properties

Boris Melnikov, Aleksandra Melnikova

Abstract


The finite and infinite iterations of finite and infinite languages arise in various problems of the formal languages theory.
For instance, we can mention their application for the description of subclasses of the context-free languages class with the decidable equivalence problem.
For infinite iterations of finite languages, we consider in this paper so-called strongly connected omega-automata and corresponding omega-regular languages.
For them, many statements are fulfilled that are not satisfied in the more general case, i.e. when we use arbitrary omega-finite automata and corresponding omega-regular languages; the omega-iterations of languages include in the class of strongly connected omega-regular languages.
The main of such properties and statements are non-existence of an omega-automaton for which there is no equivalent deterministic, and the possibility of checking the equivalence of two given omega-automata; in the general case (i.e., when we consider arbitrary omega-automata), both of these properties are not satisfied.
We also describe transferring the usual procedure of determinization to the case of omega-automata and show the correctness of this procedure in the cases we are considering.
We consider some examples, and in the second part of the paper, we shall consider the transfer of a well-known example (so called Waterloo automaton) to the case of omega-automata and omega-languages.


Full Text:

PDF

References


Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages //Informatica (Lithuanian Academy of Sciences). - 2000. - Vol. 11. No. 4. - P. 441-454.

Melnikov B., Melnikova A. Edge-minimization of non-deterministic finite automata //The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). - 2001. - Vol. 8. No. 3. - P. 469-479.

Melnikov B., Melnikova A. Extended basis finite automaton. Part I. The basic definitions //International Journal of Open Information Technologies. - 2019. - Vol. 7. No. 10. - P. 1-8. (in Russian)

Melnikov B., Melnikova A. Extended basis finite automaton. Part II. Description of auxiliary languages and some properties //International Journal of Open Information Technologies. - 2020. - Vol. 8. No. 5. - P. 1-7. (in Russian)

Dang V., Korabel'shchikova S., Melnikov B. Semigroups approximation with respect to some ad hoc predicates //Arctic Environmental Research. - 2017. - Vol. 17. No. 2. - P. 133-140.

Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language //International Journal of Open Information Technologies. - 2019. - Vol. 7. No. 3. - P. 1-6.

Khoussainov B., Nerode A. Authomata Theory and its Applications //Progress in Computer Science and Applied Logic, Vol. 21. - Springer, Berlin, 2001. %, 428 p.

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems //Fundamenta Informaticae. - 2010. - Vol. 104. No. 3. - P. 267-283.

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

Eilenberg S. Automata, Languages and Machines. Vol. A //Academic Press, N.Y., 1974.

Eilenberg S. Automata, Languages and Machines. Vol. B //Academic Press, N.Y., 1976.

Rozenberg G., Salomaa A. The Mathematical Theory of L Systems //Academic Press, N.Y., 1980.

Cohen R., Gold Y. Theory of omega-Languages. I: Characterizations of omega-Context-Free Languages //Journal of Computer and System Sciences. - 1977. - Vol. 15. - P. 169-184.

Cohen R., Gold Y. Theory of omega-Languages. II: A Study of Various Models of omega-Type Generation and Recognitions //Journal of Computer and System Sciences. - 1977. - Vol. 15. - P. 185-208.

Culik II K., Pachl J. Equivalence Problems for Mapping on Infinite Strings //Information and Control. - 1981. - Vol. 49. - P. 52-63.

Culik II K., Salomaa A. Test Sets and Cheking Words for Homomorphism Equivalence //Journal of Computer and System Sciences. - 1980. - Vol. 20. - P. 379-395.

Brosalina A., Melnikov B. Commutation in global supermonoid of free monoids //Informatica (Lithuanian Academy of Sciences). - 2000. - Vol. 11. No. 4. - P. 353-370.

Dubasova A., Melnikov B. On an extension of the context-free languages class //Programming and Computer Software (Russian Academy of Sciences). - 1995. - No. 6. - P. 46-55. (in Russian)

Melnikov B. An algorithm for checking the equality of infinite iterations of finite languages //Bulletin of Moscow University, series Computational Mathematics and Cybernetics. - 1996. - No. 4. - P. 49-54. (in Russian)

Lindenmayer A. Mathematical models for cellular interaction in development. I //Journal of Theoretical Biology. - 1968. - Vol. 18. - P. 280-298.

Lindenmayer A. Mathematical models for cellular interaction in development. II //Journal of Theoretical Biology. - 1968. - Vol. 18. - P. 299-315.

Wood D. Grammar and L Forms: an Introductions //Springer, Berlin, 1980.

Thue A. Uber unendlichen Zeichenreihen //Math.-Naturv. Klasse Skrifter udgivne af Videnskabsselskabet i Christiania. - 1906. - P. 1-22. (in German)

Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen //Math.-Naturv. Klasse Skrifter udgivne af Videnskabsselskabet i Christiania. - 1912. - P. 1-35. (in German)

Salomaa A. Jewels of Formal Language Theory //Computer Science Press, Rockville, 1981.

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

Melnikov B. On omega-languages of special billiards //Discrete Mathematics (Russian Academy of Sciences). - 2002. - No. 3. - P. 95-108. (in Russian)

Melnikov B. On omega-languages of special billiards //Discrete Mathematics and Applications. 2002. - Vol. 12. No. 5. - P. 501-514.

Melnikov B., Melnikova A. Pseudo-automata for generalized regular expressions //International Journal of Open Information Technologies. 2018. - Vol. 6. No. 1. - P. 1-8.

Harary F. Graph Theory //Addison-Wesley, Reading, 1969.

Melnikov B. The equality condition for infinite catenations of two sets of finite words //International Journal of Foundation of Computer Sciences. 1993. - Vol. 4. No. 3. - P. 267-274.

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.


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162