Partition logics of automata

M. Schaller and K. Svozil
Institut für Theoretische Physik
Technische Universität Wien
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
e1360dab@AWIUNI11.EDVZ.UniVie.AC.AT

Abstract

1  Introduction

Informally stated, the motivation behind this investigation is the construction of primitive experimental statements or propositions about automata [11]. Such experimental statements can be grouped into partitions of the set of internal automaton states; they form the basis of the formal investigation into the corresponding logics. In particular, there exist automata for which validation of one experimental statement makes impossible the validation of another experimental statement and vice versa.

2  Orthomodular Posets

For a detailed introduction to orthomodular posets and lattices see [10] and [7].  A bounded poset P has a smallest element 0 and a largest element 1, such that 0 £ x £ 1 holds for all x Î P .

Let (P, £ ) be a bounded poset. An orthocomplementation on P is a unary operation ¢ on P satisfying
(i) if x £ y then y¢ £ x¢ ,
(ii) x¢¢ = x ,
(iii) the supremum x Úx¢ exists and x Úx¢ = 1.

An orthoposet is a bounded poset with an orthocomplementation.

The relation orthogonal ^ for elements x, y of an orthoposet P is defined by
x ^y (x is orthogonal to y) if x £ y¢ holds.

An orthomodular poset P (abbr. OMP) is an orthoposet P satisfying
(i) if x ^y then the supremum x Úy exists in P
(ii) x £ y implies y = x Ú( x¢Ùy ) .
An orthomodular lattice (abbr. OML) is an OMP which is also a lattice.

A subalgebra is a subset M which is closed under the operations ¢, Ú,Ù and which contains 0 and 1. The subalgebra GA generated by an arbitrary subset A of P is the smallest subalgebra of P containing A if it exists.

If x £ y then it is obvious that G{x,y} = {0,1,x,x¢Ùy,y¢,y,x Ùy¢,x¢} (see [7]).

Let L be an OMP. A pair a,b Î L is called compatible, denoted by a « b if there exist three mutually orthogonal elements a₁, b₁, c Î L such that a = a₁ Úc and b = b₁ Úc.

Lemma 1 (i) if a,b Î L and a ^b then a « b;
(ii) if a,b Î L and a £ b, then a « b;
(iii) if a,b Î L,a « b, a = a₁ Úc, b = b₁ Úc for three mutually orthogonal elements a₁,b₁,c Î L then a Úb and a Ùb exist and a Úb = a₁ Úb₁ Úc and a Ùb = c.

For a proof see [10].

Let \frak L be a non-empty set of OMPs such that all P,Q Î \frak L satisfy the following condition:
P ÇQ is a sub-OMP of both P and Q, and the partial orderings and the orthocomplementations of P and Q coincide on P ÇQ .
On L = È\frak L define the relation £ and ¢ as follows:
x £ y iff x £ _P y for some P Î \frak L
x¢ = x¢^P iff x Î P
The algebra (L, £ ,¢) is called the pasting of the set \frak L.

A block of an OMP P is a maximal Boolean subalgebra of P. Every element x of P is contained in at least one block since the Boolean subalgebra generated by x (and consisting of x,x¢,0,1) can be embedded into a maximal one.

Let \frak B be a non-empty set of Boolean algebras such that for all B,C Î \frak B the following conditions hold:
(i) 0 = 0_B = 0_C,1 = 1_B = 1_C,
(ii) for all x Î B ÇC holds: x¢ = x¢^B = x¢^C,
(iii) B ÇC is a subalgebra of both B and C.
(the indices indicate that the operations belong to the respective Boolean algebras)
Define on the set L = È\frak B a unary operation ¢ and a relation £ by:
x¢ = x¢^B if x Î B for a B Î \frak B,
x £ y if x £ _B y for a B Î \frak B.
The set L together with ¢ and £ is called the pasting of the set \frak B.

Consider a set M and a set \frak R of partitions of M. Every partition P Î \frak R generates a Boolean algebra (B_P, Í ,¢) where B_P is the union set of P, Í is the inclusion and ¢ is the set-complement. We will call the pasting of this Boolean algebras a partition logic and denote it by (M,\frak R).

Lemma 2 A partition logic is an OMP if the following two conditions hold:
(i) the induced relation £ is transitive.
(ii) if a^b then the supremum a Úb exists.

