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

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 first part of this paper, the main definitions are given and the initial phase of the required algorithm for constructing a petal automaton is considered (using the example only). This phase is associated with special transformations of the complete automaton for a given table of the binary relation #; these transformations, generally speaking, are nonequivalent, but at the same time preserving this binary relation.


Full Text:

PDF (Russian)

References


Singh Sh., Krishna K. On syntactic complexity of circular semiflower automata // Implementation and Application of Automata, CIAA 2018, Lecture Notes in Computer Science, 10977, Springer International Publishing Ag. – 2018. – P. 312–323.

Baumgärtner S., Melnikov B. Generalized nondeterministic finite automata // News of higher educational institutions. Volga region. Physical and mathematical sciences. – 2013. – No. 2 (26). – P. 64–74 (in Russian).

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

Melnikov B. Subclasses of the context-free languages class (monograph). – Moscow, Moscow State University Ed. – 1995. – 174 p. – ISBN 5-211-03448-1. (in Russian).

Melnikov B., Vakhitova A. Some more on the finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 1998. – Vol. 5. No. 3. – P. 495–505.

Alekseeva A., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33 (in Russian).

Korabelshchikova S., Melnikov B. Maximum prefix codes and subclasses of the context-free languages class // Bulletin of the Northern (Arctic) Federal University. Series: Physics. Mathematics. – Серия: Natural sciences. – 2015. – No. 1. – P. 121–129 (in Russian).

Korabelshchikova S., Melnikov B. Iterations of languages and maximum prefix codes // Bulletin of the Voronezh State University. Series: Physics. Math. – 2015. – No. 2. – P. 106–120 (in Russian).

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. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian State Social University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7. (in Russian).

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

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. On the subclass of the regular languages class (“strongly connected” languages) // 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).

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., 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., 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.

Dolgov V., Melnikov B. About algorithms of automatic construction of Waterloo-like finite automata based on complete automata // Heuristic algorithms and distributed computing. – 2014. – Vol. 1. No. 4. – P. 24– 45 (in Russian).

Dolgov V., Melnikov B. Constructing universal finite automaton. II. Examples of algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 4. – P. 78–85 (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., 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.

Dolgov V., Melnikov B., Melnikova A. Loops of the transition graph of a basic finite automaton and related questions // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2016. – No 4. – P. 95–111 (in Russian).

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

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).

Kirsten D. Distance desert automata and the star height problem // Informatique Théorique et Applications. – 2005. – Vol. 39. No. 3. – P. 455–509.

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