Voir la notice de l'article provenant de la source Math-Net.Ru
@article{MT_2006_9_1_a5,
author = {V. Yu. Popov},
title = {NP-Completeness of {the~Dictionary} {Generation} {Problem}},
journal = {Matemati\v{c}eskie trudy},
pages = {117--129},
publisher = {mathdoc},
volume = {9},
number = {1},
year = {2006},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/}
}
V. Yu. Popov. NP-Completeness of the~Dictionary Generation Problem. Matematičeskie trudy, Tome 9 (2006) no. 1, pp. 117-129. http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/
[1] Bakhturin Yu. A., Tozhdestva v algebrakh Li, Nauka, M., 1985 | MR | Zbl
[2] Lalleman Zh., Polugruppy i kombinatornye prilozheniya, Mir, M., 1985 | MR
[3] Kholl M., Teoriya grupp, Izd-vo inostr. lit., M., 1962
[4] Aho A. V., “Algorithms for finding patterns in strings”, Handbook of Theoretical Computer Science, Elsevier Science Publishers, Amsterdam, 1990, 255–300 | MR | Zbl
[5] Bellman R., “On a routing problem”, Quart. Appl. Math., 16:1 (1958), 87–90 | MR | Zbl
[6] Bodlaender H., Downey R., Fellows M., Hallett M., and Wareham H., “Parameterized complexity analysis in computational biology”, Comput. Appl. Biosci., 11 (1995), 49–57
[7] Cherly J., “On complementary sets of group elements”, Arch. Math., 35 (1980), 313–318 | DOI | MR | Zbl
[8] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numer. Math., 1 (1959), 269–271 | DOI | MR | Zbl
[9] Dorit R. L. and Gilbert W., “The limited universe of exons”, Current Opinions in Structural Biology, 1 (1991), 973–977 | DOI
[10] Floyd R. W., “Algorithm 97: shortest path”, Comm. ACM, 5:6 (1962), 345 | DOI
[11] Ford L. R., Jr. and Fullkerson D. R., Flows in Networks, Princeton University Press, Princeton, NJ, 1962 | MR | Zbl
[12] Gusfield D., Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology, Cambridge University Press, Cambridge, 1997 | MR | Zbl
[13] Jia X.-D., “Thin bases for finite abelian groups”, J. Number Theory, 36:2 (1990), 254–256 | DOI | MR | Zbl
[14] Jia X.-D., “Thin bases for finite nilpotent groups”, J. Number Theory, 41:3 (1992), 303–313 | DOI | MR | Zbl
[15] Kozma G. and Lev A., “Bases and decomposition numbers of finite groups”, Arch. Math., 58:5 (1992), 417–424 | DOI | MR | Zbl
[16] Kozma G. and Lev A., “On $h$-bases and $h$-decompositions of the finite solvable and alternating groups”, J. Number Theory, 49:3 (1994), 385–391 | DOI | MR | Zbl
[17] Natbanson M. B., “On a problem of Rohrbach for finite groups”, J. Number Theory, 41:1 (1992), 69–76 | DOI | MR
[18] Ngo T. J. and Marks J., Computational Complexity of a Problem in Molecular Structure Prediction, Technical Report TR-17-91, Center for Research in Computing Technology, Aiken Computation Laboratory, Harvard University, Harvard, 1991
[19] Papadimitriou S. N., Computational Complexity, Addison-Wesley Publishing Company, Amsterdam, 1994 | MR | Zbl
[20] Patthy L., “Exons — original building blocks of proteins?”, BioEssays, 13:4 (1991), 187–192 | DOI
[21] Pearson W. R. and Miller W., “Dynamic programming algorithms for biological sequence comparison”, Methods in Enzymology, 183 (1992), 575–601 | DOI
[22] Piochi B., Lower Bound for Status of Semigroups, Rapporto N 7, Dipartimento di Matematica «U. Dini», Università degli Studi di Firenze, 2003
[23] Reeke G. N., Jr., “Protein folding: computational approaches to an exponential-time problem”, Annual Reviews of Computer Science, 3 (1988), 59–84 | DOI
[24] Rohrbach H., “Anwendung eines Satzes der additiven Zahlentheorie auf eine gruppentheoretische Frage”, Math. Z., 42:1 (1937), 538–542 (German) | DOI | MR | Zbl
[25] Rohrbach H., “Ein Betrag zur additiven Zahlentheorie”, Math. Z., 42 (1937), 1–30 (German) | DOI | MR
[26] Watson J., Oilman M., Witkowski J., and Zoller M., Recombinant DNA, Scientific American Books, San Francisco, CA, 1992