Normality and automata

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, identifyi...

Descripción completa

Detalles Bibliográficos
Autores principales:	Becher, Verónica Andrea, Heiber, Pablo Ariel
Publicado:	2015
Materias:	Finite automata Non-deterministic automata Normal numbers Number theory Transducers Finite state transducers Nondeterministic automata Real time Selection Rules
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n8_p1592_Becher http://hdl.handle.net/20.500.12110/paper_00220000_v81_n8_p1592_Becher
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00220000_v81_n8_p1592_Becher
record_format	dspace
spelling	paper:paper_00220000_v81_n8_p1592_Becher2023-06-08T14:45:03Z Normality and automata Becher, Verónica Andrea Heiber, Pablo Ariel Finite automata Non-deterministic automata Normal numbers Number theory Transducers Finite state transducers Nondeterministic automata Normal numbers Real time Selection Rules Finite automata 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. © 2015 Elsevier Inc. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Heiber, P.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n8_p1592_Becher http://hdl.handle.net/20.500.12110/paper_00220000_v81_n8_p1592_Becher
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Finite automata Non-deterministic automata Normal numbers Number theory Transducers Finite state transducers Nondeterministic automata Normal numbers Real time Selection Rules Finite automata
spellingShingle	Finite automata Non-deterministic automata Normal numbers Number theory Transducers Finite state transducers Nondeterministic automata Normal numbers Real time Selection Rules Finite automata Becher, Verónica Andrea Heiber, Pablo Ariel Normality and automata
topic_facet	Finite automata Non-deterministic automata Normal numbers Number theory Transducers Finite state transducers Nondeterministic automata Normal numbers Real time Selection Rules Finite automata
description	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. © 2015 Elsevier Inc.
author	Becher, Verónica Andrea Heiber, Pablo Ariel
author_facet	Becher, Verónica Andrea Heiber, Pablo Ariel
author_sort	Becher, Verónica Andrea
title	Normality and automata
title_short	Normality and automata
title_full	Normality and automata
title_fullStr	Normality and automata
title_full_unstemmed	Normality and automata
title_sort	normality and automata
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n8_p1592_Becher http://hdl.handle.net/20.500.12110/paper_00220000_v81_n8_p1592_Becher
work_keys_str_mv	AT becherveronicaandrea normalityandautomata AT heiberpabloariel normalityandautomata
_version_	1768545770865164288

Normality and automata

Ejemplares similares