An n-state generalized probabilistic automaton/array maps a list of d states stochastically into a next state, resulting in a degree-d polynomially nonlinear transformation of the n-component state-probability vector, in contrast with the linear transformation given by the conventional Markovian model. This nonlinearity introduces the possibility of chaotic behaviour as time (iteration) progresses. It is shown that for two-state systems, the d = 2 case is nonchaotic, while chaotic behaviour is found for degree d as low as 5. Examples, and open issues for other values of n and/or d, are also noted.

Irrelevance relations are sets of statements of the form: given that the ‘value’ of Z is known, the ‘values’ of Y can add no further information about the ‘values’ of X. Undirected Graphs (UGs), Directed Acyclic Graphs (DAGs) and Chain Graphs (CGs) were used and investigated as schemes for the purpose of representing irrelevance relations. It is known that, although all three schemes can approximate irrelevance, they are inadequate in the sense that there are relations which cannot be fully represented by anyone of them. In this paper annotated graphs are defined and suggested as a new model for graphical representation. It is shown that this new model is a proper generalization of the former models: any irrelevance relation that can be represented by either one of the previous models can also be represented by an annotated graph, and there are relations that can be represented by an annotated graph but cannot be represented by either one of the former models. The question of whether this new model is powerful enough to represent all the irrelevance relations, as well as some other related questions, is still open.

The problem of approximating a linear automaton (LA) over the field of real numbers by an automaton over the field of rationals is considered. "Strong" and "weak" types of approximation are defined and investigated. Necessary and sufficient conditions for an automaton to be approximable are given. The strong approximation method enables rational computation in irrational linear systems which is suited for computer use.

Using a technique based on "state splitting" it is shown that every n-state Markov system is decomposable into a whirl interconnection of n−1 two-state Markov systems.

Events representable in stochastic sequential machines, as defined previously by several authors, are shown to be regular in certain cases. The construction of deterministic machines representing those events is implicit.

Let ∑ be a finite alphabet and ∑* the set of all finite words (sequences of symbols) over ∑. A fuzzy event f is a mapping from ∑* into [0, 1] and is called probabilistic if it is induced by a probabilistic automaton.1Some operations are defined on fuzzy events f, g, r: for x∈∑* (f ∨ g)(x) =Max (f(x), g(x)); (f ∧ g)(x)= min (f(x), g(x)); f(x)= 1-f(x); fT(x) =f(xT) where xT= σk⋯ σ1if x = σ1⋯ σk; [f, g:r](x)= f(x)r(x)+g(x)r̄(x), etc., and the closure of the events with regard to those operations are studied. Typical results: probabilistic events are closed under the bar operation, the bracket operation, and the "T" operation, but are not closed under the "∨" or "∧" operations (except for some restricted cases). Of particular interest is the result about the T-closure, as this problem has been open for a couple of years.

Abstract—Finding simple or "canonical representations" for regular events is one of the important problems concerning finite automata. The present paper is an attempt to find concatenative canonical decompositions for regular events. Five different decomposition types of regular events are defined, imustrated by examples, and their properties investigated. The main tool in our investigations is the notion of a decomposition set; it is a generalization of the notion of a decomposition state, introduced by the authors in a previous paper.[7]Let A =(S, M, s0, F) be a finite automaton; a subset S̄⊂S is a decomposition set if A goes through a state of S̄ whenever it accepts a tape. In order to determine whether a given subset S̄⊂S is a decomposition set one has to check only tapes whose length is not greater than |S|-|S̄|-1, where |S| and |S̄| are the number of states in S and S̄, respectively. Thus, one can deternine all decomposition sets of A. The knowledge of the decomposition sets of A enables one to determine whether and in what form T(A), the set of tapes accepted by A, is decomposable.

The minimal number of terms required for representing any switching function as a modulo 2 sums of products is investigated, and an algorithm for obtaining economical realization is described. The main result is the following: every symmetric function of 2m+1 variables has a modulo 2 sum of products realization with at most 3mterms; but there are functions of n variables which require at least 2n/n log23 terms for sufficiently large n.

New classes of events and finite automata which generalize the noninitial definite class are introduced. These events, called “ultimate definite” (u.d.), “reverse u.d.” and “symmetric definite,” are investigated as to algebraic and closure properties. Effective decision procedures whereby it can be decided whether a given finite automata defines such an event are given and unique canonical representations for these events are derived.