{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T08:00:16Z","timestamp":1771660816964,"version":"3.50.1"},"reference-count":36,"publisher":"Zhejiang University Press","issue":"8","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Zhejiang Univ. - Sci. C"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1631\/jzus.c1200349","type":"journal-article","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T03:26:42Z","timestamp":1376018802000},"page":"623-633","source":"Crossref","is-referenced-by-count":1,"title":["Application of formal languages in polynomial transformations of instances between NP-complete problems"],"prefix":"10.1631","volume":"14","author":[{"given":"Jorge A.","family":"Ruiz-Vanoye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joaqu\u00edn","family":"P\u00e9rez-Ortega","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolfo A.","family":"Pazos Rangel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ocotl\u00e1n","family":"D\u00edaz-Parra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00e9ctor J.","family":"Fraire-Huacuja","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Frausto-Sol\u00eds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerardo","family":"Reyes-Salgado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Cruz-Reyes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"635","published-online":{"date-parts":[[2013,8,10]]},"reference":[{"key":"ref1","first-page":"14","volume-title":"Compilers: Principles. Techniques, and Tools","author":"Aho","year":"1986"},{"key":"ref2","first-page":"125","article-title":"The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich Association for Computing Machinery (ACM) and the Association for Applied Mathematics and Mechanics (GAMM) Conference","volume-title":"Proc. Int. Conf. on Information Processing","author":"Backus","year":"1959"},{"key":"ref3","first-page":"317","article-title":"Analysis on complexity of neural networks using integer weights","volume":"6","author":"Bao","year":"2012","journal-title":"Appl. Math. Inf. Sci."},{"key":"ref4","volume-title":"On Spectra","author":"Bennett","year":"1962"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1080\/09500349414552161"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0660-53"},{"key":"ref7","first-page":"24","article-title":"The Intrinsic Computational Difficulty of Functions","volume-title":"Proc. Congress for Logic, Mathematics, and Philosophy of Science","author":"Cobham","year":"1964"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/358141.358144"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1989.0099"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.4153\/cjm-1965-045-4"},{"key":"ref12","first-page":"1","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1090\/s0002-9947-1965-0170805-7"},{"key":"ref14","first-page":"1","volume-title":"Formal Languages and Their Relation to Automata","author":"Hopcroft","year":"1969"},{"key":"ref15","first-page":"205","article-title":"Complexity Results for State-Variable Planning under Mixed Syntactical and Structural Restriction","volume-title":"Proc. 6th Int. Conf. on Artificial Intelligence: Methodology, Systems, Applications","author":"Jonsson","year":"1994"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref17","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume-title":"Prob. Inf. Transm.","volume":"1","author":"Kolmogorov","year":"1965"},{"key":"ref18","volume-title":"Flex & Bison","author":"Levine","year":"2009"},{"key":"ref19","first-page":"221","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello","year":"1991"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/sct.1990.113951"},{"key":"ref21","first-page":"342","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"ref22","first-page":"260","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"ref23","first-page":"1","article-title":"Speed of Computation and Classification of Recursive Sets","author":"Rabin","year":"1959","journal-title":"Third Convention of Scientific Societies"},{"issue":"2","key":"ref24","first-page":"21","article-title":"An overview of the theory of instances computational complexity","volume":"2","author":"Ruiz-Vanoye","year":"2011","journal-title":"Int. J. Combin. Optim. Probl. Inf."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.5772\/7807"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2011.02.018"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"ref29","volume-title":"A Preliminary Report on a General Theory of Inductive Inference","author":"Solomonoff","year":"1960"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/s0019-9958(64)90223-2"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/s0019-9958(64)90131-7"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.2307\/2273858"},{"key":"ref33","volume-title":"Information-Based Complexity","author":"Traub","year":"1988"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064x(85)90020-2"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366852"}],"container-title":["Journal of Zhejiang University SCIENCE C"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1631\/jzus.C1200349.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1631\/jzus.C1200349\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1631\/jzus.C1200349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T07:00:40Z","timestamp":1771657240000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1631\/jzus.C1200349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":36,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["1429"],"URL":"https:\/\/doi.org\/10.1631\/jzus.c1200349","relation":{},"ISSN":["1869-1951","1869-196X"],"issn-type":[{"value":"1869-1951","type":"print"},{"value":"1869-196X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}