Proof: Let (M,\frak R) be a partition logic which satisfies the conditions. Obviously (M,\frak R) is an orthocomplemented poset. Let a,b Î (M,\frak R) and a ^b. Then there exists a P Î \frak R such that a,b Î B_P. In B_P the supremum exists and a Ú_BP b = a Èb. If c Î (M,\frak R) ,a £ c and b £ c then a Èb Í c holds. Since the supremum a Úb exists in (M,\frak R) we conclude that a Úb = a Èb £ c. The orthomodular law holds, because for a £ b and a,b Î B_P we have a Ú(a¢Ùb) = a Ú_BP (a¢Ù_BP b) = b.

For a more general proposition, see [9].

Every OMP can be viewed as the pasting of its blocks (see [10],[7] and [9]). Another way to dissamble an OMP L in Boolean algebras is the following one: Define \frak C(L) : = {G{x,y}|x,y Î L; x £ y}. Then L is the pasting of the set \frak C(L).

A non-void subset I of an OMP L is called an ideal if it satisfies the following conditions:
(i) if a Î I and b £ a then b Î I,
(ii) if a,b Î I and a ^b then a Úb Î I.

A prime ideal of an OMP L is an ideal P, P \not = L which satisfies the following condition:
a ^b implies a Î P or b Î P
The set of all prime ideals of an OMP L will be denoted by P(L).

Lemma 3 Let P, P \not = L be an ideal. The following conditions are equivalent.
(i) P is a prime ideal.
(ii) x Î P iff x¢\not Î P for all x Î P.

Proof: (i) implies (ii). x ^x¢ holds, hence x Î P or x¢ Î P. If x Î P and x¢ Î P then also 1 = x Úx¢ Î P, which is a contradiction to P \not = L.
(ii) implies (i). Let x,y Î P be orthogonal elements. One of the elements x,x¢ is in P. If x Î P then condition (i) is satisfied. On the other hand, if x¢ Î P then also y Î P because y £ x¢ holds.

Lemma 4 Let P be a prime ideal.
a « b and a Ùb Î P implies a Î P or b Î P.

Proof: Let a « b and a Ùb Î P. Then there exist three mutually orthogonal elements a₁,b₁,c ,such that a = a₁ Úc,b = b₁ Úc and c = aÙb. a₁ ^b₁ implies a₁ Î P or b₁ Î P. If a₁ Î P then also a = a₁ Úc Î P. On the other hand, if b₁ Î P then also b = b₁ Úc Î P.

An OMP L is called prime if for all a,b Î L, a \not = b there exists a prime ideal P of L such that a Î P,b\not Î P or a\not Î P,b Î P.

Let L₁,L₂ be OMPs. A mapping f:L₁ ® L₂ is called a morphism if the following conditions are satisfied:
(i) f(0) = 0;
(ii) f(a¢) = f(a)¢ for all a Î L₁;
(iii) a,b Î L₁ and a ^b implies f(a Úb) = f(a) Úf(b).
A morphism f is called an isomorphism if f is injective and f^-1 is also a morphism.

The following theorem can be seen as a generalization of Birkhoff's representation theorem for OMPs. In our case we have to require that the OMP is prime. (For Boolean algebras Stone's theorem hold, which state that every distributive lattice is prime.)

Theorem 1 An OMP L is isomorpic to a partition-logic iff L is prime.

Proof: (i) Suppose first that L is isomorpic to an partition-logic (M, \frak P). We may assume that L = (M, \frak P). Let A,B Î L and A \not = B. Then the set C: = (A-B) È(B-A) is not empty and we can choose a point p Î C. Define a set P Í L by P : = { X Î L| p \not Î X}. Then only one of the elements A,B is in P and we can easily check that P is a prime ideal.
(ii) Let L be a prime OMP. We denote by \frak P(P(L)) the power set of P(L). Define a mapping p: L ® \frak P(P(L)) by p(x): = {P Î P(L)| x \not Î P}.
We first proof some properties of p:
p(0) = Æ is obvious.
From Lemma 3 we know that x Î P iff x¢\not Î P. Hence, p(x¢) = P(L) - p(x).
Let x,y Î L and x ^y. We verify that p(x Úy) = p(x) Èp(y) holds. Let P Î p(x Úy). This implies xÚy \not Î P. If x Î P and y Î P then also x Úy Î P which is contradiction. Hence, x \not Î P or y \not Î P and therefore P Î p(x) Úp(y). Let now P Î p(x), i.e. x \not Î P. If x Úy Î P then also x Î P which is again a contradiction. Hence, x Úy \not Î P and P Î p(x Úy). This proofs p(x) Í p(x Úy); in the same way p(y) Í p(x Úy).
We define now the isomorphic partition logic: Let x,y Î L and x ^y. We set R({x,y}): = {p(x),p(y),p(x¢Ùy¢)}. Let us verify that R({x,y}) is a partition of P(L). From x £ y¢ we obtain p(x) Í p(y¢) and further p(x) Çp(y) = Æ. p(x¢Ùy¢) = p((x Úy)¢) = P(L) - (p(x) Èp(y)) proofs that R({x,y}) is indeed a partition. Set \frak R = {R({x,y})| x ^y; x,y Î L}. Then K = (P(L),\frak R) is a partition logic. Further, K is the range of p. If x,y are different elements of L then there exists a prime ideal P such that P includes one of the elements without including the other. Therefore, p is injective. Hence, p:L ® K together with the properties of p above is an isomorphism.

