Equivalence, reduction and minimization of finite automata over semirings. (English) Zbl 0737.68063
A new theory of finite automata over semi-rings is proposed. A unified approach to equivalence, reduction and minimization is sketched. Criteria are obtained for computability of the behaviour matrix, equivalence of states, equivalence of automata, reduction of states, finding reduced and minimal form. The relationship with Noetherian property in the category of semi-modules clarified the exposé. Deterministic, nondeterministic, stochastic and fuzzy automata are included in this unified scheme.
Reviewer: V.Topencharov (Sofia)
MSC:
| 68Q70 | Algebraic theory of languages and automata |
References:
| [1] | Budach, L.; Hoehnke, H.-J., Automaten und Funktoren (1975), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0363.18006 |
| [2] | Carlyle, J. W., Reduced forms for stochastic sequential machines, J. Mat. Anal. Appl., 7, 2, 167-175 (1963) · Zbl 0281.94038 |
| [3] | Denning, P.; Dennis, J.; Qualitz, J., Machines, Languages and Computation (1978), Prentice-Hall: Prentice-Hall N.J · Zbl 0492.68003 |
| [4] | Dubois, D.; Prade, H., Fuzzy sets and systems: Theory and applications, (Mathematics and Science in Engineering, Vol. 144 (1980), Academic Press: Academic Press London) · Zbl 0605.03021 |
| [5] | Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
| [6] | Garey, M.; Johnson, D., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [7] | Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer: Springer Berlin · Zbl 0582.68002 |
| [8] | MacLane, S., Categories for the Working Mathematicians (1971), Springer: Springer New York · Zbl 0232.18001 |
| [9] | MacLane, S.; Birkhoff, G., Algebra (1979), Macmillan: Macmillan New York · Zbl 0153.32401 |
| [10] | Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York · Zbl 0234.94055 |
| [11] | Peeva, K., On algebraic structures for matrices, relations and graphs over a semiring, Mat. Bilten, 7-8, 36-48 (1983/1984) · Zbl 0605.15012 |
| [12] | Peeva, K., Systems of linear equations over a bounded chain, Acta Cybernet., 7, 2, 195-202 (1985) · Zbl 0584.68074 |
| [13] | Peeva, K., Behaviour, reduction and minimization of finite \(L\)-automata, Fuzzy Sets and Systems, 28, 171-181 (1988) · Zbl 0663.68069 |
| [14] | Santos, E. S., On reduction of maximin machines, J. Math. Anal. Appl., 40, 1, 60-78 (1972) · Zbl 0245.94041 |
| [15] | Santos, E. S.; Wee, W. G., General formulation of sequential machines, Inform. and Control, 12, 1, 5-10 (1968) · Zbl 0162.02501 |
| [16] | Starke, P., Abstract Automata (1972), North-Holland: North-Holland Amsterdam · Zbl 0225.94035 |
| [17] | Topencharov, V.; Peeva, K., Equivalence, reduction and minimization of finite fuzzy automata, J. Math. Anal. Appl., 84, 270-281 (1981) · Zbl 0477.68051 |
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.
