Abstract
We present natural bounds for the complexity function of two-dimensional arrays, and we study the shape of the maximal complexity function.
Some problems concerning the existence of maximal arrays are discussed.
Authors
Mira-Cristiana Anisiu
Tiberiu Popoviciu Institute of Numerical Analysis Romanian Academy
Antal Iványi
Faculty of Informatics of Eötvös Loránd University, Budapest, Hungary
Keywords
?
Paper coordinates
M.-C. Anisiu, A. Iványi, Two-dimensional arrays with maximal complexity, Pure Math. Appl., 17 (2006) nos. 3-4, 197-204.
About this paper
Journal
PU.M.A
Publisher Name
DOI
Print ISSN
Online ISSN
google scholar link
[1] M.-C. Anisiu, Finite words with special complexity properties, Pure Math. Appl., 13 (2002), 31–37.
[2] M.-C. Anisiu, Z. Blázsik and Z. Kása, Maximal complexity of finite words, Pure Math. Appl., 13 (2002), 39–48.
[3] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Revue Anal. Numér. Théor. Approx., 33 (2) (2004), 123–139.
[4] N.G. de Bruijn, A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch., 49 (1946), 758–764.
[5] A. Carpi and A. de Luca, Words and special factors, Theor. Comp. Sci., 259 (2001), 145–182.
[6] J. Cassaigne, Subword complexity and periodicity in two and more dimensions. In: Developments in Language Theory, (Proc. of 4th Int. Conf. DLT, Aachen, 1999). Eds. G. Rosenberg and W. Thomas, World Scientific Publishing, River Edge, NJ, 2000, 14–21.
[7] L.J. Cummings and D. Wiedemann, Embedded de Bruijn sequences, Congr. Numer., 53 (1986), 155–160.
[8] J. Dénes and A.D. Keedwell, Frequency allocation for a mobile radio telephone system, IEEE Trans. Communications, 36 (1988), 765–767.
[9] T. Etzion, Construction of perfect maps and pseudo-random arrays, IEEE Trans. Inf. Theory, 34 (1988), 1308–1316.
[10] C.T. Fan, S.M. Fan, S.L. Ma and M.K. Siu, On de Bruijn arrays, Ars Combin., 19A (1985), 205–213.
[11] S. Ferenczi and Z. Kása, Complexity of finite and infinite words, Theor. Comp. Sci., 218 (1999), 177–195.
[12] M. Harvit, Spectrometric imager, Appl. Optics, 10 (1971), 1415–1421.
[13] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27–38.
[14] A. Iványi, On the d-complexity of words, Annales Univ. Sci. Budapest., Sect. Comput., 8 (1987), 69–90.
[15] A. Iványi, Construction of infinite de Bruijn arrays, Discr. Appl. Math., 22 (1988/89), 289–293.
[16] A. Iványi, Construction of three-dimensional perfect matrices, Ars Combin., 29C (1990), 33–40.
[17] A. Iványi and Z. Tóth, Construction of planar de Bruijn words. In: Papers on Automata and Languages, (ed. by I. Peák), pp. 63–69. Karl Marx Univ. of Economics, Budapest, 1988.
[18] S. Jaeger, R. Lima and B. Mossé, Symbolic analysis of finite words. In: The complexity function, Bull. Braz. Soc. Math. New Series 34 (2003), 457–477.
[19] Z. Kása, On d-complexity of strings, Pure Math. Appl., 9 (1–2) (1998), 119–128.
[20] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Journées Montoises d’Informatique Théorique (Marne-la-Valée, 2000), Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277–291.
[21] A. de Luca, On the combinatorics of finite words, Theor. Comp. Sci., 218 (1) (1999), 13–29.
[22] S.L. Ma, A note on binary arrays with certain window property, IEEE Trans. Inform. Theory, 30 (1984), 774–775.
[23] M.H. Martin, A problem of arrangements, Bull. Amer. Math. Soc., 40 (1934), 859–864.
[24] C.J. Mitchell, Aperiodic and semi-periodic perfect maps, IEEE Trans. Inform. Theory, 41 (1995), 88–95.
[25] C.J. Mitchell and K.G. Paterson, Decoding perfect maps, Des. Codes Cryptogr., 4 (1994), 11–30.
[26] K.G. Paterson, Perfect maps, IEEE Trans. Inform. Theory, 40 (1994), 743–753.
[27] J. Shallit, On the maximum number of distinct factors in a binary string, Graphs Comb., 9 (2) (1993), 197–200.