On a measure of complexity for stochastic sequential machines
- 1 October 1968
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The need for a measure different from the number of states in analyzing stochastic sequential machines is pointed out. Using the decomposition previously demonstrated in association with actual physical realization of stochastic sequential machines4, a particular measure of complexity C(M) for a given machine M is introduced. The computational aspect of C(M) is discussed and an example exhibiting two state-equivalent machines M1 and M2 with #{S1} ≫ #{S2} (#{Si} ≡ number of states of machine Mi i=1, 2) but C(M1) ≪ C(M2) is given. Areas for future research are pointed out.Keywords
This publication has 3 references indexed in Scilit:
- On the Uniqueness of Minimal-State Stochastic Sequential MachinesIEEE Transactions on Computers, 1970
- Reduced forms for stochastic sequential machinesJournal of Mathematical Analysis and Applications, 1963
- Markov Chains as Random Input AutomataThe American Mathematical Monthly, 1961