{"entities":{"Q1920231":{"pageid":1930973,"ns":120,"title":"Item:Q1920231","lastrevid":47408314,"modified":"2026-01-01T16:11:02Z","type":"item","id":"Q1920231","labels":{"en":{"language":"en","value":"Using graph coloring in an algebraic compiler"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 918715"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920231$3C25DEB3-FFFF-4C4B-A829-5845F9374B38","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5c7a29861ed236aad4eeb75a16e32eea468acb62","datavalue":{"value":{"text":"Using graph coloring in an algebraic compiler","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1920231$DDF03323-7D27-4119-89EA-682942A8D27C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35028aef7464720b57f28c7ae4bafe0b4b300f9a","datavalue":{"value":"0865.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$9247BF5C-56B6-4218-A491-7D7509456D9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7420153a881d0b0533813766e67a09d1f9c5c2d5","datavalue":{"value":{"entity-type":"item","numeric-id":1129125,"id":"Q1129125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920231$C38896A5-15FA-4E7A-81CE-4873436F6092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c06e49fb7f2fdf79d0fcc1ad5ca574fb1cfacc16","datavalue":{"value":{"entity-type":"item","numeric-id":391987,"id":"Q391987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920231$965D4535-F6AC-471D-84FC-CC6425FCE461","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920231$FAC6DE36-0596-4C8E-B1DD-938F290F495E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c52e4811fffdb8f318da6437d640586a60136db4","datavalue":{"value":{"time":"+1996-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1920231$D53B36CE-28A1-440C-8A63-956ECCCEA16F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc8173db1e94ce7e7c67e8af0f5a3c02e129192f","datavalue":{"value":"An algebraic compiler allows incremental development of the source program and builds its target image by composing the target images of the program components. In this paper we describe a general structure of an algebraic compiler focusing on compositional code generation. We show that the mathematical model for register management by an algebraic compiler is a graph coloring problem in which an optimally colored graph is obtained by composing optimally colored subgraphs. More precisely, we define the clique-composition of graphs \\(G_1\\) and \\(G_2\\) as the graph obtained by joining all the vertices in a clique in \\(G_1\\) with all the vertices in a clique in \\(G_2\\). We present a linear-time algorithm that takes as input optimally colored graphs \\(G_1\\) and \\(G_2\\) and constructs an optimal coloring of any clique-composition of \\(G_1\\) and \\(G_2\\). Motivated by the operation of clique-composition, we define the class of clique-composable graphs as those graphs that can be iteratively built from single vertices using the clique-composition operation. We show that the class of clique-composable graphs coincides with the well-known class of chordal graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920231$FCDC93C3-1F69-484B-9B5E-AA157E08D3A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$58E4E2A4-9990-46B9-8A98-74E523ED03A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$E29CDC6A-0371-4954-9BAC-8DD43ED3F01A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$077C62DE-D041-4F8E-9F52-BCBB83E89593","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f0fc793e28f669ed1c4d1e8561874ea318faae1","datavalue":{"value":"918715","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$D34B7CB2-6931-4146-B30D-922A9A6076D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb0f4881450a67d699ffecfa7ed9b715a8d6a2a5","datavalue":{"value":"algebraic compiler","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920231$2395EE82-0B43-4C21-87C7-7CC23DD61487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920231$590E5CF0-2606-4F0A-B061-87EB0D76DE13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfac0e87d1bf3b63b73918af097a13e84cdf6d82","datavalue":{"value":"optimally colored subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920231$7CDD3859-4327-4AE9-B1CA-6AB18D0BA7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"694b76255f5075f1872cc269125530e13a9876f3","datavalue":{"value":"clique-composable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920231$48E76004-B49D-427D-A907-7482287043CF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920231$A9BBAE2A-57D2-48B7-877B-61F3186A6D45","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"60b232fc0026defb6badf5514c950121dad8c083","datavalue":{"value":"https://doi.org/10.1007/s002360050079","type":"string"},"datatype":"url"},"type":"statement","id":"Q1920231$789CA51D-92C8-4C24-826E-01E5BB70EC90","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8ef6ec6a68bbe49028930ff93f52b1d77fcbbd4","datavalue":{"value":"W2008487560","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$268B4A50-73C5-4CD8-8119-C7D1DCC0D076","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a6e96d31d83d8a450c3dea76e773d60421a8f1dc","datavalue":{"value":"Q121875131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$D4AA326E-7793-42D4-B331-D4A3A496A54B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fc3cd4766f3efefbf822eae4f17f6e93073927a","datavalue":{"value":"10.1007/S002360050079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920231$E7B2031C-F80C-4C4D-AC76-FEE98F4731FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd39a359ea1dba26791d8b3a1698c99542d44f6f","datavalue":{"value":{"entity-type":"item","numeric-id":5493394,"id":"Q5493394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eb82d5300c86011d30fa6da0cc46f52da71b3aa","datavalue":{"value":{"amount":"+0.7831395864486694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920231$067E64EC-C3AD-46E8-B550-432FD148148D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29a0b187c0d49940925650f5d679f0d5146735c8","datavalue":{"value":{"entity-type":"item","numeric-id":1296576,"id":"Q1296576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"727694472a92fc8df5eb5a0ff2ec2435a5d6a8f1","datavalue":{"value":{"amount":"+0.7615736126899719","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920231$01ED94EE-6C70-4577-BB44-DDB8C69D4AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8a475f2c6fb55dd8721e9ca36487a36d9d163c2","datavalue":{"value":{"entity-type":"item","numeric-id":4886067,"id":"Q4886067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"727694472a92fc8df5eb5a0ff2ec2435a5d6a8f1","datavalue":{"value":{"amount":"+0.7615736126899719","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920231$5B5E3591-EF0A-4839-9746-9447D0CBDB20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92aa50966080e0f73259961e78cdd79dbb81e07d","datavalue":{"value":{"entity-type":"item","numeric-id":4417780,"id":"Q4417780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d2fae1e31bb2230fdcaba3143e9ca7b9df9b0a5","datavalue":{"value":{"amount":"+0.7536543011665344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920231$6A7BEEBB-511C-4294-A98A-6520D9DD66AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4c822b70a3bb9b3aa0e200f4187181bf13f3718","datavalue":{"value":{"entity-type":"item","numeric-id":673230,"id":"Q673230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9ce509c26643c71971de1454b07da659250aac3","datavalue":{"value":{"amount":"+0.7440058588981628","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920231$09E47B27-9BB4-4206-AB3E-3E91D9521D73","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1920231","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1920231"}}}}}