Normality and Automata

BECHER, VERÓNICA; CARTÓN, OLIVIER; HEIBER, PABLO ARIEL

JOURNAL OF COMPUTER AND SYSTEM SCIENCES

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2015 vol. 81 p. 1592 - 1613

0022-0000

We prove that finite-state transducers with injective behavior, deterministic or not, real-time or not, with no extra memory or a single counter, cannot compress any normal word. We exhaust all combinations of determinism, real-time, and additional memory in the form of counters or stacks, identifying which models can compress normal words. The case of deterministic push-down transducers is the only one still open. We also present results on the preservation of normality by selection with finite automata. Complementing Agafonov´s theorem for prefix selection, we show that suffix selection preserves normality. However, there are simple two-sided selection rules that do not.