Waterloo-like finite automata and algorithms for their automatic construction

Boris Melnikov, Elena Melnikova


In the problems of minimization of nondeterministic finite automata, there may be situations, when a covering set of blocks defines an automaton, which is not equivalent to the original one. For the first time, such an example was obtained in 1970 by Kameda and Weiner, and according to their paper, was given the name Waterloo. The existence of such constructions ("walibad" in our terminology, from "Waterloo-like badness") greatly complicates the description of practical algorithms
for the state minimization of nondeterministic finite automata. Hence the problems of the search and description of such constructions arouse, and, where possible, it should be done before applying the said algorithms of minimization.
In this paper, we propose an example of algorithm for the transformation of so-called complete automaton given by a table of binary relation #. At the same time, we know that for this table for the binary relation #, there exists some corresponding nondeterministic automaton having Waterloo-like badness. The proposed transformation, which is not equivalent, is the serial removal of a state and combining a pair of states. It gives the opportunity to build on the basis of the given relation # some automaton which also has the walibad-property. And, generally speaking, the obtained automaton is different from the known in advance. We emphasize, that in the process of building we used only relation #, and did not use automaton known in advance.

Full Text:



Melnikov B. The complete finite automaton. International Journal of Open Information Technologies. 2017, vol. 5, no. 10, pp. 9-17.

Jiang T. and Ravikumar B. Minimal NFA problems are hard. SIAM J. Comput. 1993, vol. 22, no. 6, pp. 1117-1141.

Melnikov B. Once more about the state-minimization of the nondeterministic finite automata. The Korean Journal of Computational and Applied Mathematics. 2000, vol. 7, no. 3, pp. 655-662.

Polak L. Minimalizations of NFA using the universal automaton. Int. J. Found. Comput. Sci. 2005, vol. 16, no. 5, pp. 999-1010.

Melnikov B., Radionov A., Moseev A. and Melnikova E. Some specific heuristics for situation clustering problems. Proceedings of the 1st International Conference on Software and Data Technologies, ICSOFT-2006. Setubal, Portugal. 2006, pp. 272-279.

Geldenhuys J., van der Merwe B. and van Zijl L. Reducing nondeterministic finite automata with SAT solvers. Springer. Finite-State Methods and Natural Language Processing. Lecture Notes in Computer Science. 2010, vol. 6062, pp. 81-92.

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

Yo-Sub Han. State elimination heuristics for short regular expressions. Fundamenta Informaticae. 2013, vol. 128, pp. 445-462.

Krivolapova A., Melnikova E. and Sofonova N. Nekotoryye vspomogatel'nyye algoritmy dlya postroyeniya Waterloo-podobnykh avtomatov [Some auxiliary algorithms for construction of Waterloo-like automata]. Vestnik of Voronezh State University. Series: System analysis and information technologies. 2016, no. 4, pp. 20-28. (in Russian)

Gera R., Hedetniemi S., and Larson C., editors. Graph Theory: Favorite Conjectures and Open Problems - 1. Springer, 2016, 291 p.

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae. 2010, vol. 104, no. 3. pp. 267-283.

Melnikov B. and Zubova M. Postroenie avtomata COM na osnove bazisnogo avtomata [Construction of automaton COM on the base of the basis automaton]. Vektor Nauki of Togliatti State University, 2010, no. 4, pp. 30-32. (in Russian)

Dolgov V. and Melnikov B. Postroenie universalnogo konechnogo avtomata. I. Ot teorii k prakticheskim algoritmam [Construction of the universal finite automaton. I. From the theory to the practical algorithms]. Vestnik of Voronezh State University. Series: Physics. Mathematics, 2013, no. 2, pp. 173-181. (in Russian)

Dolgov V. and Melnikov B. Postroyeniye universal'nogo konechnogo avtomata. II. Primery raboty algoritmov [Construction of universal finite automaton. II. Examples of work of algorithms]. Vestnik of Voronezh State University. Series: Physics. Mathematics, 2014, no. 1, pp. 78-85. (in Russian)

Melnikov B. and Dolgov V. Some more algorithms for Conway's universal automaton. Acta Univ. Sapientiae, Informatica. 2014, vol. 6, no. 1, pp. 5-20.

Melnikov B. and Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language. The Korean Journal of Com. and Applied Mathematics. 2002, vol. 9, no. 2., pp. 475-485.

Kameda T. and Weiner P. On the state minimization of nondeterministic finite automata. IEEE Trans. on Comp. 1970, vol. C-19, no. 7, pp. 617-627.

Baumgartner S. and Melnikov B. Multievristicheskiy podkhod k probleme zvyozdno-vysotnoy minimizacii nedeterminirovannykh konechnykh avtomatov [Multiheuristic approach to the problem of star-height minimization of nondeterministic finite automata]. Vestnik of Voronezh State University. Series: System analysis and information technologies. 2010, no. 1, pp. 5-7. (in Russian)

Melnikov B., Pivneva S., Melnikova E. and Rudnitskiy V. Parallelnaya realizatsiya zadach diskretnoy optimizatsii na osnove multievristicheskogo podkhoda [The parallel implementation of the optimization problems on the base of multiheuristic approach]. Samara, ASGARD Ed., 2017. 70 p. (in Russian)

Lombardy S. and Sakarovitch J. The Universal Automaton. in: Logic and Automata, Texts in Logic and Games Amsterdam Univ. Press. 2008, vol. 2, pp. 457-504.

Melnikov B., Tsyganov A. and Bulychov O. A multi-heuristic algorithmic skeleton for hard combinatorial optimization problems. Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization, CSO. Sanya, Hainan. 2009, pp. 33-36.

Melnikov B., Pivneva S. and Rogova O. Reprezentativnost' sluchayno sgenerirovannykh nedeterminirovannykh konechnykh avtomatov s tochki zreniya sootvetstvuyushchikh bazisnykh avtomatov [Representation of randomly generated nondeterministic finite automata from the view of the basis automata]. Stochastic Optimization in Informatics, 2010, vol. 6, no. 1-1, pp. 74-82. (in Russian)


  • There are currently no refbacks.

Abava   Servletsuite

ISSN: 2307-8162