Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Normality and two-way automata
Autor:Carton, O.; Heiber, P.A.
Filiación:Laboratoire d'Informatique Algorithmique: Fondements et Applications, CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014, Paris Cedex 13, 75205, France
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, Buenos Aires, 1428, Argentina
Palabras clave: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
Año:2015
Volumen:241
Página de inicio:264
Página de fin:276
DOI: http://dx.doi.org/10.1016/j.ic.2015.02.001
Título revista:Information and Computation
Título revista abreviado:Inf Comput
ISSN:08905401
CODEN:INFCE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08905401_v241_n_p264_Carton

Referencias:

  • Aho, A.V., Hopcroft, J.E., Ullman, J.D., A general theory of translation (1969) Math. Syst. Theory, 3, pp. 193-221
  • Alur, R., Cerný, P., Expressiveness of streaming string transducers (2010) LIPIcs, 8, pp. 1-12. , FSTTCS, Leibniz-Zentrum für Informatik Schloss Dagstuhl
  • Becher, V., Carton, O., Heiber, P.A., (2013) Normality and Automata, , http://www.dc.uba.ar/people/profesores/becher/na.pdf, Preprint
  • Becher, V., Heiber, P.A., Normal numbers and finite automata (2013) Theor. Comput. Sci., 477, pp. 109-116
  • Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rend. Circ. Mat. Palermo, 27, pp. 247-271
  • Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Series: Cambridge Tracts in Mathematics, 193. , Cambridge University Press
  • Dai, J., Lathrop, J., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theor. Comput. Sci., 310, pp. 1-33
  • Engelfriet, J., Hoogeboom, H.J., MSO definable string transductions and two-way finite-state transducers (2001) ACM Trans. Comput. Log., 2 (2), pp. 216-254
  • Gurari, E.M., The equivalence problem for deterministic two-way sequential transducers is decidable (1982) SIAM J. Comput., 11 (3), pp. 448-452
  • Culik, K., II, Karhumäki, J., The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable (1987) SIAM J. Comput., 16 (2), pp. 221-230
  • Merkle, W., Reimann, J., Selection functions that do not preserve normality (2006) Theory Comput. Syst., 39 (5), pp. 685-697
  • Perrin, D., Pin, J.-É., (2004) Infinite Words, , Elsevier
  • Schnorr, C.P., Stimm, H., Endliche Automaten und Zufallsfolgen (1972) Acta Inform., 1, pp. 345-359

Citas:

---------- APA ----------
Carton, O. & Heiber, P.A. (2015) . Normality and two-way automata. Information and Computation, 241, 264-276.
http://dx.doi.org/10.1016/j.ic.2015.02.001
---------- CHICAGO ----------
Carton, O., Heiber, P.A. "Normality and two-way automata" . Information and Computation 241 (2015) : 264-276.
http://dx.doi.org/10.1016/j.ic.2015.02.001
---------- MLA ----------
Carton, O., Heiber, P.A. "Normality and two-way automata" . Information and Computation, vol. 241, 2015, pp. 264-276.
http://dx.doi.org/10.1016/j.ic.2015.02.001
---------- VANCOUVER ----------
Carton, O., Heiber, P.A. Normality and two-way automata. Inf Comput. 2015;241:264-276.
http://dx.doi.org/10.1016/j.ic.2015.02.001