Geodesic
Calculating parameters and behavior types of combinatorial complexity for regular languages
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 2, pp. 270-287
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The main quantitative characteristics of a language $L$ over a finite alphabet $\Sigma$ is the function $C_L(n)=|L\cap\Sigma^n|$ called the combinatorial complexity of $L$. We relate the type and parameters of the asymptotic behaviour of this function for a regular language $L$ to the parameters of the corresponding finite automaton. Then we give efficient algorithms to calculate such parameters of finite automata. Using these results, we describe the oscillations of combinatorial complexity for arbitrary, prefix, and factorial regular languages.
Keywords: regular language, finite automaton, combinatorial complexity, growth rate. 
@article{TIMM_2010_16_2_a23,
     author = {A. M. Shur},
     title = {Calculating parameters and behavior types of combinatorial complexity for regular languages},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {270--287},
     year = {2010},
     volume = {16},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a23/}
}
TY  - JOUR
AU  - A. M. Shur
TI  - Calculating parameters and behavior types of combinatorial complexity for regular languages
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 270
EP  - 287
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a23/
LA  - ru
ID  - TIMM_2010_16_2_a23
ER  - 
%0 Journal Article
%A A. M. Shur
%T Calculating parameters and behavior types of combinatorial complexity for regular languages
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 270-287
%V 16
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a23/
%G ru
%F TIMM_2010_16_2_a23
A. M. Shur. Calculating parameters and behavior types of combinatorial complexity for regular languages. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 2, pp. 270-287. http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a23/

[1] Balogh J., Bollobas B., “Hereditary properties of words”, RAIRO Inf. Theor. Appl., 39 (2005), 49–65 | DOI | MR | Zbl

[2] Berstel J., “Growth of repetition-free words – a review”, Theor. Comput. Sci., 340:2 (2005), 280–290 | DOI | MR | Zbl

[3] Cassaigne J., “Special factors of sequences with linear subword complexity”, Developments in language theory, II, eds. J. Dassow, G. Rozenberg, A. Salomaa, World Scientific, Singapore, 1996, 25–34 | MR | Zbl

[4] Cassaigne J., “Counting overlap-free binary words”, Proc. 10th Ann. symp. on theoretical aspects of computer science, Lect. Notes Comp. Sci., 665, 1993, 216–225 | MR | Zbl

[5] Choffrut C., Karhumki J., “Combinatorics of words”, Handbook of formal languages, 1, eds. G. Rozenberg, A. Salomaa, Springer, Berlin, 1997, ch. 6, 329–438 | MR

[6] Chomsky N., Miller G. A., “Finite state languages”, Inf. and Control., 1:2 (1958), 91–112 | DOI | MR

[7] Chomsky N., Schützenberger M. P., “The algebraic theory of context-free languages”, Computer programming and formal system, eds. P. Braffort, D. Hirschberg, North-Holland, Amsterdam, 1963, 118–161 | MR

[8] Cormen T. H. [et al.], Introduction to algorithms, 2nd edition, The MIT Press, Cambridge, MA, 2001, 1202 pp. | MR | Zbl

[9] Cvetković D. M., Doob M., Sachs H., Spectra of graphs. Theory and applications, 3rd edition, Johann Ambrosius Barth, Heidelberg, 1995, 447 pp. | MR

[10] Ehrenfeucht A., Rozenberg G., “A limit theorem for sets of subwords in deterministic TOL languages”, Inform. Process. Lett., 2 (1973), 70–73 | DOI | MR | Zbl

[11] Ehrenfeucht A., Rozenberg G., “On subword complexities of homomorphic images of languages”, RAIRO Inform. Theor., 16 (1982), 303–316 | MR | Zbl

[12] Gromov M., “Groups of polynomial growth and expanding maps”, Inst. Hautes Études Sci. Publ. Math., 53 (1981), 53–73 | DOI | MR

[13] Krause G., Lenagan T. H., Growth of algebras and Gelfand–Kirillov dimension, Research Notes in Math., 116, Pitman, 1985, 212 pp. | MR | Zbl

[14] Lothaire M., Combinatorics on words, Addison-Wesley, Reading, MA, 1983, 238 pp. | MR | Zbl

[15] Milnor J., “Growth of finitely generated solvable groups”, J. Diff. Geom., 2 (1968), 447–450 | MR

[16] Morse M., Hedlund G. A., “Symbolic dynamics”, Amer. J. Math., 60 (1938), 815–866 | DOI | MR | Zbl

[17] Odlyzko A. M., “Asymptotic enumeration methods”, Handbook of combinatorics, 2, eds. R. L. Graham, M. Grötschel, L. Lovasz, Elsevier, Amsterdam, 1995, ch. 22, 1063–1230 | MR

[18] Salomaa A., Soittola M., Automata-theoretic aspects of formal power series, Springer, New York, 1978, 167 pp. | MR | Zbl

[19] Shur A. M., “Comparing complexity functions of a language and its extendable part”, RAIRO Theor. Inf. Appl., 42:3 (2008), 647–655 | DOI | MR | Zbl

[20] Shur A. M., “Combinatorial complexity of regular languages”, Lect. Notes Comp. Sci., 5010, eds. E. A. Hirsch [et al.], 2008, 289–301 | MR | Zbl

[21] Tarjan R., “Depth-first search and linear graph algorithms”, SIAM J. Computing, 1:2 (1972), 146–160 | DOI | MR | Zbl

[22] Trofimov V. I., “Growth functions of finitely generated semigroups”, Semigroup Forum, 21 (1980), 351–360 | DOI | MR | Zbl

[23] Gantmakher F. R., Teoriya matrits, Izd. 4-e, Fizmatlit, M., 1988, 552 pp. | MR

[24] Govorov V. E., “Graduirovannye algebry”, Mat. zametki, 12:2 (1972), 197–204 | MR | Zbl

[25] Trofimov V. I., “Funktsii rosta nekotorykh klassov yazykov”, Kibernetika, 1981, no. 6, 9–12 | MR | Zbl

[26] Ufnarovskii V. A., “O roste algebr”, Vest. MGU. Ser. 1. Matematika. Mekhanika, 1978, no. 4, 59–65 | MR | Zbl

[27] Shur A. M., “Indeksy rosta yazykov ogranichennoi eksponenty”, Izv. vuzov. Matematika, 2009, no. 9, 82–88 | MR | Zbl