{"entities":{"Q1095643":{"pageid":1106395,"ns":120,"title":"Item:Q1095643","lastrevid":69826770,"modified":"2026-04-13T10:36:45Z","type":"item","id":"Q1095643","labels":{"en":{"language":"en","value":"A polynomial determination of the most-recent property in Pascal-like programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028874"}},"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":"Q1095643$732A0A0A-722D-41B4-ACB5-500018D18E26","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a0f99bc9cf0504204a325f699a09c7b4a60c621","datavalue":{"value":{"text":"A polynomial determination of the most-recent property in Pascal-like programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095643$790192EA-600A-45DC-866D-FC57C3C2F2C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"853fde2a2d615805d7097858bf0bad7467e3e776","datavalue":{"value":"0632.68018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095643$C46B0323-D9CD-4304-A9AF-797F3DB19575","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d9f2d004db06074c23d36d4374a2557ad2515558","datavalue":{"value":"10.1016/0304-3975(86)90003-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095643$D48029F6-ADDC-4714-AA2A-1B237830522E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$2F213D45-57BD-440C-BCCD-5A5664A48CCF","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":"Q1095643$6F421309-F484-4AA3-8F05-F2FAA7243FCA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca00a16b3af04df38328e27a00a7b57358eee76e","datavalue":{"value":"If a compiler knew which procedures (or functions) of a program fulfill the most-recent property, it could produce more adequate code. This stands in contrast to the prevailing tacit worst-case assumption on the non-most-recent behavior of those procedures being passed as parameters (for all other procedures this property holds trivially). This old and well-known phenomenon will attract new attention with the development of new computer architectures - such as RISC.    We present a method which has a polynomial time complexity (in program length) for deciding this property in Wirth-Pascal-like programs by exploiting the inherent restriction concerning formal procedures. It is this restriction that enables us to (1) (polynomially) reduce the most- recent problem to a reachability problem for certain procedures and (2) solve this reachability problem with the polynomial algorithm which we present.    This polynomial result for such programs is rather unexpected since, for programs in slightly less restricted languages like ISO-Pascal, the problem is still decidable but with a complexity as bad as P-space complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$999AAF5B-B17B-4B45-ADEA-8A1895BFC958","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095643$9BD31451-DE2A-47FD-A694-814E960FE3C5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cfdce2b9eff601139e25789e835df16e946adabd","datavalue":{"value":"4028874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095643$D748EA3A-ED04-47C0-8740-93CCD2E08E0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"901c6d511d35303a6a968c1174234f4350020c8b","datavalue":{"value":"compiler","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$400A13A2-C220-4DA7-AC5B-E18AA6C0F8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f30a3c8672a0f1efa7df0391b8e932f16adb45a","datavalue":{"value":"computer architectures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$83A085AD-6AB5-4B46-9E87-65BDC7BECA79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"935e544cfdd3c7650374412765353585db235d6c","datavalue":{"value":"RISC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$E9BC98EE-26D1-47FB-92E2-70CB2A2D5D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e90b7870184b4fec8c274946c1560c81ece1d150","datavalue":{"value":"polynomial time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$0939FDCC-B839-4681-8953-E3FA713F4ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be4b33a7148620e81ef8792da1647525081fbfaf","datavalue":{"value":"program length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$75EB5666-7E0D-4A8E-9801-174CCE254F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0ec50b1d4947cb4f525da534d8caea75047b25b","datavalue":{"value":"Wirth-Pascal-like programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$F8780CA0-EEBB-42D2-A85E-77AC3233418A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecc2e39a874768547c2175f9054d183dcbd30568","datavalue":{"value":"reachability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$5F2FE53B-9F38-4265-8EF7-41C3A88A4784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$8D4B249B-47CB-42AD-BF3C-8C817E899B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc58c025ec0b0c28061cc703de93874cd9298ed5","datavalue":{"value":"ISO-Pascal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$D21AE95D-A7AE-4675-9B02-E927985A6870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4026530cf219f49314fb0429d444a589608fe6a","datavalue":{"value":"P-space complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095643$D2B46A1C-C1E2-41D7-8460-C05521128A3A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f0702b578a328224eb4d1059a09394720b2b190","datavalue":{"value":{"entity-type":"item","numeric-id":258507,"id":"Q258507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$A2BF19DB-4820-4897-9FB4-DB4382CC8583","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":"Q1095643$7E001405-7832-4464-AEAB-FAE60538527B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ced3ad03b016cab254d865f917ad98c7982b337","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90003-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095643$74BA947E-2F66-4840-8F65-A4BAAFA11D51","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7fa6f17cb59358742b39fb6047c48c9f4dda1587","datavalue":{"value":"W2044614616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095643$4B61FBC4-775B-4868-94B7-36C7D7B44498","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"96da5d1a0806df6dbae76f72772fd11bba32bbfd","datavalue":{"value":{"entity-type":"item","numeric-id":3711738,"id":"Q3711738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$E37ECAC7-88B3-41CC-81A6-E93AA9FDE480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90d234667bd4cc615eaa884ce4ebca4a48af2d4a","datavalue":{"value":{"entity-type":"item","numeric-id":4172933,"id":"Q4172933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$D7EDEB7D-A8FB-4F20-BCA6-CC5B9B4E68C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74b352addabe9a91f930877bc99a4c10e3203505","datavalue":{"value":{"entity-type":"item","numeric-id":5560688,"id":"Q5560688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$E0126B7B-AD50-4B4B-8C7B-AC3E0B3853D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5126bb28c012200ac6cd9dd1fd5c2963040844cc","datavalue":{"value":{"entity-type":"item","numeric-id":4776826,"id":"Q4776826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$EFBAAA8E-73F7-4C1A-BD67-0967CD92A4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89e7325979007118002bfffe6683e99fc52b5c08","datavalue":{"value":{"entity-type":"item","numeric-id":2561483,"id":"Q2561483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$37230604-C3B0-4784-A372-A86C414C5E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a81cd6faacc1fff33a03beb0210e1ef07324944e","datavalue":{"value":{"entity-type":"item","numeric-id":4101422,"id":"Q4101422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$2F38CAEC-3B5B-441A-8954-F87EC2CFF5B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d99b374b38464d15b17b9b19bf9e5c1f9567a428","datavalue":{"value":{"entity-type":"item","numeric-id":1169276,"id":"Q1169276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$4D6A2DCF-D0F9-43D1-933A-32D43F596C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694b2e084e8bf3578a9b75d45960bffba3ec7a2c","datavalue":{"value":{"entity-type":"item","numeric-id":1169277,"id":"Q1169277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095643$5A51C422-84C1-46CE-8F17-9D34EA204487","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4ac28cca090b56d8f7ec104057683af1ca8bead","datavalue":{"value":{"entity-type":"item","numeric-id":5096232,"id":"Q5096232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d0b05a5b11b23f4384e165ac8c0288dab59300c","datavalue":{"value":{"amount":"+0.826816737651825","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":"Q1095643$949C8DB5-29A6-46AF-B1F2-2F19A167BB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"339b4d084d16afe8d23db129417be76b67c1494b","datavalue":{"value":{"entity-type":"item","numeric-id":1057638,"id":"Q1057638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc51aa709d8d425b16526d2a971517f8e68ff59","datavalue":{"value":{"amount":"+0.7119593024253845","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":"Q1095643$5A31D60C-AD52-4D90-B270-A87675FC60CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4217c11fa018b03721cf9f5e14a3f10a88322586","datavalue":{"value":{"entity-type":"item","numeric-id":3709860,"id":"Q3709860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d7a8054164da76a0be767df71ed940cf5d59c4c","datavalue":{"value":{"amount":"+0.6777918934822083","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":"Q1095643$2DF586E6-85B9-4A9F-882D-1AC6AAC31AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acaaea0cc3fa6a8d30716da35caf95fad192a27c","datavalue":{"value":{"entity-type":"item","numeric-id":1329196,"id":"Q1329196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e811e0f0caa1193cf152ed2459734f1aa87b4ac1","datavalue":{"value":{"amount":"+0.6731312870979309","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":"Q1095643$186C0C56-8F6D-4B59-A7DD-F2688F1EDD8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d619172e9c7c8b095da98b290cc2501d6ff64d17","datavalue":{"value":{"entity-type":"item","numeric-id":3340120,"id":"Q3340120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44ec6189f99cd725fe3504512e066fe480fa8802","datavalue":{"value":{"amount":"+0.6731116771697998","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":"Q1095643$25BEE072-8CBF-432F-85ED-D336BE065268","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial determination of the most-recent property in Pascal-like programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_determination_of_the_most-recent_property_in_Pascal-like_programs"}}}}}