Navegar

Colección

Datos Estadísticas

Artículo

Becher, V.; Carton, O.; Heiber, P.A. "Normality and automata" (2015) Journal of Computer and System Sciences. 81(8):1592-1613
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 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.

Registro:

Documento: Artículo
Título:Normality and automata
Autor:Becher, V.; Carton, O.; Heiber, P.A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I, Buenos Aires, 1428, Argentina
CONICET, Argentina
Laboratoire d'Informatique Algorithmique: Fondements et Applications, CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014, Paris Cedex 13, 75205, France
Palabras clave:Finite automata; Non-deterministic automata; Normal numbers; Number theory; Transducers; Finite state transducers; Nondeterministic automata; Normal numbers; Real time; Selection Rules; Finite automata
Año:2015
Volumen:81
Número:8
Página de inicio:1592
Página de fin:1613
DOI: http://dx.doi.org/10.1016/j.jcss.2015.04.007
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v81_n8_p1592_Becher

Referencias:

  • Agafonov, V.N., Normal sequences and finite automata (1968) Sov. Math. Dokl., 9, pp. 324-325
  • Béal, M.-P., Carton, O., Determinization of transducers over infinite words: The general case (2004) Theory Comput. Syst., 37 (4), pp. 483-502
  • 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
  • Broglio, A., Liardet, P., Predictions with automata. Symbolic dynamics and its applications (1992) Contemp. Math., 135, pp. 111-124. , Also in Proceedings AMS Conference in Honor of R.L. Adler. New Haven CT, USA, 1991
  • Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Cambridge Tracts in Mathematics, 193. , Cambridge University Press
  • Carton, O., Heiber, P.A., Normality and two-way automata (2015) Inf. Comput., 241, pp. 264-276
  • Carton, O., Michel, M., Unambiguous Büchi automata (2003) Theor. Comput. Sci., 297, pp. 37-81
  • Champernowne, D.G., The construction of decimals normal in the scale of ten (1933) J. Lond. Math. Soc., 8, pp. 254-260
  • Dai, J., Lathrop, J., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theor. Comput. Sci., 310, pp. 1-33
  • Kuipers, L., Niederreiter, H., (1974) Uniform Distribution of Sequences, , John Wiley & Sons New York
  • Merkle, W., Reimann, J., Selection functions that do not preserve normality (2006) Theory Comput. Syst., 39 (5), pp. 685-697
  • Minsky, M.L., Recursive unsolvability of Post's problem of "tag" and other topics in the theory of Turing machines (1961) Ann. Math., 74, pp. 437-454
  • O'Connor, M.G., An unpredictability approach to finite-state randomness (1988) J. Comput. Syst. Sci., 37 (3), pp. 324-336
  • Perrin, D., Pin, J.-É., (2004) Infinite Words, , Elsevier
  • Sakarovitch, J., (2009) Elements of Automata Theory, , Cambridge University Press
  • Schnorr, C.P., Stimm, H., Endliche Automaten und Zufallsfolgen (1972) Acta Inform., 1, pp. 345-359

Citas:

---------- APA ----------
Becher, V., Carton, O. & Heiber, P.A. (2015) . Normality and automata. Journal of Computer and System Sciences, 81(8), 1592-1613.
http://dx.doi.org/10.1016/j.jcss.2015.04.007
---------- CHICAGO ----------
Becher, V., Carton, O., Heiber, P.A. "Normality and automata" . Journal of Computer and System Sciences 81, no. 8 (2015) : 1592-1613.
http://dx.doi.org/10.1016/j.jcss.2015.04.007
---------- MLA ----------
Becher, V., Carton, O., Heiber, P.A. "Normality and automata" . Journal of Computer and System Sciences, vol. 81, no. 8, 2015, pp. 1592-1613.
http://dx.doi.org/10.1016/j.jcss.2015.04.007
---------- VANCOUVER ----------
Becher, V., Carton, O., Heiber, P.A. Normality and automata. J. Comput. Syst. Sci. 2015;81(8):1592-1613.
http://dx.doi.org/10.1016/j.jcss.2015.04.007