# Finite Automata and Randomness

Ludwig Staiger

► To cite this version:

Ludwig Staiger. Finite Automata and Randomness. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.1-10, 10.1007/978-3-319-94631-3_1 . hal-01905642

HAL Id: hal-01905642

https://inria.hal.science/hal-01905642

Submitted on 26 Oct 2018

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Finite Automata and Randomness

Ludwig Staiger

Institut für Informatik,
Martin-Luther-Universität Halle-Wittenberg
D-06099 Halle (Saale), Germany
staiger@informatik.uni-halle.de

**Abstract.** The lecture surveys approaches using finite automata to define several notions of (automata-theoretic) randomness.

It focuses on the one hand on automata-theoretic randomness of infinite sequences in connection with automata-independent notions like disjunctivity and Borel normality.

On the other hand it considers the scale of relaxations of randomness (Borel normality and disjunctivity), that is, finite-state dimension and subword complexity and their interrelations.

**Keywords:** finite automata, infinite words, betting automata, finite-state dimension, subword complexity

## 1 Introduction

The (algorithmic) randomness of infinite sequences can be defined by means of computability. There have been three main approaches to the definition of algorithmically random sequences, namely

1. the measure-theoretic approach,

2. the unpredictability approach, and

3. the incompressibility (or complexity-theoretic) approach.

All these approaches are based on Turing machines and were shown to be equivalent in the case of Martin-Löf random sequences. We refer the reader to the textbooks [5,9,10,13] for a complete history of Martin-Löf randomness and related topics.

After Martin-Löf's measure-theoretic approach [11] and Schnorr's unpredictability approach [16] already in the 1970s sequences random with respect to finite automata were considered. It turned out that two approaches equivalent in the algorithmic case yield different characterisations of sequences which might be called “random” in the automata case. The first approach is an adaptation of the betting or martingale approach of [16] to finite automata whereas the second – in an analogy to Martin-Löf's measure theoretic approach – uses a randomness definition via null sets definable by finite automata.

Here we present a brief survey on both randomness approaches for finite automata and their relaxations which result in the finite-state dimension on the one hand and in a connection to subword complexity on the other hand.
## 2 Notation

We introduce the notation used throughout the paper. By $\mathbb{N} = \{0, 1, 2, ...\}$ we denote the set of natural numbers. Let $X = \{0, ..., r-1\}$ be a finite alphabet of cardinality $|X| = r \ge 2$, and $X^*$ be the set (monoid) of words on $X$, including the empty word $e$, and $X^\omega$ be the set of infinite sequences ($\omega$-words) over $X$. As usual we refer to subsets $W \subseteq X^*$ as languages and to subsets $F \subseteq X^\omega$ as $\omega$-languages.

For $w \in X^*$ and $\eta \in X^* \cup X^\omega$ let $w \cdot \eta$ be their concatenation. This concatenation product extends in an obvious way to subsets $W \subseteq X^*$ and $P \subseteq X^* \cup X^\omega$. For a language $W$ let $W^* := \bigcup_{i \in \mathbb{N}} W^i$ be the submonoid of $X^*$ generated by $W$, and by $W^\omega := \{w_1 \cdots w_i \cdots : w_i \in W \setminus \{e\}\}$ we denote the set of infinite strings formed by concatenating words in $W$. Furthermore $|w|$ is the length of the word $w \in X^*$ and pref($P$) (infix($P$)) is the set of all finite prefixes (infixes) of strings in $P \subseteq X^* \cup X^\omega$, in particular, pref($P$) $\subseteq$ infix($P$). We shall abbreviate $w \in$ pref($\eta$) ($\eta \in X^* \cup X^\omega$) by $w \subseteq \eta$. If $n \le |p|$ then $p[0..n]$ is the n-length prefix of $p \in X^* \cup X^\omega$.

