Normality and two-way automata

We prove that two-way transducers (both deterministic and non-deterministic) cannot compress normal numbers. To achieve this, we first show that it is possible to generalize compressibility from one-way transducers to two-way transducers. These results extend a known result: normal infinite words ar...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Heiber, Pablo Ariel
Publicado: 2015
Materias:
Compression
Normal numbers
Two-way automata
Automata theory
Compaction
Number theory
Finite state transducers
Infinite word
Lossless
Two-way transducers
Unbounded memory
Transducers
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08905401_v241_n_p264_Carton
http://hdl.handle.net/20.500.12110/paper_08905401_v241_n_p264_Carton
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_08905401_v241_n_p264_Carton
record_format dspace
spelling paper:paper_08905401_v241_n_p264_Carton2023-06-08T15:47:06Z Normality and two-way automata Heiber, Pablo Ariel Compression Normal numbers Two-way automata Automata theory Compaction Number theory Finite state transducers Infinite word Lossless Normal numbers Two-way automata Two-way transducers Unbounded memory Transducers We prove that two-way transducers (both deterministic and non-deterministic) cannot compress normal numbers. To achieve this, we first show that it is possible to generalize compressibility from one-way transducers to two-way transducers. These results extend a known result: normal infinite words are exactly those that cannot be compressed by lossless finite-state transducers, and, more generally, by bounded-to-one non-deterministic finite-state transducers. We also argue that such a generalization cannot be extended to two-way transducers with unbounded memory, even in the simple form of a single counter. © 2015 Elsevier Inc. All rights reserved. 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_08905401_v241_n_p264_Carton http://hdl.handle.net/20.500.12110/paper_08905401_v241_n_p264_Carton
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Compression
Normal numbers
Two-way automata
Automata theory
Compaction
Number theory
Finite state transducers
Infinite word
Lossless
Normal numbers
Two-way automata
Two-way transducers
Unbounded memory
Transducers
spellingShingle Compression
Normal numbers
Two-way automata
Automata theory
Compaction
Number theory
Finite state transducers
Infinite word
Lossless
Normal numbers
Two-way automata
Two-way transducers
Unbounded memory
Transducers
Heiber, Pablo Ariel
Normality and two-way automata
topic_facet Compression
Normal numbers
Two-way automata
Automata theory
Compaction
Number theory
Finite state transducers
Infinite word
Lossless
Normal numbers
Two-way automata
Two-way transducers
Unbounded memory
Transducers
description We prove that two-way transducers (both deterministic and non-deterministic) cannot compress normal numbers. To achieve this, we first show that it is possible to generalize compressibility from one-way transducers to two-way transducers. These results extend a known result: normal infinite words are exactly those that cannot be compressed by lossless finite-state transducers, and, more generally, by bounded-to-one non-deterministic finite-state transducers. We also argue that such a generalization cannot be extended to two-way transducers with unbounded memory, even in the simple form of a single counter. © 2015 Elsevier Inc. All rights reserved.
author Heiber, Pablo Ariel
author_facet Heiber, Pablo Ariel
author_sort Heiber, Pablo Ariel
title Normality and two-way automata
title_short Normality and two-way automata
title_full Normality and two-way automata
title_fullStr Normality and two-way automata
title_full_unstemmed Normality and two-way automata
title_sort normality and two-way automata
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08905401_v241_n_p264_Carton
http://hdl.handle.net/20.500.12110/paper_08905401_v241_n_p264_Carton
work_keys_str_mv AT heiberpabloariel normalityandtwowayautomata
_version_ 1768544090796851200

Ejemplares similares