{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:53:33Z","timestamp":1725490413635},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_59","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T10:58:43Z","timestamp":1188039523000},"page":"680-691","source":"Crossref","is-referenced-by-count":3,"title":["Aliased Register Allocation for Straight-Line Programs Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Jonathan K.","family":"Lee","sequence":"first","affiliation":[]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[]},{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/378795.378854","volume-title":"PLDI","author":"A.W. Appel","year":"2001","unstructured":"Appel, A.W., George, L.: Optimal spilling for CISC machines with few registers. In: PLDI, pp. 243\u2013253. ACM Press, New York (2001)"},{"key":"59_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511811432","volume-title":"Modern Compiler Implementation in Java","author":"A.W. Appel","year":"2002","unstructured":"Appel, A.W., Palsberg, J.: Modern Compiler Implementation in Java. Cambridge University Press, Cambridge (2002)"},{"key":"59_CR3","first-page":"267","volume-title":"Discrete Mathematics","author":"M. Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. I:\u00cainterval graphs. In: Discrete Mathematics, p. 267. ACM Press, New York (1992) Special volume (part 1) to mark the centennial of Julius Petersen\u2019s Die theorie der regularen graphs"},{"key":"59_CR4","unstructured":"Briggs, P.: Register Allocation via Graph Coloring. PhD thesis, Rice University (1992)"},{"issue":"1","key":"59_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/130616.130617","volume":"1","author":"P. Briggs","year":"1992","unstructured":"Briggs, P., Cooper, K., Torczon, L.: Coloring register pairs. ACM Letters on Programming Languages\u00a01(1), 3\u201313 (1992)","journal-title":"ACM Letters on Programming Languages"},{"key":"59_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G.J. Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Computer Languages\u00a06, 47\u201357 (1981)","journal-title":"Computer Languages"},{"key":"59_CR7","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing 5(4) (1976)","DOI":"10.1137\/0205048"},{"key":"59_CR8","first-page":"564","volume-title":"9th ACM-SIAM symposium on Discrete Algorithms","author":"M. Farach","year":"1998","unstructured":"Farach, M., Liberatore, V.: On local register allocation. In: 9th ACM-SIAM symposium on Discrete Algorithms, pp. 564\u2013573. ACM Press, New York (1998)"},{"key":"59_CR9","volume-title":"A Retargetable C Compiler: Design and Implementation","author":"C. Fraser","year":"1995","unstructured":"Fraser, C., Hanson, D.: A Retargetable C Compiler: Design and Implementation. Addison-Wesley, Reading (1995)"},{"key":"59_CR10","first-page":"245","volume-title":"Internation Symposium on Microarchitecture","author":"C. Fu","year":"2002","unstructured":"Fu, C., Wilken, K.D.: A faster optimal register allocator. In: Internation Symposium on Microarchitecture, pp. 245\u2013256. ACM Press, New York (2002)"},{"key":"59_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier, Amsterdam (2004)","edition":"2"},{"issue":"8","key":"59_CR12","first-page":"929","volume":"26","author":"D.W. Goodwin","year":"1996","unstructured":"Goodwin, D.W., Wilken, K.D.: Optimal and near-optimal global register allocations using 0-1 integer programming. SPE\u00a026(8), 929\u2013965 (1996)","journal-title":"SPE"},{"key":"59_CR13","first-page":"202","volume-title":"JMLC","author":"U. Hirnschrott","year":"2003","unstructured":"Hirnschrott, U., Krall, A., Scholz, B.: Graph coloring vs. optimal register allocation for optimizing compilers. In: JMLC, pp. 202\u2013213. Springer, Heidelberg (2003)"},{"key":"59_CR14","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1109\/MICRO.1998.742791","volume-title":"Internation Symposium on Microarchitecture","author":"T. Kong","year":"1998","unstructured":"Kong, T., Wilken, K.D.: Precise register allocation for irregular architectures. In: Internation Symposium on Microarchitecture, pp. 297\u2013307. ACM Press, New York (1998)"},{"key":"59_CR15","first-page":"297","volume-title":"PLDI","author":"A. Koseki","year":"2002","unstructured":"Koseki, A., Komatsu, H., Nakatani, T.: Preference-directed graph coloring. In: PLDI, pp. 297\u2013307. ACM Press, New York (2002)"},{"key":"59_CR16","doi-asserted-by":"crossref","unstructured":"Nickerson, B.R.: Graph coloring register allocation for processors with multi-register operands. In: PLDI, pp. 40\u201352 (1990)","DOI":"10.1145\/93542.93552"},{"key":"59_CR17","first-page":"240","volume-title":"SCOPES","author":"J. Runeson","year":"2003","unstructured":"Runeson, J., Nystrom, S.-O.: Retargetable graph-coloring register allocation for irregular architectures. In: SCOPES, pp. 240\u2013254. Springer, Heidelberg (2003)"},{"key":"59_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/513829.513854","volume-title":"LCTES\/SCOPES","author":"B. Scholz","year":"2002","unstructured":"Scholz, B., Eckstein, E.: Register allocation for irregular architectures. In: LCTES\/SCOPES, pp. 139\u2013148. ACM Press, New York (2002)"},{"key":"59_CR19","doi-asserted-by":"crossref","unstructured":"Smith, M.D., Ramsey, N., Holloway, G.: A generalized algorithm for graph-coloring register allocation. In: PLDI, pp. 277\u2013288 (2004)","DOI":"10.1145\/996841.996875"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:11:21Z","timestamp":1619503881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}