Two Characterizations of Finite-State Dimension

A. Kozachinskiy; A. Shen

doi:10.1007/978-3-030-25027-0_6

АБВ
АБВ
АБВ

Обычная версия сайта

Priority areas

by year

Subject

News

October 14, 2026

At HSE University–St Petersburg, Experts Discuss How AI Changes Tourist Routes and Cultural Heritage

Neural networks are no longer simple travel assistants; now they decide what to include on the route and what to skip. Artificial intelligence changes how people perceive a place and shapes the image of tourist centres. At the II International Scientific and Practical Conference ’Information Technologies in the Preservation and Promotion of Cultural Heritage,’ researchers discussed who controls algorithmic solutions and in what ways, and whether authentic traditions get lost in them.

October 12, 2026

Road Injuries Leading Cause of Death Among Men Aged 10 to 39

Worldwide, road injuries are the leading cause of death among males aged 10–39. An international team of researchers reached this conclusion as part of the Global Burden of Disease Study 2023, analysing data from 204 countries between 1990 and 2023. Their findings have been published in The Lancet Public Health, with HSE University Professor Vasily Vlassov listed among the collaborators.

October 8, 2026

HSE Experts Take Part in 23rd Annual Meeting of Valdai Discussion Club

The 23rd Annual Meeting of the Valdai Discussion Club was held from September 28 to October 1, 2026 under the theme ‘Responsibility for the Future: Limits of the Possible, or Limitless Possibilities?’ The forum brought together 120 experts from 40 countries, including representatives of China, the United States, India, Brazil, the United Kingdom, Germany, Egypt, Iran, and Japan.

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications

?

Two Characterizations of Finite-State Dimension

P. 80–94.

Kozachinskiy A., Shen A.

In this paper we provide two equivalent characterizations of the notion of finite-state dimension introduced by Dai, Lathrop, Lutz and Mayordomo [7]. One of them uses Shannon’s entropy of non-aligned blocks and generalizes old results of Pillai [12] and Niven – Zuckerman [11]. The second characterizes finite-state dimension in terms of superadditive functions that satisfy some calibration condition (in particular, superadditive upper bounds for Kolmogorov complexity). The use of superadditive bounds allows us to prove a general sufficient condition for normality that easily implies old results of Champernowne [5], Besicovitch [1], Copeland and Erdös [6], and also a recent result of Calude, Staiger and Stephan [4].

Language: English

DOI

Keywords: Finite-state dimension Superadditive complexity functions Normal sequences

Publication based on the results of:

Mathematical methods in algorithm theory and computational complexity (2019)

In book

Fundamentals of Computation Theory, 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings

Vol. 11651. , Springer, 2019.

Finite-state relative dimension, dimensions of A. P. subsequences and a finite-state van Lambalgen's theorem

Nandakumar S., Pulari S., S A., Information and Computation 2024 Vol. 298 Article 105156

Finite-state dimension, introduced by Dai, Lathrop, Lutz and Mayordomo quantifies the information rate in an infinite sequence as measured by finite-state automata. In this paper, we define a relative version of finite-state dimension. The finite-state relative dimension dimFSY(X) of a sequence X relative to Y is the finite-state dimension of X measured using the class of finite-state gamblers with oracle access to Y. We ...

Added: February 20, 2026