A (deterministic) finite automaton over $X$ is a quintuple $\mathcal{A} = (X, Q, q_0, \delta, Q')$ where $Q$ is a finite set of states, $q_0 \in Q$ the initial state, $\delta: Q \times X \to Q$ is the transition function, and $Q' \subseteq Q$ is the set of final states. As usual $\delta$ also denotes the continuation of $\delta$ to $Q \times X^*$ defined by $\delta(q, e) := q$ and $\delta(q, wx) := \delta(\delta(q, w), x)$.

A language $W \subseteq X^*$ is called regular if there is a finite automaton $\mathcal{A}$ such that $W = \{w : \delta(q_0, w) \in Q'\}$.

## 3 Randomness by Martingales

If one is asked why a certain event is random then often will be the answer that the event be “unpredictable”. In particular, an $\omega$-word $\xi = x_1x_2\cdots$ should be random if one cannot win by betting on its digits given other (previous) digits. For automata this yields the following.

**Definition 1 (Betting automaton).** $\mathcal{A} = (X, Q, \mathbb{R}_{\ge 0}, q_0, \delta, \nu)$ is a finite betting automaton : $\iff$

1. $(X, Q, q_0, \delta)$ is a finite automaton (without final states) and

2. $\nu: Q \times X \to \mathbb{R}_{\ge 0}$ and $\sum_{x \in X} \nu(q, x) \le 1$, for all $q \in Q$.

The automaton starts with capital $V_A(e) = 1$. After the history $w \in X^*$ its capital is $V_A(w)$ and the automaton bets $\nu(\delta(q_0, w), x) \cdot V_A(w)$ on every $x$ as the outcome of the next digit. Its reward is $r \cdot \nu(\delta(q_0, w), x) \cdot V_A(w)$ ($r = |X|$) for the next digit $x$. This results in the following capital function (or martingale).

$$ 
\begin{aligned}
V_A(e) &:= 1, \text{ and} \\
V_A wx &:= r \cdot \nu(\delta(q_0, w), x) \cdot V_A(w)
\end{aligned}
\qquad (1) 
$$

In order to formulate the main result we need still the following notion.
**Definition 2 (Borel normal ω-word).** An ω-word $\xi \in X^\omega$ is Borel normal iff every subword (infix) $w \in X^*$ appears with the same frequency:

$$ \forall w \left( \lim_{n \to \infty} \frac{|\{i : i \le n \wedge \xi[0..i] \in X^* \cdot w\}|}{n} \right) = r^{-|w|} $$

Then Schnorr and Stimm [17] proved the following characterisation of ω-words random w.r.t. finite betting automata.

**Theorem 1 ([17]).** If $\xi \in X^\omega$ is Borel normal then for every finite automaton $\mathcal{A}$ it holds

1. $\forall^\infty n(n \in \mathbb{N} \to \mathcal{V}_A(\xi[0..n]) = \mathcal{V}_A(\xi[0..n+1]))$, or

2. $\exists \gamma(0 > \gamma \wedge \forall^\infty n(n \in \mathbb{N} \to \mathcal{V}_A(\xi[0..n]) \le r^{\gamma \cdot n}))$.

If $\xi \in X^\omega$ is not Borel normal then there are a finite automaton $\mathcal{A}$ and $\gamma > 0$ such that

3. $\exists^\infty n(n \in \mathbb{N} \to \mathcal{V}_A(\xi[0..n]) \ge r^{\gamma \cdot n})$.

Other recent approaches to relate Borel normality to finite automata can be found e.g. in [2,3] or [20].

# 4 Finite-State Dimension

Next we turn to aspects of partial randomness via automaton definable martingales $\mathcal{V}_A$. Finite-state dimension may be seen as the estimate of the maximally achievable exponent $\gamma$ in Theorem 1.3. To this end we define for a betting automaton $\mathcal{A}$ and a non-empty subset $F \subseteq X^\omega$

$$ \alpha_A(F) := \sup \left\{ \alpha : \forall \xi (\xi \in F \to \limsup_{n \to \infty} \frac{\mathcal{V}_A(\xi[0..n])}{r^{(1-\alpha) \cdot n}} > 0) \right\} \quad (2) $$

Observe that $1 - \alpha$ corresponds to the exponent $\gamma$.

Then the finite-state dimension of $F$ is obtained as

$$ \dim_{\mathrm{FS}}(F) := \sup \{ \alpha_A(F) : \mathcal{A} \text{ is a finite automaton} \} \quad (3) $$

In this definition we followed Schnorr's approach via martingales and order functions (cf. [26]) rather than the one by s-gales in [6]. If we replace $\limsup$ in Eq. (2) by $\liminf$ we obtain the so called strong finite-state dimension which has similar properties [7].

As an immediate consequence of Theorem 1 we obtain that $\dim_{\mathrm{FS}}(\xi) = 1$ if and only if $\xi$ is Borel normal. One possibility to obtain ω-words of smaller finite-state dimension is by dilution (inserting blocks of zeros) of Borel normal ones. In this way one proves

**Lemma 1 ([6, Lemma 6.5]).** For every rational number $t \in \mathbb{Q} \cap [0, 1]$ there is an ω-word $\xi$ such that $\dim_{\mathrm{FS}}(\xi) = t$.
The papers [4,6,7] give several equivalent definitions of finite-state dimension in terms of information-lossless compression by finite-state machines, by log-loss rates of continuous measures<fnref n="1" /> on $X^*$, or by block-entropy rates.

Combining the results of [6] with the ones of [18,19] in [8] it was observed that finite-state dimension has also a characterisation via decompression by transducers.

**Definition 3 (Finite transducer).** $\mathcal{M} = (X, Y, Q, q_0, \delta, \lambda)$ is a generalised sequential machine (or finite transducer) if and only if $(X, Q, q_0, \delta)$ is a finite automaton without final states, $Y$ is an alphabet and $\lambda: Q \times X \to Y^*$

The transducer realises a prefix monotone mapping $\varphi: X^* \to Y^*$ in the following way:

$$ \varphi(e) := e, \text{ and } \varphi wx := \varphi(w) \cdot \lambda(\delta(q_0, w), x) $$

This mapping can be extended to $\omega$-words via $\text{pref}(\bar{\varphi}(\eta)) = \text{pref}(\varphi(\text{pref}(\eta)))$, that is, $\bar{\varphi}(\eta) := \lim_{v \to \eta} \varphi(v)$.

We define the decompression rate $\vartheta_{\mathcal{M}}(\eta)$ along an input $\eta$ as follows.

**Definition 4 (Decompression along an input).**

$$ \vartheta_{\mathcal{M}}(\eta) := \liminf_{n \to \infty} \frac{n}{|\varphi(\eta[0..n])|}, $$

where $\mathcal{M}$ is a finite transducer and $\varphi$ its related mapping.

As the difference $|\varphi wx) - \varphi(w)|$ is bounded, this quantity measures in some sense the asymptotic amount of digits necessary to obtain the first $\ell$ digits of the output.

Then the finite-state dimension of $\xi \in X^\omega$ turns out to be the simultaneous best choice of a transducer $\mathcal{M}$ with a suitable best input $\eta$ generating $\xi = \bar{\varphi}(\eta)$ (cf. [6,8,18,19]).

**Theorem 2.** Consider the class $\mathcal{K}_X$ of transducers $\mathcal{M}$ having output alphabet $Y = X$. Then for all $\xi \in X^\omega$ we have

$$ \dim_{\text{FS}}(\xi) = \inf\{\vartheta_{\mathcal{M}}(\eta) : \mathcal{M} \in \mathcal{K}_X \wedge \eta \in X^\omega \wedge \xi = \bar{\varphi}(\eta)\}. $$

We conclude this section by presenting a connection between the finite-state dimension of some set $F \subseteq X^\omega$ and the entropy of regular languages $W$ containing $\text{pref}(F)$ [4, Theorem 3.5].

The entropy (or entropy rate) $H_W$ of a language $W \subseteq X^*$ is defined as [4,22]

$$ H_W := \limsup_{n \to \infty} \frac{\log_r(1 + |W \cap X^n|)}{n}, \quad (4) $$

The entropy is monotone and stable, that is, $H_{W \cup V} = \max\{H_W, H_V\}$. It should be mentioned that $H_W = H_{\text{pref}(W)} = H_{\text{infix}(W)}$, for regular languages.

**Theorem 3 ([4]).** $\dim_{\text{FS}}(F) \le \inf\{H_W : \text{pref}(F) \subseteq W \wedge W \text{ is regular}\}$

<footnote n="1">¹ These measures were called predictors in [4].</footnote>
# 5 Automaton Definable Null Sets

We start this section with introducing $\omega$-languages definable by finite automata. For more background see the books [15,28] or the surveys [23,27].

Let $\mathcal{B} = (X, Q, \Delta, q_0, Q')$ be a non-deterministic (Büchi-)automaton. Then the sequence $(q_i, \xi(i+1), q_{i+1})_{i \in \mathbb{N}}$ is a run of $\mathcal{B}$ on the $\omega$-word $\xi = \xi(1) \cdot \xi(2) \cdots$ provided $(q_i, \xi(i+1), q_{i+1}) \in \Delta$ for all $i \in \mathbb{N}$. A run is called *successful* if infinitely many of the $q_i$ are in the set of final states $Q'$.

The $\omega$-language $L_{\omega}(\mathcal{B})$ defined by $\mathcal{B}$ is then

$$L_{\omega}(\mathcal{B}) = \{\xi : \xi \in X^{\omega} \wedge \text{ there is a successful run of } \mathcal{B} \text{ on } \xi\}.$$

**Definition 5 (Regular $\omega$-language).** An $\omega$-language $F \subseteq X^{\omega}$ is called regular if and only if $F$ is accepted by a finite automaton

The following properties of the class of regular (automaton definable) $\omega$-languages are well-known.

**Theorem 4.** 1. An $\omega$-language $F \subseteq X^{\omega}$ is regular if and only if there are an $n \in \mathbb{N}$ and regular languages $W_i, V_i \subseteq X^*$, $i \le n$, such that $F = \bigcup_{i=1}^n W_i \cdot V_i^{\omega}$.

2. The set of regular $\omega$-languages over $X$ is closed under Boolean operations.

3. If $F \subseteq X^{\omega}$ is regular then $\mathbf{pref}(F)$ and $\mathbf{infix}(F)$ are regular languages.

**Theorem 5.** Let $\mathcal{DB}$ be the class of $\omega$-languages accepted by deterministic Büchi automata. Then

1. $\mathcal{DB}$ is a proper subclass of the class of regular $\omega$-languages, and

2. $\mathcal{DB}$ is closed under union and intersection but not under complementation.

3. If $W \subseteq X^*$ is a regular language then $\{\xi : \xi \in X^* \wedge \mathbf{pref}(\xi) \subseteq W\} \in \mathcal{DB}$ and $\{\xi : \xi \in X^* \wedge |\mathbf{pref}(\xi) \cap W| = \infty\} \in \mathcal{DB}$.

As measure on the space $X^\omega$ we use the usual product measure $\mu$ defined by its values on the cylinder sets $\mu(w \cdot X^\omega) := r^{-|w|}$. Then in [21,24] the following characterisation of regular null sets via “forbidden subwords” is proved.

**Theorem 6.** Let $F$ be a regular $\omega$-language.

1. If $F \in \mathcal{DB}$ then $\mu(F) = 0$ if and only if there is word $w \in X^*$ such that $F \subseteq X^* \setminus X^* \cdot w \cdot X^*$.

2. $\mu(F) = 0$ if and only if $F \subseteq \bigcup_{w \in X^*} X^* \setminus X^* \cdot w \cdot X^*$.

*Remark 1.* Theorem 6 holds for a much larger class of finite measures on $X^\omega$ including all non-degenerated product measures on $X^\omega$ (cf. [21,24,29,30]).

Now we can characterise those $\omega$-words which are not contained in a regular $\omega$-language of measure zero.

**Definition 6 (Disjunctivity).** An $\omega$-word $\xi \in X^\omega$ is called disjunctive (or rich or saturated) if and only if it contains every word $w \in X^*$ as subword (infix).
Consequently, $\omega$-words random w.r.t. finite automata in the sense of the measure theoretic approach are exactly the disjunctive ones. This allows us to compare both of the presented approaches of randomness.

**Proposition 1.** Every Borel normal $\omega$-word is disjunctive, but there are disjunctive $\omega$-words which are not Borel normal, e.g. the $\omega$-word $\zeta := \prod_{w \in X^*} 0^{|w|}$. w.

# 6 Subword Complexity

The characterisation via “forbidden subwords” enables us to derive a notion of partial randomness similar to the finite-state dimension. To this end we use the entropy of languages defined in Eq. (4) and define for arbitrary $P \subseteq X^* \cup X^\omega$

**Definition 7 (Subword complexity).**

$$ \tau(P) := H_{\text{infix}(P)} $$

In view of the inequality $\text{infix}(P) \cap X^{n+m} \subseteq (\text{infix}(P) \cap X^n) \cdot (\text{infix}(P) \cap X^m)$ which holds for $\text{infix}(P)$ the limit in Eq. (4) exists and equals

$$ \tau(P) = \inf \left\{ \frac{\log_r(1 + |\text{infix}(P) \cap X^n|)}{n} : n \in \mathbb{N} \right\}. $$

This value is also known as factor complexity in automata theory and topological entropy in symbolic dynamics.

The following is clear.

**Proposition 2.** $0 \le \tau(\xi) \le 1$ and an $\omega$-word $\xi \in X^\omega$ is disjunctive if and only if $\tau(\xi) = 1$.

For subword complexity one has for every possible value an $\omega$-word of exactly this complexity [12].

**Theorem 7.** For every $t, 0 \le t \le 1$, there is a $\xi \in X^\omega$ such that $\tau(\xi) = t$.

Similar to Eq. (5.1.2) of [22] one can derive the following identity.

$$ \tau(P) = \inf\{H_W : W \subseteq X^* \wedge \text{infix}(P) \subseteq W \wedge W \text{ is regular}\} \quad (5) $$

Now Theorem 3 yields the following relation to finite-state dimension.

$$ \tau(F) \le \dim_{\text{FS}} F \quad (6) $$

For regular $\omega$-languages $F \subseteq X^\omega$ we have identity in Eq. (6).

**Proposition 3.** If $F \subseteq X^\omega$ is regular then $\tau(F) = \dim_{\text{FS}} F$.

*Proof.* Here $\text{infix}(F)$ is a regular language appearing in the right hand side of the inequality of Theorem 3.
# 7 Predicting Finite Automata

A further feature of randomness of an $ω$-word $\xi$, similar to the one mentioned for betting automata, is the impossibility of the exact prediction of the next symbol. Here Tadaki [25] proposed the following.

**Definition 8 (Predicting automaton).** A transducer $\mathcal{A} = (X, X, Q, q_0, \delta, \lambda)$ is referred to as a predicting automaton if $\lambda: Q \to \{e\} \cup X$ is a labelling of states.

**Definition 9 (Prediction).** A predicting automaton $\mathcal{A} = (X, X, Q, q_0, \delta, \lambda)$ strongly predicts $\xi \in X^\omega$ if and only if

1. $\lambda(\delta(q_0, \xi[0..n-1])) = \xi(n)$ for infinitely many $n \in \mathbb{N}$, and

2. if $\lambda(\delta(q_0, \xi[0..n-1])) \neq \xi(n)$ then $\lambda(\delta(q_0, \xi[0..n-1])) = e$.

Definition 9 is a strong requirement, it forces the automaton to make on input $\xi$ infinitely many correct predictions and no incorrect ones. Here using the label $\lambda(q) = e$ the automaton may skip. Nevertheless, in the binary case $X = \{0,1\}$ we have the following.

**Theorem 8.** 1. Let $\mathcal{A} = (\{0,1\}, \{0,1\}, Q, q_0, \delta, \lambda)$ be a binary predicting automaton. If $\mathcal{A}$ strongly predicts $\xi \in \{0,1\}^\omega$ then $\xi$ is not disjunctive.

2. If $\xi \in \{0,1\}^\omega$ is disjunctive then no predicting automaton predicts $\xi$.

This theorem does not hold in the other cases when $|X| \ge 3$. Here we have to turn to “negative” prediction. We say that $\mathcal{A}$ weakly predicts $\xi$ provided $\lambda(\delta(q_0, \xi[0..n-1])) \neq \xi(n)$ for infinitely many $n \in \mathbb{N}$ and $\lambda(\delta(q_0, \xi[0..n-1])) = e$ otherwise. Then we have.

**Theorem 9.** 1. Let $\mathcal{A} = (X, X, Q, q_0, \delta, \lambda)$ be a binary predicting automaton. If $\mathcal{A}$ weakly predicts $\xi \in X^\omega$ then $\xi$ is not disjunctive.

2. If $\xi \in X^\omega$ is disjunctive then no predicting automaton weakly predicts $\xi$.

# 8 Finite-State Genericity

This section reviews some connections between disjunctivity and finite-state genericity. As in [1] we define the following.

**Definition 10.** Let $\xi \in X^\omega$.

1. $\xi$ meets a function $\psi: X^* \to X^*$ if $w \cdot \psi(w) \subseteq \xi$.

2. $\xi$ is finite-state generic if $\xi$ meets every function $\varphi$ realised by a finite transducer.

This can be interpreted in terms of the usual product topology on $X^\omega$ which can be defined by the metric $\rho(\xi, \eta) := \sup\{r^{-n} : \xi(n) \neq \eta(n)\}$ where we agree on $\sup\emptyset = 0$. The cylinder sets $w \cdot X^\omega$ are simultaneously open and closed balls of diameter $r^{-|w|}$. The closure $C(F)$ of (smallest closed set containing) a set $F \subseteq X^\omega$ obtains as $C(F) = \{\xi : \text{pref}(\xi) \subseteq \text{pref}(F)\}$.
A subset $F$ is nowhere dense if its closure does not contain a non-empty open subset, that is, for every $w \in \mathbf{pref}(F)$ there is a continuation $v \in X^*$ such that $w \cdot v \cdot X^* \cap F = \emptyset$, that is “$v$ leads $w$ to a hole” in $F$.

Then Definition 10.2 gives an indication that finite-state generic $\omega$-words avoid “finite-state nowhere dense” subsets of $X^*$. This is shown by Theorem 4.4 of [1].

**Theorem 10 ([1]).** An $\omega$-word $\xi$ is disjunctive if and only if it is finite-state generic.

Theorem 10 fits into the more general coincidence of measure and category for regular $\omega$-languages depicted in Figure 1 (see [21,24,29,30]). In the general case, however, the monograph [14] shows that measure and category (topological density) are two concepts which do no coincide.

<table><caption>**Fig. 1.** Coincidence of measure and category for regular $\omega$-languages</caption><thead><tr><th></th><th>Measure</th><th>Category (Density)</th></tr></thead><tbody><tr><td>very large</td><td>$\mu(F) = \mu(X^*)$</td><td>$F$ is residual (co-meagre)</td></tr><tr><td>large</td><td>$\mu(F) \neq 0$</td><td>$F$ is of 2<sup>nd</sup> BAIRE category</td></tr><tr><td>small</td><td>$\mu(F) = 0$</td><td>$F$ is of 1<sup>st</sup> BAIRE category (meagre)</td></tr><tr><td>very small</td><td>$\mu(C(F)) = 0$</td><td>$F$ is nowhere dense</td></tr></tbody></table>

As usual a subset $F$ is *meagre* or of *first Baire category* if it is an at most countable union of nowhere dense sets, a set is of *second Baire category* if it is not meagre, and it is *residual* if its complement is meagre. The first column of Figure 1 presents a comparison of the sizes of $F \subseteq X^*$, and the rows indicate that for regular $\omega$-languages $F \subseteq X^*$ properties of the same row coincide, e.g. $\mu(F) = 0$ iff $F$ is meagre.

## References

1. Ambos-Spies, K., Busse, E.: Automatic forcing and genericity: On the diagonalization strength of finite automata. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) Discrete mathematics and theoretical computer science. 4th international conference, DMTCS 2003, Dijon, France, July 7–12, 2003. Proceedings, pp. 97–108. Berlin: Springer (2003)

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

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

4. Bourke, C., Hitchcock, J.M., Vinodchandran, N.: Entropy rates and finite-state dimension. Theor. Comput. Sci. 349(3), 392–406 (2005)
5. Calude, C.S.: Information and randomness. Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, second edn. (2002), http://dx.doi.org/10.1007/978-3-662-04978-5, an algorithmic perspective, With forewords by Gregory J. Chaitin and Arto Salomaa

6. Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310(1-3), 1-33 (2004)

7. Doty, D., Lutz, J.H., Nandakumar, S.: Finite-state dimension and real arithmetic. Inf. Comput. 205(11), 1640-1651 (2007)

8. Doty, D., Moser, P.: Finite-state dimension and lossy decompressors. CoRR abs/cs/0609096 (2006), http://arxiv.org/abs/cs/0609096

9. Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Theory and Applications of Computability, Springer-Verlag, New York (2010)

10. Li, M., Vitányi, P.M.B.: An introduction to Kolmogorov complexity and its applications. Texts and Monographs in Computer Science, Springer (1993), http://dx.doi.org/10.1007/978-1-4757-3860-5

11. Martin-Löf, P.: The definition of random sequences. Inf. Control 9, 602-619 (1966)

12. Moldagaliyev, B., Staiger, L., Stephan, F.: On the values for factor complexity (2018), to appear

13. Nies, A.: Computability and randomness, Oxford Logic Guides, vol. 51. Oxford University Press, Oxford (2009), http://dx.doi.org/10.1093/acprof:oso/9780199230761.001.0001

14. Oxtoby, J.C.: Measure and category, Graduate Texts in Mathematics, vol. 2. Springer-Verlag, New York-Berlin, second edn. (1980), a survey of the analogies between topological and measure spaces

15. Perrin, D., Pin, J.E.: Infinite words. Automata, semigroups, logic and games. Amsterdam: Elsevier/Academic Press (2004)

16. Schnorr, C.P.: Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitsstheorie. Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin (1971)

17. Schnorr, C.P., Stimm, H.: Endliche Automaten und Zufallsfolgen. Acta Inf. 1, 345-359 (1972)

18. Sheinwald, D., Lempel, A., Ziv, J.: On compression with two-way head machines. In: Storer, J.A., Reif, J.H. (eds.) Proceedings of the IEEE Data Compression Conference, DCC 1991, Snowbird, Utah, April 8-11, 1991. pp. 218-227. IEEE Computer Society (1991), https://doi.org/10.1109/DCC.1991.213359

19. Sheinwald, D., Lempel, A., Ziv, J.: On encoding and decoding with two-way head machines. Inf. Comput. 116(1), 128-133 (1995)

20. Shen, A.: Automatic Kolmogorov complexity and normality revisited. In: Klasing, R., Zeitoun, M. (eds.) Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10472, pp. 418-430. Springer (2017), https://doi.org/10.1007/978-3-662-55751-8-33

21. Staiger, L.: Reguläre Nullmengen. Elektron. Informationsverarbeit. Kybernetik 12(6), 307-311 (1976)

22. Staiger, L.: Kolmogorov complexity and Hausdorff dimension. Inform. and Comput. 103(2), 159-194 (1993), http://dx.doi.org/10.1006/inco.1993.1017

23. Staiger, L.: ω-languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 339-387. Springer-Verlag, Berlin (1997), beyond words

24. Staiger, L.: Rich ω-words and monadic second-order arithmetic. In: Nielsen, M., Thomas, W. (eds.) Computer science logic (Aarhus, 1997), Lecture Notes
in Computer Science, vol. 1414, pp. 478-490. Springer-Verlag, Berlin (1998), http://dx.doi.org/10.1007/BFb0028032, selected papers from the 11th International Workshop (CSL '97) held at the 6th Annual Conference of the European Association for Computer Science Logic (EACSL) at the University of Aarhus, Aarhus, August 23-29, 1997

25. Tadaki, K.: Phase transition and strong predictability. In: Ibarra, O.H., Kari, L., Kopecki, S. (eds.) Unconventional computation and natural computation. 13th international conference, UCNC 2014, London, ON, Canada, July 14-18, 2014. Proceedings, pp. 340-352. Cham: Springer (2014)

26. Terwijn, S.A.: Complexity and randomness. Rend. Semin. Mat., Torino 62(1), 1-37 (2004)

27. Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (ed.) Handbook of theoretical computer science, Vol. B, pp. 133-191. Elsevier, Amsterdam (1990), formal models and semantics

28. Trakhtenbrot, B.A., Barzdiń, Y.M.: Finite automata. North-Holland Publishing Co., Amsterdam (1973), behavior and synthesis, Translated from the Russian by D. Louvish, English translation edited by E. Shamir and L. H. Landweber, Fundamental Studies in Computer Science, Vol. 1

29. Varacca, D., Völzer, H.: Temporal logics and model checking for fairly correct systems. In: 21st IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings. pp. 389-398. IEEE Computer Society (2006), http://dx.doi.org/10.1109/LICS.2006.49

30. Völzer, H., Varacca, D.: Defining fairness in reactive and concurrent systems. J. ACM 59(3), Art. 13, 37 (2012), http://dx.doi.org/10.1145/2220357.2220360