# zbMATH — the first resource for mathematics

New coins from old: Computing with unknown bias. (English) Zbl 1099.68052
For a word $$w$$ over $$\{0,1\}$$ and for a real $$p\in (0,1)$$, let $$\mathbf P_p(w)=p^{n_1(w)}(1-p)^{n_0(w)}$$ where $$n_i(w)$$ is the number of occurrences of $$i$$ in $$w$$ for $$i=0,1$$. For a language $$L$$ over $$\{0,1\}$$, let $$\mathbf P_p(L)=\sum_{w\in L}\mathbf P_p(w)$$. A pair $$(L_0,L_1)$$ of disjoint prefix-free languages over $$\{0,1\}$$ simulates a function $$f:\mathcal D\to(0,1)$$ where $$\mathcal D\subseteq (0,1)$$ if $$\mathbf P_p(L_ 0\cup L_1)=1$$ and $$\mathbf P_p(L_1)=f(p)$$ for all $$p\in \mathcal D$$. An automaton $$\mathcal A$$ simulates $$(L_0,L_1)$$ if there exist disjoint sets $$A_0$$ and $$A_1$$ of states such that $$\mathcal A$$ with a final set $$A_i$$ accepts $$L_i$$ for $$i=0,1$$. We say that a simulation $$(L_0,L_1)$$ of $$f$$ is a block simulation if there exist a positive integer $$k$$ and disjoint sets $$A_0,A_1\subseteq \{0,1\}^k$$ with $$L_i=(A')^{*}A_i$$ for $$i=0,1$$ where $$A'=\{0,1\}^k\setminus (A_0\cup A_1)$$. It is proved that for a function $$f:\mathcal D \to(0,1)$$ where $$\mathcal D\subseteq (0,1)$$ the following are equivalent: 1) $$f$$ can be block simulated, 2) $$f$$ can be simulated via a finite automaton, 3) $$f$$ is a restriction of a rational function over $$\mathbb Q$$. If $$f$$ can be simulated via a pushdown automaton then $$f$$ is a restriction of an algebraic function over $$\mathbb Q$$. Several examples and open problems are presented.

##### MSC:
 68Q45 Formal languages and automata 68Q70 Algebraic theory of languages and automata
Full Text: