Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Modal Logics with Hard Diamond-Free Fragments Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Quest for Algorithmically Random Infinite Structures, II

verfasst von : Bakhadyr Khoussainov

Erschienen in: Logical Foundations of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present an axiomatic approach that introduces algorithmic randomness into various classes of structures. The central concept is the notion of a branching class. Through this technical yet simple notion we define measure, metric, and topology in many classes of graphs, trees, relational structures, and algebras. As a consequence we define algorithmically random structures. We prove the existence of algorithmically random structures with various computability-theoretic properties. We show that any nontrivial variety of algebras has an effective measure 0. We also prove a counter-intuitive result that there are algorithmically random yet computable structures. This establishes a connection between algorithmic randomness and computable model theory.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On Lambek’s Restriction in the Presence of Exponential Modalities
Nächstes Kapitel Probabilistic Justification Logic
Fußnoten
1
The next subsection provides many examples of classes with height function. For now, for the reader a good example of a class with a height function is the class of rooted finite binary trees.
 
Literatur
1.
Benjamini, I., Schramm, O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6(23), 1–13 (2001)MathSciNetMATH
2.
Calude, C.S.: Information and Randomness - An Algorithmic Perspective, 2nd edn. Springer, Heidelberg (2002). Revised and ExtendedCrossRefMATH
3.
Chaitin, G.J.: On the length of programs for computing finite binary sequences: statistical considerations. J. ACM 16, 145–159 (1969)MathSciNetCrossRefMATH
4.
Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York (2010)CrossRefMATH
5.
Grätzer, G.: Universal Algebra. Springer, New York (2008). Revised reprint of the second editionCrossRefMATH
6.
Hodges, W.: Model Theory. Encyclopaedia of Mathematics and Its Applications, vol. 42. Cambridge University Press, Cambridge (1993)CrossRefMATH
7.
Kolmogorov, A.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1, 1–7 (1965)MATH
8.
Khoussainov, B.: A quest for algorithmically random infinite structures. In: Proceedings of LICS-CSL Conference Vienna, Austria (2014)
9.
10.
Kozen, D.: Complexity of finitely presented algebras. In: Proceedings of the 9th ACM Symposium on Theory of Computing, p. 164–177 (1977)
11.
Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and its Applications. Springer, Heidelberg, 3rd Edn., p. xx+792 (2008)
12.
Mal’cev, A.I.: Constructive algebras. I. Uspehi Mat. Nauk, 16(3(99)), 3–60 (1961)
13.
14.
15.
16.
Nies, A., Stephan, F.: Personal communication
17.
Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Amer. Math. Soc. 95, 341–360 (1960)MathSciNetMATH
18.
19.
Schnorr, C.P. : The process complexity and effective random tests. In: Proceedings of the Fourth ACM Symposium of Theory of Computing, Denver, Colorado, 13 May (1972)
20.
Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algoritheorems. Russ. Math. Surv. 25(6), 83–124 (1970)CrossRefMATH
Metadaten
Titel
A Quest for Algorithmically Random Infinite Structures, II
verfasst von
Bakhadyr Khoussainov
Copyright-Jahr
2016
Buch
Logical Foundations of Computer Science

Print ISBN: 978-3-319-27682-3

Electronic ISBN: 978-3-319-27683-0

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-27683-0_12

Premium Partner

    Bildnachweise