Moore machines duality. (English) Zbl 07661892
Summary: We present a simple algorithm to find the Moore machine with the minimum number of states equivalent to a given one.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press · Zbl 1086.11015 |
| [2] | Berstel, J.; Boasson, L.; Carton, O.; Fagnot, I., Minimization of automata, (Automata: from Mathematics to Applications (2010), European Mathematical Society) |
| [3] | (Berthé, V.; Ferenczi, S.; Mauduit, C.; Siegel, A., Substitutions in Dynamics, Arithmetics and Combinatorics. Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, vol. 1794 (2002), Springer), 321-342 · Zbl 1014.11015 |
| [4] | (Bonchi, F.; Bonsangue, M. M.; Rutten, J. J.M. M.; Silva, A.; Constable, R. L.; Silva, A., Kozen Festschrift. Kozen Festschrift, LNCS, vol. 7230 (2012), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 12-23 |
| [5] | Brzozowski, J. A., Canonical regular expressions and minimal state graphs for definite events, (Proc. Sympos. Math. Theory of Automata. Proc. Sympos. Math. Theory of Automata, New York, 1962 (1962), Polytechnic Press of Polytechnic Inst. of Brooklyn: Polytechnic Press of Polytechnic Inst. of Brooklyn Brooklyn, NY), 529-561, MR 0175719 · Zbl 0116.33605 |
| [6] | Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. Fr., 108, 401-419 (1980) · Zbl 0472.10035 |
| [7] | Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Applications to Automata (1969), Addison Wesley · Zbl 0196.01701 |
| [8] | Moore, E. F., Gedanken-Experiments on Sequential Machines, Automata Studies, Annals of Mathematical Studies, vol. 34, 129-153 (1956), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0074.11204 |
| [9] | Peyrière, J., Moore machine duality |
| [10] | Queffélec, Substitution Dynamical Systems - Spectral Analysis, Lecture Notes in Mathematics, vol. 1294 (1987), 2nd ed., (2010) · Zbl 0642.28013 |
| [11] | Yao, J.-Y., Some properties of Ising automata, Theor. Comput. Sci., 314, 251-279 (2004) · Zbl 1070.68079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
