×

The number of languages with maximum state complexity. (English) Zbl 07565556

Summary: Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to determine the number of maximum-complexity languages. Here we give a formula for this number. We also generalize their work from languages to functions on finite sets.

MSC:

68Q45 Formal languages and automata
05A15 Exact enumeration problems, generating functions
68Q19 Descriptive complexity and finite models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Câmpeanu, C.; Ho, WH, The maximum state complexity for finite languages, J. Autom. Lang. Comb., 9, 2-3, 189-202 (2004) · Zbl 1098.68064
[2] Champarnaud, JM; Pin, JE, A maxmin problem on finite automata, Discret. Appl. Math., 23, 1, 91-96 (1989) · Zbl 0666.68078 · doi:10.1016/0166-218X(89)90037-1
[3] Kjos-Hanssen, B., On the complexity of automatic complexity, Theory Comput. Syst., 61, 4, 1427-1439 (2017) · Zbl 1387.68158 · doi:10.1007/s00224-017-9795-4
[4] Kjos-Hanssen, B., Liu, L.: The number of languages with maximum state complexity. In: Gopal, T., Watada, J. (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 11436, pp. 394-409. Springer, Cham (2019). doi:10.1007/978-3-030-14812-6_24 · Zbl 1524.68173
[5] Poluyan, SV; Ershov, NM, Quantile transform in structural bioinformatics problems, Comput. Nanotechnol., 4, 29-43 (2019) · doi:10.33693/2313-223X-2019-6-4-29-43
[6] Shallit, J., A Second Course in Formal Languages and Automata Theory (2008), New York: Cambridge University Press, New York · Zbl 1163.68025 · doi:10.1017/CBO9780511808876
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.