nach oben

Theory of Computing Systems

Erschienen in:

14.08.2020

Preservation of Normality by Non-Oblivious Group Selection

verfasst von: Olivier Carton, Joseph Vandehey

Erschienen in: Theory of Computing Systems | Ausgabe 2/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We give two different proofs of the fact that non-oblivious selection via regular group sets preserves normality. Non-oblivious here means that whether or not a symbol is selected can depend on the symbol itself. One proof relies on the incompressibility of normal sequences, the other on the use of augmented dynamical systems.

Nächster Artikel Exploration of Dynamic Cactuses with Sub-logarithmic Overhead

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 "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

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

Actually not quite a bijection, due to the phenomenon of \(0.0\overline {9}=0.1\), but this will not be relevant and can be ignored.

Agafonov, V. N.: Normal sequences and finite automata. Sov. Math. Doklady 9, 324–325 (1968)MathSciNetMATH

Becher, V., Carton, O.: Normal numbers and computer science. In: Berthé, V., Rigo, M. (eds.) Sequences, Groups, and Number Theory, Trends in Mathematics Series. Springer, Birkhäuser (2018)

Becher, V., Carton, O., Heiber, P. A.: Normality and automata. J. Comput. Syst. Sci. 81(8), 1592–1613 (2015)MathSciNetCrossRef

Becher, V., Heiber, P. A.: Normal numbers and finite automata. Theor. Comput. Sci. 477, 109–116 (2013)MathSciNetCrossRef

Borel, É. : Les probabilités dénombrables et leurs applications arithmétiques. Rend. Circ. Mat. Palermo 27, 247–271 (1909)CrossRef

Carton, O., Heiber, P. A.: Normality and two-way automata. Inf. Comput. 241, 264–276 (2015)MathSciNetCrossRef

Dai, J., Lathrop, J., Lutz, J., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310, 1–33 (2004)MathSciNetCrossRef

Furstenberg, H.: Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation. Math. Syst. Theory 1, 1–49 (1967)MathSciNetCrossRef

Heersink, B., Vandehey, J.: Continued fraction normality is not preserved along arithmetic progressions. Arch Math. (Basel) 106(4), 363–370 (2016)MathSciNetCrossRef

10.

Kamae, T.: Subsequences of normal sequences. Israel J. Math. 16, 121–149 (1973)MathSciNetCrossRef

11.

Kamae, T., Weiss, B.: Normal numbers and selection rules. Israel J. Math. 21(2-3), 101–110 (1975). Conference on Ergodic Theory and Topological Dynamics (Kibbutz Lavi, 1974)MathSciNetCrossRef

12.

Merkle, W., functions, J. Reimann.: Selection that do not preserve normality. Theory Comput. Syst. 39(5), 685–697 (2006)MathSciNetCrossRef

13.

Moshchevitin, N. G., Shkredov, I. D.: On the pyatetskii-shapiro criterion of normality. Math. Notes 73(3-4), 539–550 (2003)MathSciNetCrossRef

14.

Perrin, D., Pin, J.-É.: Infinite words. Elsevier (2004)

15.

Pin, J.-É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp 679–746. Springer (1997)

16.

Schnorr, C. P., Stimm, H.: Endliche automaten und zufallsfolgen. Acta Inform. 1, 345–359 (1972)MathSciNetCrossRef

17.

Vandehey, J.: On the joint normality of certain digit expansions. arXiv:1408.0435 (2014)

18.

Vandehey, J.: Non-trivial matrix actions preserve normality for continued fractions. Compos. Math. 153(2), 274–293 (2017)MathSciNetCrossRef

19.

Vandehey, J.: Uncanny subsequence selections that generate normal numbers. Unif. Distrib. Theory 12(2), 65–75 (2017)MathSciNetCrossRef

20.

Wall, D. D.: Normal Numbers. ProQuest LLC, Ann Arbor (1950). Thesis (Ph.D.)-University of California, Berkeley

21.

Weiss, B.: Normal sequences as collectives. In: Proceedings of Symposium on Topological Dynamics and Ergodic Theory, Univ. of Kentucky (1971)

Titel: Preservation of Normality by Non-Oblivious Group Selection
verfasst von: Olivier Carton
Joseph Vandehey
Publikationsdatum: 14.08.2020
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2021
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-020-09998-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2021

On the Complexity of the Smallest Grammar Problem over Fixed Alphabets

On the Relation Between Structured d-DNNFs and SDDs

Exploration of Dynamic Cactuses with Sub-logarithmic Overhead

Stable Divisorial Gonality is in NP

Computability of Products of Chainable Continua

Faster Parameterized Algorithm for Cluster Vertex Deletion