Semigroups and effective structures of automata

  • M. Dal Cin
  • E. Dilger
Contributed Papers IV. Structure of Groups and Dynamical Systems
Part of the Lecture Notes in Physics book series (LNP, volume 79)


In physical realizations of complex systems the internal feedback flow of information (e.g. carried by electric signals) often gives rise to serious synchronization and reliability problems. Clearly, the maintainability of a system increases with decreasing interdependence of system components. On the other hand, the effect of signal delays due to propagation times decreases. Therefore, it is convenient - if not mandatory - to design complex systems in such a way that their internal feedback of information is minimal. For a class of finite statemachines (automata) this goal is reached as soon as an algorithm is given by which each machine of this class can be decomposed into a cascade |1| of smaller machines each of which no longer decomposable in a meaningful way; cf. Fig. 1.


  1. 1.
    H. Jürgensen, this volumeGoogle Scholar
  2. 2.
    C. Wells, Am. Math. Month. 83, 317, 1976Google Scholar
  3. |3|.
    M. A. Arbib, The Algebraic Theory of Machines, Languages and Semigroups, Academic Press, 1968Google Scholar
  4. |4|.
    H. Wielandt, On factors of groups, Symp. Math. 1, 187; Ist. Nat. di Alta Mathematica, Roma 1968Google Scholar
  5. |5|.
    E. Dilger, thesis University of Tübingen, Inst. for Inform.SciencesGoogle Scholar
  6. |6|.
    E. Dilger, Inform. Control 30, 86, 1976Google Scholar
  7. |7|.
    E. Dilger, this volumeGoogle Scholar
  8. |8|.
    M. Dal Cin, in Proc. Tübingen Int. Summer School on Groups and Many Body Physics, 1977Google Scholar
  9. |9|.
    S. Eilenberg, Automata, Languages and Machines, Academic Press, 1974Google Scholar
  10. |10|.
    A. Nozaki, Practical Decomposition of Automata, to appear.Google Scholar

Copyright information

© Springer-Verlag 1978

Authors and Affiliations

  • M. Dal Cin
    • 1
  • E. Dilger
    • 1
  1. 1.Institute for Information SciencesUniversity of TübingenTübingenGermany

Personalised recommendations