By extracting the basic properties common to the automata appeared in existing literatures, we develop a general formulation of automata with "weights." We define a pseudoautomaton and derive from it the well-known deterministic automaton, nondeterministic automaton, probabilistic automaton, fuzzy automaton, and so on. Moreover, several interesting automata such as /-semigroup automaton, lattice automaton, dual lattice automaton, mixed boolean automaton, semiring automaton, ring automaton and field automaton which have never appeared in any other paper before are derived.
1. Introduction
Recently some interesting automata such as fuzzy automata , maxproduct automata [4], integer-valued generalized automata have been formulated as a generalization of weU-known deterministic automata, nondeterministic automata, and probabilistic automata. The common property with these automata is that they have the "weights" of state transitions as well as initial and final distributions. Clearly probabilistic automata can be considered as sorts of these automata with "weights." For example, fuzzy automata are the automata with weights where the values in the interval [0, I] are adopted as the weights of state transition and the operations max and min are introduced. In addition, max-product automata can be formulated from fuzzy automata by replacing min by ordinary product. And by using + and X as the operations and the probabilities as the weights, probabilistic automata can be defined. Moreover, integer-valued generalized automata have integers as weights and + and X as operations.
In this paper we develop a general formulation of automata with weights by extracting the basic properties common to the existing automata and by incorporating the appropriate algebra systems with automata systems and by performing the operations of the algebra systems to the state transition functions and initial and final distribution functions of the pseudoautomata defined later. Now we shall briefly review the concept of L-fuzzy relations by Goguen [5] as a preparation. The concept of L-fuzzy relations will be found to be an important concept in defining various kinds of automata with weights in Section 3.