Petal (semi-flower) finite automata: basic definitions, examples and their relation to complete automata. Part II

Boris Melnikov

Abstract


This paper discusses (non-deterministic) finite automata of a special kind. We have not found any publications in the literature in Russian that define the title for such automata, so we propose a new name for them, i.e. “petal automata”. (In the only publication found in the Englishlanguage literature, the term “semi-flower automata” is used, apparently it is not very successful.) The study of such automata is very important for several topics discussed in our previous publications. First of all, it is a connection with algorithms for solving problems, related to various variants of the study of the equality of infinite iterations of two finite languages: in particular, to the description of algorithms for solving these problems in the form of a special type of nondeterministic finite automata (i.e., PRI and NSPRI automata). Other problems are also close to this topic, which, in principle, can also be solved by considering all subsets of the set of potential word roots of a given language: for example, it is the problem of extracting the root of some power for the given language. But a very important auxiliary purpose is to solve these problems using algorithms, less complex than exponential ones. Two more possible topics of the applications of petal automata are as follows. It is possible to apply the obtained results in auxiliary algorithms necessary for more general algorithms of state- and edge-minimization of nondeterministic finite automata. In addition, the study of petal automata can be associated with the study of the binary relation table #, since variants of such tables divide the whole set of regular languages into special equivalence classes. The possibility of using petal automata in the last topic follows from the main result of this paper, namely, from the considered description of the algorithm for constructing such a petal automaton, the table of binary relation # of which is the same as the given table (perhaps, with the only specially added right column). In the proposed second part of the paper, we directly go to to work with petal automata. We consider issues related to the algorithm for obtaining the corresponding petal automaton based on a given table #.


Full Text:

PDF (Russian)

References


Melnikov B. Petal (semi-flower) finite automata: basic definitions, examples and their relation to complete automata. Part I // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 9. – P. 1–11. (in Russian).

Melnikov B., Dolgov V. Simplified regular languages and a special equivalence relation on the class of regular languages. Part I // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 9. – P. 12–20. (in Russian).

Hashiguchi K. Regular languages of star height one // Information and Control. – 1982. – Vol. 53. No. 3. – P. 199–210.

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. Some more on the equivalent transformation of nondeterministic finite automata. Part III. The “adding” algorithm // International Journal of Open Information Technologies. – 2019. – Vol. 7. No. 12. – P. 1–4.

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 4. – P. 1–9. (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 5. – P. 1–8. (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 7. – P. 1–9. (in Russian).

Melnikov B. Description of special submonoids of the global supermonoid of the free monoid // News of higher educational institutions. Mathematics. – 2004. – No. 3. – P. 46–56. (in Russian).

Čulík II K., Fich F., Salomaa A. A homomorphic characterization of regular languages // Discrete Applied Mathematics – 1982. – Vol. 4. No. 2. – P. 149–152.

Melnikov B. Variants of finite automata, corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13. (in Russian).

Melnikov B. Variants of finite automata, corresponding to infinite iterative morphism trees. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 10. – P. 1–8. (in Russian).

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

Melnikov B., Sayfullina M. On some algorithms of equivalent transformation of nondeterministic finite automata // News of higher educational institutions. Mathematics. – 2009. – No. 4. – P. 67–72. (in Russian).

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.

Dolgov V., Melnikov B. Constructing universal finite automation. II. Examples of algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 4. – P. 78–85. (in Russian).

Melnikov B. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian Social State University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7. (in Russian).

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

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., Melnikova A. Some more on ω-finite automata and ω-regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. – 2020. – Vol. 8. No. 8. – P. 1– 7.

Melnikov B. About one subclass of the class of regular languages (“strongly connected” languages): definitions and corresponding canonical automata // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 3. – P. 1–10. (in Russian).

Melnikov B. Automata – complete invariants for strongly connected regular languages // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 6. – P. 1–10. (in Russian).

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

Melnikov B., Melnikova A. A new algorithm of constructing the basis finite automaton // Informatica (Lithuanian Academy of Sciences Ed.). – 2002. – Vol. 13. No. 3. – P. 299–310.


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162