Navegar

Colección

Datos Estadísticas

Artículo

Becher, V.; Carton, O.; Heiber, P.A. "Finite-State Independence" (2018) Theory of Computing Systems. 62(7):1555-1572
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:

In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word x1x2x3… where x2n = xn for every n. This construction has its own interest. © 2017, Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Finite-State Independence
Autor:Becher, V.; Carton, O.; Heiber, P.A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales & ICC, Universidad de Buenos Aires & CONICET, Buenos Aires, Argentina
Institut de Recherche en Informatique Fondamentale, Université Paris Diderot, Paris, France
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & CONICET, Buenos Aires, Argentina
Palabras clave:Finite-state automata; Independence; Infinite sequences; Normal sequences; Computer science; Finite automata; Mathematical techniques; Auxiliary inputs; Finite state; Finite state transducers; Independence; Infinite sequences; Infinite word; Lebesgue measure; Normal sequences; Automata theory
Año:2018
Volumen:62
Número:7
Página de inicio:1555
Página de fin:1572
DOI: http://dx.doi.org/10.1007/s00224-017-9821-6
Título revista:Theory of Computing Systems
Título revista abreviado:Theory Comput. Syst.
ISSN:14324350
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14324350_v62_n7_p1555_Becher

Referencias:

  • Bauwens, B., Shen, A., Takahashi, H., (2016) Conditional Probabilities and Van Lambalgen Theorem Revisited, , Submitted
  • Becher, V., Carton, O., (2017) Normal numbers and computer science, , Berthé, V., Rigó, M., Sequences, Groups, Number Theory, Trends in Mathematics Series, Birkhauser/Springer
  • Becher, V., Carton, O., Heiber, P.A., Normality and automata (2015) J. Comput. Syst. Sci., 81 (8), pp. 1592-1613
  • 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) Rendiconti del Circolo Matematico di Palermo, 27, pp. 247-271
  • Bugeaud, Y., (2012) Distribution Modulo One and Diophantine Approximation. Series: Cambridge Tracts in Mathematics 193, , Cambridge University Press
  • Calude, C.S., Zimand, M., Algorithmically independent sequences (2010) Inf. Comput., 208 (3), pp. 292-308
  • Carton, O., Heiber, P.A., Normality and two-way automata (2015) Inf. Comput., 241, pp. 264-276
  • Dai, J., Lathrop, J., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theor. Comput. Sci., 310, pp. 1-33
  • Downey, R.G., Hirschfeldt, D., (2010) Algorithmic Randomness and Complexity. Theory and Applications of Computability, p. xxvi 855. , Springer, New York, NY
  • Hardy, G.H., Wright, E.M., (2008) An Introduction to the Theory of Numbers, , 6th edn, Oxford University Press
  • Huffman, D., A method for the construction of minimum-redundancy codes (1952) Institute of Radio Engineers, 40 (9), pp. 1098-1101
  • Hyde, K., Kjos-Hanssen, B., Nondeterministic automatic complexity of almost square-free and strongly cube-free words (2014) Computing and Combinatorics: 20Th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings, pp. 61-70. , Cai, Z., Zelikovsky, A., Bourgeois, A., Springer International Publishing, Cham
  • Kautz, S., (1991) Degrees of Random Sets, , PhD Thesis, Cornell University
  • Kuipers, L., Niederreiter, H., (1974) Uniform Distribution of Sequences, , Wiley-Interscience, New York
  • Li, M., Vitanyi, P., (2008) An Introduction to Kolmogorov Complexity and Its Applications, , 3rd edn. Springer Publishing Company, Incorporated
  • Nies, A., (2008) Computability and Randomness, , Clarendon Press
  • 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 Informatica, 1, pp. 345-359
  • Shallit, J., Wang, M., Automatic complexity of strings (2001) J. Autom. Lang. Comb., 6 (4), pp. 537-554
  • Shen, A., Uspensky, V., Vereshchagin, N., (2016) Kolmogorov Complexity and Algorithmic Randomness, , Submitted
  • van Lambalgen, M., Random Sequences (1987) Phd Thesis, University of Amsterdam

Citas:

---------- APA ----------
Becher, V., Carton, O. & Heiber, P.A. (2018) . Finite-State Independence. Theory of Computing Systems, 62(7), 1555-1572.
http://dx.doi.org/10.1007/s00224-017-9821-6
---------- CHICAGO ----------
Becher, V., Carton, O., Heiber, P.A. "Finite-State Independence" . Theory of Computing Systems 62, no. 7 (2018) : 1555-1572.
http://dx.doi.org/10.1007/s00224-017-9821-6
---------- MLA ----------
Becher, V., Carton, O., Heiber, P.A. "Finite-State Independence" . Theory of Computing Systems, vol. 62, no. 7, 2018, pp. 1555-1572.
http://dx.doi.org/10.1007/s00224-017-9821-6
---------- VANCOUVER ----------
Becher, V., Carton, O., Heiber, P.A. Finite-State Independence. Theory Comput. Syst. 2018;62(7):1555-1572.
http://dx.doi.org/10.1007/s00224-017-9821-6