×

Growth rates of complexity of power-free languages. (English) Zbl 1196.68121

Summary: We present a new fast algorithm for calculating the growth rate of complexity for regular languages. Using this algorithm we develop a space and time efficient method to approximate growth rates of complexity of arbitrary power-free languages over finite alphabets. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds and discover some general regularities.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Berstel, J.; Karhumäki, J., Combinatorics on words: a tutorial, Bull. eur. assoc. theoret. comput. sci., 79, 178-228, (2003) · Zbl 1169.68560
[2] Brandenburg, F.-J., Uniformly growing \(k\)-th power free homomorphisms, Theoret. comput. sci., 23, 69-82, (1983) · Zbl 0508.68051
[3] Carpi, A., On dejean’s conjecture over large alphabets, Theoret. comput. sci., 385, 137-151, (2007) · Zbl 1124.68087
[4] Crochemore, M.; Mignosi, F.; Restivo, A., Automata and forbidden words, Inform. process. lett., 67, 3, 111-117, (1998) · Zbl 1339.68145
[5] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs. theory and applications, (1995), Johann Ambrosius Barth Heidelberg · Zbl 0824.05046
[6] Dejean, F., Sur un theoreme de thue, J. combin. theory ser. A, 13, 1, 90-99, (1972) · Zbl 0245.20052
[7] Edlin, A., The number of binary cube-free words of length up to 47 and their numerical analysis, J. difference equ. appl., 5, 153-154, (1999) · Zbl 0939.05007
[8] Franklin, J.N., Matrix theory, (1968), Prentice-Hall Inc. Englewood Cliffs, NJ · Zbl 0174.31501
[9] Gantmacher, F.R., Application of the theory of matrices, (1959), Interscience New York · Zbl 0085.01001
[10] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[11] Karhumäki, J.; Shallit, J., Polynomial versus exponential growth in repetition-free binary words, J. combin. theory. ser. A, 105, 335-347, (2004) · Zbl 1065.68080
[12] Kobayashi, Y., Repetition-free words, Theoret. comput. sci., 44, 175-197, (1986) · Zbl 0596.20058
[13] Kobayashi, Y., Enumeration of irreducible binary words, Discrete. appl. math., 20, 221-232, (1988) · Zbl 0673.68046
[14] R. Kolpakov, On the number of repetition-free words, in: Electronic Proceedings of Workshop on Words and Automata, WOWA’06, S.-Petersburg, 2006, #6. · Zbl 1249.68149
[15] Lothaire, M., Combinatorics on words, (1983), Addison-Wesley · Zbl 0514.20045
[16] P. Ochem, T. Reix, Upper bound on the number of ternary square-free words, in: Electronic Proceedings of Workshop on Words and Automata, WOWA’06, S.-Petersburg, 2006, #8.
[17] Restivo, A.; Salemi, S., (), 196-206
[18] Richard, C.; Grimm, U., On the entropy and letter frequencies of ternary square-free words, Electron. J. combin., 11, 1, (2004), # R14 · Zbl 1104.68090
[19] Shur, A.M., The structure of the set of cube-free Z-words in a two-letter alphabet, Izv. ross. akad. nauk ser. mat., 64, 201-224, (2000), (Russian); English translation in Izv. Math. 64 (2000), 847-871 · Zbl 0972.68131
[20] Shur, A.M., Combinatorial complexity of rational languages, Discr. anal. oper. research, ser. 1, 12, 2, 78-99, (2005), (Russian) · Zbl 1249.68107
[21] Shur, A.M., Comparing complexity functions of a language and its extendable part, RAIRO theor. inf. appl., 42, 647-655, (2008) · Zbl 1149.68055
[22] Shur, A.M., Calculating parameters and behavior types of combinatorial complexity for regular languages, Proc. inst. math. mech. UB RAS, 16, 2, 270-287, (2010)
[23] Shur, A.M., (), 289-301
[24] Thue, A., Über unendliche zeichenreihen, Kra. vidensk. selsk. skrifter. I. mat.-nat. kl., christiana, 7, 1-22, (1906) · JFM 39.0283.01
[25] J.D. Currie, N. Rampersad, A proof of Dejean’s conjecture, http://arxiv.org/PScache/arxiv/pdf/0905/0905.1129v3.pdf. · Zbl 1215.68192
[26] M. Rao, Last Cases of Dejean’s conjecture, in: Proceedings of the 7th International Conference on Words, Salerno, Italy,-2009. #115. · Zbl 1230.68163
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.