Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Endliche Automaten und Zufallsfolgen

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

We consider the behaviour of finite automata on infinite binary sequences and study the class of random tests which can be carried out by finite automata. We give several equivalent characterizations of those infinite binary sequences which are random relative to finite automata. These characterizations are based on the concepts of selection rules, martingales and invariance properties defined by finite automata.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Literatur

  1. Agafonoff, V. N.: Normal sequences and finite automata. Soviet Math. Dokl. 9, 324–325 (1968) (engl. Übersetzung).

    Google Scholar 

  2. Böhling, K. H., Indermark, K.: Endliche Automaten I. Mannheim: BI 1969.

    Google Scholar 

  3. Chaitin, G. J.: On the length of programs for computing finite binary sequences. Journ. ACM 13, 547–569 (1966).

    Google Scholar 

  4. Chung, K. L.: Markov chains with stationary transition probabilities, 2. edition. Berlin-Göttingen-Heidelberg: Springer 1967.

    Google Scholar 

  5. Copeland, A. H.: Admissible numbers in the theory of probability. Amer. Journ. Math. 50, 535–552 (1928).

    Google Scholar 

  6. Doob, J. L.: Note on probability. Annals of Math. 37, 363–367 (1936).

    Google Scholar 

  7. Hotz, G., Walter, H.: Automatentheorie und formale Sprachen. Mannheim: BI 1969.

    Google Scholar 

  8. Kolmogoroff, A. N.: Drei Zugänge zur Definition des Begriffs „Informationsgehalt” [russisch]. Probl. peredaci informacii 1, 3–11 (1965).

    Google Scholar 

  9. Loveland, D. W.: A variant of the Komogoroff concept of complexity. Inform. Control 15, 510–526 (1969).

    Google Scholar 

  10. Martin-Löf, P.: The definition of Random sequences. Inform. Control 6, 602–619 (1966).

    Google Scholar 

  11. Popper, K.: Logik der Forschung zur Erkenntnistheorie der modernen Naturwissenschaft. Schriften zur wissenschaftlichen Weltauffassung, Bd. 9. Wien: Springer 1935.

    Google Scholar 

  12. Reichenbach, H.: Wahrscheinlichkeitslehre. Leiden: Sijthoff 1935.

    Google Scholar 

  13. Schnorr, C. P.: Zufälligkeit und Wahrscheinlichkeit. Lecture Notes. Berlin-Heidelberg-New York: Springer 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Mathematik der Johann Wolfgang Goethe-Universität, Robert-Mayer-Str. 10, D-6000, Frankfurt 1, Bundesrepublik Deutschland

    C. P. Schnorr & H. Stimm

Authors
  1. C. P. Schnorr
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. Stimm
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Diese Arbeit wurde im Rahmen des Forschungsvorhabens Schn 143/1 von der Deutschen Forschungsgemeinschaft gefördert.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schnorr, C.P., Stimm, H. Endliche Automaten und Zufallsfolgen. Acta Informatica 1, 345–359 (1972). https://doi.org/10.1007/BF00289514

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00289514

Search

Navigation