Let L be a Greechie logic (an OMP which can be described by a Greechie diagram, see [10]). Let A be the set of all atoms of L and let \frak B the set of all blocks of L.
A set W Í A is called a weight if for all B Î \frak B we have W ÇB = {a} for an atom a Î A, i.e. the intersection of W and an arbitrary block consists of exactly one atom.
The set of all weights on L will be denoted by W(X).

Lemma 5 Let j: P(L) ® W(X) be the mapping defined by j(P) = {a Î X|a \not Î P}. Then j is bijective.

For a proof see [10].
We only remark that the inverse mapping is given by j^-1 = {x Î L| x £ a¢ for an atom a Î W}.

There exists a finite OMP, which is not prime, and hence, which is not isomorpic to a partition-logic. The OMP is given by the following Greechie- diagram.

Picture Omitted
It is easy to check that the OMP has no prime ideals.

A concrete logic is a set W and a collection D of subsets of W such that the following condititions are satisfied:
(i) Æ Î D
(ii) if A Î D then W- A Î D
(iii) if A,B Î D and A ÇB = Æ then A ÈB Î D
The relation £ is given by the inclusion and the ortocomplement ¢ is given by the complement in W. By this definition every concrete logic is an OMP.

A two-valued state on an OMP L is a mapping s:L ® {0,1} such that
(i) s(1) = 1;
(ii) if a ^b and a,b Î L then s(a Úb) = s(a) + s(b).
The set of all two-valued states on L is denoted by \frak S(L).

Lemma 6 Let L be an OMP. Then the mapping c: \frak S(L) ®P(L), c(s) = {x Î L|s(x) = 0} is bijective.

Proof: Let L be an OMP, s a two-valued state on L. We show that the set P = {x Î L| s(x) = 0} is a prime ideal of L. s(0) = 0 and s(1) = 1 implies P \not = Æ and P \not = L.
Let b Î P and a £ b. Then s(b) = 0 implies s(a) = 0. Hence, a Î P.
Let a ^b and a,b Î P. Then a Úb Î P because s(a Úb) = s(a) + s(b) = 0.
Let x ^y. s(xÚy) = s(x) + s(y) £ 1 implies s(x) = 0 or s(y) = 0. Hence, x Î P or y Î P.
The inverse mapping is given by c^-1(P)(x) = 0 if x Î P and c^-1(P)(x) = 1 if x \not Î P.

An OMP L is called rich if if the following implication holds:
({s Î \frak S(L)|s(a) = 1} Í {s Î \frak S(L)|s(b) = 1}) implies a £ b.

Theorem 2 (Gudder [6]): An OMP L is isomorphic to a concrete logic iff L is rich.

For a proof see [6] or [10].

Lemma 7 Every rich OMP is prime.

Proof: Let L be a rich OMP and let a,b,a ¹ b be elements of L. Let us assume that ({s Î \frak S(L)|s(a) = 1} = {s Î \frak S(L)|s(b) = 1}). The richness of L implies a £ b and b £ a, hence a = b, which is a contradiction to a ¹ b. It follows there is a state s Î \frak S(L) such that s(a) = 1,s(b) = 0 or s(a) = 0, s(b) = 1. Lemma 6 implies that this is equivalent to the existence of a prime ideal which includes one of the elements a,b, without including the other. This proofs also that every concrete logic is a partiton logic.

There exists an OMP which is prime, but not rich. The OMP is given by the following Greechie-diagram.

