{"entities":{"Q1113663":{"pageid":1124412,"ns":120,"title":"Item:Q1113663","lastrevid":66153801,"modified":"2026-04-12T07:54:32Z","type":"item","id":"Q1113663","labels":{"en":{"language":"en","value":"Conditions for incremental iteration: Examples and counterexamples"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4080883"}},"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":"Q1113663$5C42E3F4-BBF2-4348-BC9B-595A876F01D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"782a274c69ea40d7e412555571381e7db33eae32","datavalue":{"value":{"text":"Conditions for incremental iteration: Examples and counterexamples","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1113663$4BD601EB-D3E9-488A-BAB4-AF20B23A538C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03fb4b2e835e945deddf5fa8adc0aec6018311b2","datavalue":{"value":"0661.68014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$536B9E86-9783-41E2-8A09-B58F93762060","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be061879fd61e8f7c167265c2d4c17bd58564cfe","datavalue":{"value":"10.1016/0167-6423(88)90061-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$631E96F9-C77D-4AEE-A079-96CB5B40E9E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4082512e7d3530b9726df691c7c28e9fec542a8c","datavalue":{"value":{"entity-type":"item","numeric-id":169675,"id":"Q169675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113663$5E49D3BA-6F93-4C26-99A1-51069FE80861","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1113663$89700525-E4EA-46EF-9E54-C9697E7878EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b812b8b70ea42fadfe704f74dab8a903b728deb4","datavalue":{"value":"Given a problem (e.g., that of data-flow analysis) formulated as a set of (generally recursive) equations \\(X=A(X)\\), its solution can be found by iterative algorithms as an extreme (here the least) fixed point \\(X^ m\\) of the system as above. It is often too expensive to fully reanalyse a system each time it changes from \\(X=A(X)\\) onto \\(Y=B(Y)\\). The paper is concerned with correctness of the following strategy: use iteration and recompute the desired solution incrementally, by restarting iterations of B from \\(X^*\\) (or from some iterative \\(X^ i=A^ i(\\perp))\\) rather than from the smallest element \\(\\perp\\). Sufficient conditions for correctness of this incremental recomputations are given and, moreover, it is shown that these incremental iterations involve at most as many applications of B to attain its fixed point as standard successive applications of B starting with \\(\\perp\\), i.e., \\(<B^ j(A^ i(\\perp))>_{j\\to \\infty}\\) attains its limit at least as rapidly as the sequence \\(<B^ j(\\perp)>_{j\\to \\infty}\\). A number of motivating/illustrating (counter) examples is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113663$9681AA47-EB0F-4231-85FC-BF53DBD31275","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$A956F910-4074-4143-A78E-0FCD102A56AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$63710F1E-0F59-46A5-AAAC-9743B12EB6B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"591e03bc9307f82ba1f525949fd0cc00dbfe7287","datavalue":{"value":"4080883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$67F9AC2B-A4C5-4492-91D9-C9E1FCAF1939","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eca86ec2199e946a904187c988edd92122e10ef9","datavalue":{"value":"fixed points of systems of equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113663$7D43ED22-F67B-47C5-A7BC-0E331E62D022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"318ee7787be3e0c68242571730e2f45b7e60a539","datavalue":{"value":"incremental data flow analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113663$1C680D52-0F00-4569-A272-E8B8452777C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c23a8e517d4c5b1b75d8af071d2d2625d4abebbe","datavalue":{"value":"iterative algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113663$E84480D9-2772-421D-99A4-D7B96BA08CF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77a7a65e5d14bb41c3f1c854c9e84732783685d2","datavalue":{"value":"incremental iterations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113663$F71A0346-0FB3-4AEB-9C0B-9AEAD4E7163A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01878fc13290955bbf4152b0852507e9d2eaffd5","datavalue":{"value":{"entity-type":"item","numeric-id":202479,"id":"Q202479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113663$B8F2A4E3-698A-4811-80EF-C956A6DF5F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d63a08d80e4eb0dac2bd3b9b4820e060dea00045","datavalue":{"value":{"entity-type":"item","numeric-id":1823165,"id":"Q1823165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113663$CFE7BB2E-E31B-4805-B6A0-CAD72C4B0ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"19c818b576090003976797a56598e7980ef7ca63","datavalue":{"value":{"entity-type":"item","numeric-id":913507,"id":"Q913507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113663$99569B42-96C3-4189-9B0E-35808252A8A2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90e834492c280ea6f7cd09939cbb51910bf38c22","datavalue":{"value":{"entity-type":"item","numeric-id":1006888,"id":"Q1006888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113663$F6854EF2-6ABC-4515-9A2B-E67C980BB562","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":"Q1113663$74CF1E03-15F3-41BC-A659-F4E19E66F073","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75697469dcae7e01e77acf111e1728f5bba07937","datavalue":{"value":"https://doi.org/10.1016/0167-6423(88)90061-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1113663$9460F958-134F-4A3D-8B89-1E06578065DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce087912ac94e6faa64a5be4c9d6034856769288","datavalue":{"value":"W2046531404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$277039A4-3EFA-4ADD-958B-40D0755D89E9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"374d4d4158bb9636acc24e0857784b31e0310d20","datavalue":{"value":"Q124856659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113663$DE291A8F-6017-45D2-9822-B447B79C1649","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c25416612df98e2c893b0f1ee3fd200bf5e66813","datavalue":{"value":{"entity-type":"item","numeric-id":688197,"id":"Q688197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49e631cda7ae0fe360fd50c1389fa63811e1d7a0","datavalue":{"value":{"amount":"+0.7534974813461304","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":"Q1113663$F8F8426C-BD60-4999-A20C-A0FCF7A39A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c70eff01fd1b21585ff24120d9a133a72213affd","datavalue":{"value":{"entity-type":"item","numeric-id":1919660,"id":"Q1919660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41455394dd8824a336a74b9464771ad106c52750","datavalue":{"value":{"amount":"+0.7491444945335388","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":"Q1113663$72CE6968-3F3E-40F9-B3A3-E2A9474E45FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28daf98177955b70818ae09d5730887e46ca0e89","datavalue":{"value":{"entity-type":"item","numeric-id":5287508,"id":"Q5287508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7a5911f2ecc14b8e7720eee8562876e643e1a8d","datavalue":{"value":{"amount":"+0.7463315725326538","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":"Q1113663$97D9350C-678A-4DFE-B029-74667D744DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce77d607fa2d8c09d0cd8ea7f8f0ea8927bcfe18","datavalue":{"value":{"entity-type":"item","numeric-id":3314955,"id":"Q3314955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f67b8f0ecbc5abfb091c84da99458273145ffd75","datavalue":{"value":{"amount":"+0.7458009719848633","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":"Q1113663$FC8CD8A7-64BC-438B-BC75-9ABF73A0F132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"907e0283f77723e3abfbba915d66b58e3be22482","datavalue":{"value":{"entity-type":"item","numeric-id":2999782,"id":"Q2999782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c40be62db22e85b038cd0ffe3e574f421cb572ee","datavalue":{"value":{"amount":"+0.7445123195648193","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":"Q1113663$FD695470-6B0B-479E-BF58-33FF9C33130E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Conditions for incremental iteration: Examples and counterexamples","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Conditions_for_incremental_iteration:_Examples_and_counterexamples"}}}}}