Normality and automata

作者：

Highlights：

• We prove a non-real-time 1-counter transducers cannot compress any normal number.

• We prove a real-time k-counter transducers cannot compress any normal number.

• We prove there exist pushdown transducers that can compress a normal number.

• We prove normality is preserved by suffix selection by finite automata.

摘要

•We prove a non-real-time 1-counter transducers cannot compress any normal number.•We prove a real-time k-counter transducers cannot compress any normal number.•We prove there exist pushdown transducers that can compress a normal number.•We prove normality is preserved by suffix selection by finite automata.

论文关键词：Normal numbers,Finite automata,Non-deterministic automata

论文评审过程：Received 5 May 2014, Revised 5 March 2015, Accepted 30 April 2015, Available online 10 June 2015, Version of Record 25 August 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.04.007