Picture Omitted
We construct an isomorpic partition logic: The weights of L are:
W₁ = {1,5,9,13}, W₂ = {1,4,6,9}, W₃ = {1,5,8,10},
W₄ = {2,5,9,12,13}, W₅ = {2,5,8,11,13}, W₆ = {2,4,6,9,12},
W₇ = {2,4,7,11}, W₈ = {2,4,6,8,11}, W₉ = {2,5,8,10,12},
W₁₀ = {3,7,11,13}, W₁₁ = {3,6,8,11,13}, W₁₂ = {3,7,10,12}
W₁₃ = {3,6,8,10,12}.
For Greechie logics the composition q: = j°p: L ®\frak P(W(X)) is also a morphism and the restriction q: L ®q(L) is again an isomorphism (lemma 5 and theorem 1). We can also restrict q to the set of atoms: q: X ® \frak P(W(X)). The function q is given by q(x) = {W Î W(X)|x Î W}.

The following Greechie shows the picture of q for the atoms. (The letter W is not written).

Picture Omitted
For a proof that the OMP from figure 2 is not rich, see [10].

3  Automata Logic

In the sequel we want to investigate the logic of discrete, deterministic systems. For this purpose we use the automaton concept.

An alphabet is a finite set, the elements of an alphabet are called symbols. A word (string) is a finite sequence of symbols juxtaposed. Let S be an alphabet. The set of all words over S
S^* = {x₁¼x_n|x_i Î S, 1 £ i £ n, 0 £ n }
together with the concatenation is the free monoid with neutral element e (for n = 0). |w| denotes the length of a word w Î S^*: |x₁¼x_n| = n.

A Mealy automaton is a 5-tuple M = (Q,S,D,d,l), where
(i) Q is the set of states,
(ii) S is the input alphabet,
(iii) D is the output alphabet,
(iv) d:Q×S® Q is the transition function,
(v) l:Q×S® D is the output function.

The functions d and l can be generalized to functions [^(d)] :Q ×S^* ® Q and [^(l)] :Q ×S^* ® D^*.
Let q Î Q, w Î S^* ,a Î S.
(i) [^(d)](q,e) = q
(ii) [^(d)](q,wa) = d([^(d)](q,w),a)
(i) [^(l)](q,e) = e
(ii) [^(l)](q,wa) = [^(l)](q,w) l([^(d)](q,w),a)
In the sequel we write also d and l for [^(d)] and [^(l)]
We need also the generalization of l to a function l: \frak P(Q) ® \frak P(S^*).
Let P be a subset of Q.We set
l(P,w) = È_{q Î P} l(q,w).

The relation = for states p,q Î Q and w Î S^* is defined by
p = q if l(p,w) = l(q,w).
= is an equivalence relation. For the partition generated by = we write Q/ = and the equivalence classes are denoted by [q]_w.

Two states p,q Î Q are called distinguishable if there is a word w Î S^* such that l(p,w) ¹ l(q,w).

We shall investigate the following distinguishing problem: If an automaton M and its description is given (i.e. the 5-tuple M = (Q,S,D,d,l) ), but not the state of the automaton, which propositions can we make about the initial state? To learn something about the initial state, we have to enter a word and observe the output. If the input word is determined before we observe the first output, the experiment is called a simple one. Alternatively, the input word can depend on its previous output, permitting the experiment to branch. The later experiments are called branch experiments.

Let us first consider only simple experiments. Every simple experiment is described by an input word w Î S^*. We assign to every state q Î Q the proposition ``The automaton is in the state q'' and write for this proposition again q. In the same way, we identify a subset P of Q with the disjunction of the propositions in P, in words ``The automaton is is in a state q Î Q'' (more exactly q stands for `` The initial state of the automaton at the begin of the experiment is q''). A proposition is called decidable if there is a simple experiment which determines the truth value.

In generally, it is not possible to determine what state the automaton was in at the beginning of the experiment even when any pair of the automaton states is distinguishable (Moore's Uncertainty Principle [8], [3]). So the question we asked is not trivial.

Every partition Q/ = generates a Boolean algebra, denoted by B(Q/ = ). The mapping j:Q/ = ® l(Q,w) defined by j([q]_w) = l(q,w) is bijective.
We also generalize j to a function

j:B(Q/ = )® \frak P(S^*):
j(A) = È_{[q]w Í A} l(q,w).

Lemma 8 A proposition P Í Q is decidable by a simple experiment w Î S^* iff P Î B(Q/ = ).

Proof: l(w) denotes the observed output of the experiment. Of course, l(w) Î l(Q,w) holds.
(i) Let P Î B(Q/ = ). It follows
P is true iff l(w) Î j(P).
Hence, P is decidable.
(ii) Let P Î \frak P (Q), but P \not Î B(Q/ = ). Then there exists a W Î l(Q,w) such that Æ Ì j^-1(W) ÇP Ì j^-1 (W), where the inclusion is proper. There are points p,q Î Q such that q Î j^-1(W) ÇP and p Î j^-1(W) - P. If the observed output is W then P is not decidable, because the initial state of the automaton could be p as well as q. But the true value of the proposition P depends on this fact.

The pasting of all partitions Q/ = , w Î S^* generates a partition logic, denoted by L(M) = (Q,{Q/ = | w Î S^*}).

Lemma 9 (Svozil [11]) To every partition logic L there exists an automaton M such that L = L(M).

Proof: Let L = (Q,\frak P) be a partition logic. We will construct a minimal automaton M in the sense, that M has at most three outputs. Therefore we use the dissambling \frak C(L).
We define M = (Q,\frak C(L),{0,1,2},d,l).
Let p be an arbitrary element of Q.
Let q Î Q, C Î \frak C(L) and denote the atoms of C by A₀,A₁,A₂.
We define:
d(q,C): = p and
l(q,C) = i,0 £ i £ 2 if q Î A_i.
Obviously, L = L(M).

Notice, that nonisomorphic automata can possess the same partition logic.

We now want to clarify in which way the logical connection of propositions is expressed in the partition logic. The interpretation of the orthocomplement is quite straightforward. The orthocomplement A¢ of a proposition A is the logical negation of A, i.e. A¢ has the meaning ``non A''. Notice, that every experiment which decides A also decides A¢.
The relation £ can be interpreted by:
A £ B iff (``if A is true then B is true'' and there is a experiment which decides both propositions A and B).
That means £ is not an idealistic relation, but a measurable one.

Two propositions of a partition logic are simultaneously measurable, if both propositions can be decided by the same experiment. In quantum logic two propositions are simultaneously measurable if the generate a distributive subalgebra. This does not hold for partition logics.
Consider two automata with the partitions:
{{{1},{2},{3},{4}}} and
{{{1},{2},{3,4}},{{1},{3},{2,4}},{{1},{4},{2,3}},
{{2},{3},{1,4}},{{2},{4},{1,3}},{{3},{4},{1,2}}}.
The pasting of the both is the same, the Boolean algebra 2⁴, but by the first the two propositions {1,2} and {1,3} are simultaneously mesurable, but not by the second partition. For a further discussion of the relationship between partition logics and quantum logics, see K. Svozil [11].

At last we will consider branch experiments. Formally, we can describe branch experiments by a mapping E:D^* ® SÈ{e} (see also [3]).
The branch experiment E is carried out in the following way:
(i) E(e) denotes the initial input symbol.
(ii) Let us assume the input w Î S^* was applied and the output W Î D^* was observed. Then we enter the input E(W) into the automaton. The experiment terminates if E(W) = e.
l_E(q) denotes the observed output, if the automaton was in the initial state q. Similiar to simple experiments we define an equivalence relation
q = p iff l_E(q) = l_E(p).
Therefore we can use the same methods as for simple experiments. The yield a partition logic L_branch(M) by the same way. Note that L_simple(M) Í L_branch(M) which is the simple consequence of the fact that every simple experiment is also a branch experiment.

References

[1]

Birkhoff, G.: Lattice Theory, Second Edition. New York: American Mathematical Society 1948

[2]

Birkhoff, G. and von Neumann, J.: The logic of quantum mechanics, Ann. Math.

37, 823-843 (1936)

[3]

Conway, J. H.: Regular Algebra and Finite Machines. London: Chapman and Hall Ltd. 1971

[4]

Finkelstein, D. and Finkelstein, S. R.: Computational complementarity. International Journal of Theoretical Physics 22, 753-779 (1983)

[5]

Grib, A. A. and Zapatrin, R. R.: Automata simulating quantum logics. International Journal of Theoretical Physics 29, 113-123 (1990); Macroscopic realizations of quantum logics. Ibid. 31, 1669-1687 (1992).

[6]

Gudder, S.: Stochastic Methods in Quantum Mechanics. Amsterdam: North-Holland 1979

[7]

Kalmbach, G.: Orthomodular Lattices. New York: Academic Press 1983

[8]

Moore, E.F.: Gedanken-Experiments on Sequential Machines. In: Shannon, C. E. and McCarthy, J. (eds.) Automata Studies. Princeton: Princeton University Press 1956

[9]

Navara, M. and Rogalewicz, V.: The pasting constructions for orthomodular posets. Math. Nachr.

154, 157-168 (1991).

[10]

Pták, P. and Pulmannová, S.: Orthomodular Structures as Quantum Logics. Amsterdam: Kluwer Academic Publishers 1991

[11]

Svozil, K.: Randomness and Undecidability in Physics. Singapore: World Scientific 1993