The principal goal of this paper is to bring the two approaches to the empirical logic of automata in a coherent perspective. Two groups of researchers (M. Schaller and K. Svozil in Vienna, and A. A. Grib and R. R. Zapatrin in St. Petersburg) have approached this issue from different directions. In this joint paper we investigate the connection between these two approaches.
The paper is organized in the following way: in section the class of automata we are going to deal with is specified. In section the concept of the empirical logic of automata is specified. The approach carried out by the Vienna group based on a partitioning of the set of automaton states is introduced in section , and that of the St. Petersburg group based on a closure operation on the set of inputs is described in section . The comparison of the two approaches concludes the paper.
| ||||||||||||||||
| ||||||||||||||||
As an example, consider the normalized automaton associated with the graph P drawn in Fig. .
1.00mm
Picture Omitted
Suppose the automaton is prepared in the initial state corresponding to the vertex 1. Then, if we apply the input 1, the state of the automaton will not change, and it will output the symbol 1. If, starting from the same initial state 1, the input 2 is applied, the state of the automaton changes to 2, though the output value will still be 1. If, on the other hand, we apply any one of the inputs 3 or 4, then the automaton makes a transition to the final state 0 (since there is no edge between the initial vertex 1 and the vertices 3 and 4, respectively) and the output value will be 0. We shall return to this example in the discussion of the propositional structures below.
The motivation behind the investigations in this paper is the construction of primitive empirical statements or propositions about automata []. Such experimental statements form the basis of the formal investigation of the corresponding logics. In particular, there exist automata for which validation of one empirical statement makes impossible the validation of another empirical statement and vice versa, as it was first pointed out by Moore [].
Thereby, one decisive feature of the set-up is the intrinsic character of the measurement process: The automaton is treated as a black box with known description but unknown initial state. Automata experiments are conducted by applying an input sequence and observing the output sequence.
In the above example, it is not necessary to input sequences containing more than one symbol, since the non-final states are not distinguished by the output function.
The conventional state identification problem [,,] is to obtain information about an unknown initial state. Thereby it is assumed that only a single automaton copy is available for inspection. That is, no second, identical example of the automaton can be used for further examination. Alternatively, one may think of it as choosing at random a single automaton from an automata ensemble which differ only by their initial state. The task then is to find out which was the initial state of the chosen automaton.
The partition logic approach to finite automata study was introduced in [], and subsequently in [,,]. There, statements about single automata of the following form pA are considered:
| (1) |
|
Let us try to characterize this state identification problem algebraically. Again, V denotes the set of automaton states. Now associate with any input v the set of automaton states such that any pair of states from any element of the partition are mutually indistinguishable. For normalized automata studied in this paper, this partition reduces to the splitting of the entire set of states V into two subsets
| ||||||||||||||||||||||
Now consider the entire collection of the sets of the form V0 and V1 (2) for all possible inputs v. Note that for different inputs, the partitions (2) may coincide (cf. the example below). V0 may be thought of as the negation of V1 and vice versa. Therefore, each pair of them form a Boolean algebra 22. The propositional structure is then built from these algebras by pasting; i.e., by identifying their greatest and their least elements. The resulting propositional structures are the lattices MOn, where n stands for the number of different partitions (2). The partial order can be interpreted as logical implication ``Þ'' on the statements about a single automaton from the ensemble. This is why we call these statements microstatements.
To take up the example mentioned earlier, consider the partitions produced by all possible inputs v = 1,2,3,4. They are
| ||||||||||||||||||||||||||||
It should be emphasized that although the elements of the lattice associated with the partition logic are the subsets of the set of states V, the partial order relation (``implication Þ'') is weaker than the set theoretical inclusion `` Ì .'' For instance, we can see from the above example that {1} Ì {1,2,3} but {1} \notÞ{1,2,3}. In general, the partial order relation always implies set inclusion but not vice versa. Only if two statements can be identified by the same experiment, i.e., only if both statements are simultaneously measurable, the partial ordering coincides with set inclusion.
Before describing the approach in general, we return to our example of automaton. Suppose now that we have at our disposal two ensembles of such automata. The first of them is prepared in such a way that some of the constituent automata of the ensemble are in the state {1,2,3}. That is, initially, the automata from the first ensemble are either in state 1 or in state 2 or in state 3. The second ensemble is prepared in the state {2,3,4}. That is, initially, the automata from the first ensemble are either in state 2 or in state 3 or in state 4.
As before, only one experiment on each particular automaton from the ensemble can be carried out; from each individual automaton in the ensemble, only a single copy is available.
We first perform experiments on the first ensemble. Suppose we have generated the protocol of a sufficiently large sequence of measurements of the results of each input. The values of the output function which can be observed are 0 and 1 for each input.
Next, we deal with the second ensemble in a similar way. Again, looking into the protocol, we see that there are 0's and 1's as the result of each input. Since we have made no particular choice of the distribution of the initial states, we have to conclude that the two states of the ensemble described above are indistinguishable.
However, assume that a third ensemble is prepared in the "pure" state associated with the activation of only the vertex 1. Then, analyzing the protocol, one finds that the output values corresponding to the input 3 are always 0. This makes the protocol differ from the protocols generated from the first two ensembles. Thus, we can distinguish the state of the third ensemble from the states of the first and the second ensemble.
We now give the rigorous definitions. With each subset A Í V, we consider the statement about the ensemble of automata of the following form sA:
| (9) |
|
|
The motivation for this definition is the following. The outcome of the statistical experiment on the ensemble of automata is the protocol of the following form:
| |||||||||||||||||||
In our example, the only proper (i.e. ¹ 0,V) subsets which are in principle testable, are: {1},{4},{1,2},{3,4}. For instance, if, on any input of 1, the output is always 0, then one can conclude that the automata in the ensemble are either in the (micro-)state 3 or in (micro-)state 4; therefore the ensemble is in the macrostate denoted by {3,4}. Since the partial order relation strictly follows set inclusion, the lattice of properties looks as the one drawn in Fig. .
Let us finally state the common features of our two approaches.
Operationalistic. Just as in quantum measurements, the extrinsic view is assumed to be inaccessible. All we are allowed to do is to choose the input to be applied and then observe the output values. For instance, in order to measure the electron spin, we are not allowed to ``screw open'' the electron. Moreover, one cannot in general copy an (arbitrary number of) identical electrons from the single electrons taken from an ensemble.
Mathematical. In both approaches, the collection of propositions is associated with a partially ordered set, whose elements are subsets of the set of states of the automaton.
Since our two approaches are based on different empirical setups, there are certain features in which of our two approaches differ.
Automaton model. The normalized automata used here are appropriate for the logical simulation of macrostatements. They are assumed to have only two output values. With a different automaton model, to which the partition logic of microstatements is applicable, one obtains more general structures of microstatements than the lattices MOn. Examples of such automaton models are Moore and Mealy type automata having more than two output values and thus allowing for more than two elements in the partitions.
Operationalistic.
Macrostatements refer to ensembles of automata.
Mathematical.
The structure of the collection of macroproperties is always a lattice with orthocomplementation. It is not necessarily orthomodular [].
The collections of subsets associated with testable microstatements and macrostatments do not in general include one another but always overlap. The partial ordering of these subsets can be induced from both sorts of propositional structures. For macrostatements, the partial order is exactly the set inclusion. As has already been pointed out, for microstatements the set inclusion implies the partial order only if both statements are simultaneously measurable (cf. section 3).
Brauer, W. Automatentheorie (Teubner, Stuttgart, 1984).
Conway, J. H.: Regular Algebras and Finite Machines, (Clowes and Sons, London, Colchester, 1971).
Svozil K., Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).
1 Institut für Theoretische Physik, University of Technology Vienna, Wiedner Hauptstraß e 8-10/136, A-1040 Vienna, Austria; e-mail: svozil@tph.tuwien.ac.at
2 Department of Mathematics, SPb UEF, Griboyedova, 30-32, 191023, St. Petersburg, Russia; e-mail: tmpry@friedman.usr.lgu.spb.su