{"entities":{"Q879597":{"pageid":881445,"ns":120,"title":"Item:Q879597","lastrevid":50093212,"modified":"2026-01-12T22:21:23Z","type":"item","id":"Q879597","labels":{"en":{"language":"en","value":"Temporal logics with incommensurable distances are undecidable"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5152425"}},"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":"Q879597$073F0DD1-EFFC-47A5-B2D3-B96E54416BD3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9ef840e2084ecb0c0fd14ce36100b66e467d341","datavalue":{"value":{"text":"Temporal logics with incommensurable distances are undecidable","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879597$5C492B0D-BD7C-4E69-B300-DEAAE145C72B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fb6b43d1ad063801cae04472520a8c1f52313e49","datavalue":{"value":"1128.03009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$2CCAC1AD-6B53-442C-95DC-F8BC6C83223F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91a6d5b55b11b7c5072badc33d9b23eaf1c7a459","datavalue":{"value":{"entity-type":"item","numeric-id":259067,"id":"Q259067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$DA655E94-BD8A-496F-B328-6A90F9076CCD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$A7043A78-A7CC-459D-802E-7FE9C9D76902","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a2af428023bb1f64e3e9e7c392bd08e7b812892","datavalue":{"value":{"time":"+2007-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q879597$853C294B-F0D4-431E-9107-6E70EB99F55B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d1cd42f4088ab74e59e25fc35cbc7b73ff9be0d","datavalue":{"value":"The paper under review shows the undecidability of linear temporal logic with ``since'' and ``until'' extended by the two modalities ``\\(X\\) will happen within one unit of time'' and ``\\(X\\) will happen within \\(\\tau\\) unit of time'' where \\(\\tau\\) is irrational. The result can be straightforwardly generalized to the case when 1 and \\(\\tau\\) are replaced by numbers \\(c\\) and \\(d\\) such that \\(c/d\\) is irrational. The undecidability proof is obtained by a reduction of the reachability problem for two-counter machines. Such a machine \\(M\\) consists of a finite set of states and two unbounded non-negative integer variables called counters. Three types of instructions are used in \\(M\\): branching based on whether a specific counter has the value 0, incrementing and decrementing of a counter. It is well known that for such machines it is undecidable whether a given state is reachable from the initial state. In the main part of the paper, the author provides a detailed account of how to ``encode'' computations of \\(M\\) in the temporal logic under consideration, which yields the desired result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q879597$2F247957-5589-40DB-85A0-0915DC5B5116","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5399c0e6c1a86c6c28134f8ba8886948fee3319b","datavalue":{"value":{"entity-type":"item","numeric-id":194999,"id":"Q194999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$CC0ACD60-3B7E-4633-9818-3F0D5047EAFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e2244b32b83bf71a9c045223e635ab074452b389","datavalue":{"value":"03B44","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$88CECCF3-50E9-419B-8809-B8692187D7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$3E104FA8-2671-4895-91D2-206BDEA4CFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$BC90D90C-674B-4A66-8B1E-E948F2F2BE51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03e82bfd314e4da7a95d47506f89b17519e6ec2a","datavalue":{"value":"5152425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$1EA68E73-F93F-4EBB-8581-1245E3ED73E2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4a6f11756e1720f07cda5a080ef0476786d909b","datavalue":{"value":"temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q879597$6CA2FFD9-3616-42CB-84A4-65C133CFD8ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eef9b077df28169ed43edc8b21b8cd30073607d6","datavalue":{"value":"metric properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q879597$7723B890-26F3-45A8-B9E7-E9E88988FC9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q879597$9A20ECD7-9348-42E0-92F4-4BEC386C2961","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":"Q879597$EE427508-ACA8-4877-A7AE-2C53B98CD18F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"545f6e7a547925281e8ee2e2ffbc849e5dfa6623","datavalue":{"value":"https://doi.org/10.1016/j.ic.2006.11.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q879597$B7DBD525-5E13-462A-B5C0-ECF30D111694","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c52ca055b515d35ded64db9d0644e8251e9a58be","datavalue":{"value":"W2131379151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$419CA954-3C76-4F9C-880D-6DD96E58E331","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e019e14c862ddaf7bcd66cd64d6515bc5dc195","datavalue":{"value":{"entity-type":"item","numeric-id":4371517,"id":"Q4371517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$96EDFDFE-A5BF-4F9A-97DF-ABC05542E2B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9f21257d8b20ccfecd3db595afbc8b2e1a0a737","datavalue":{"value":{"entity-type":"item","numeric-id":3835817,"id":"Q3835817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$17D1EA9C-9040-486A-BDA7-C734D0429C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bd2e069871eb3bf4232917297a8392cabd79fa8","datavalue":{"value":{"entity-type":"item","numeric-id":4251919,"id":"Q4251919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$7C88ED44-4995-4707-B9CE-A3AE5683DD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da4bb6f9cf8d59bb08e30fa860898c4d527ef942","datavalue":{"value":{"entity-type":"item","numeric-id":4945224,"id":"Q4945224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$68F04915-E9B8-47E0-B536-A17F6363FFC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e828e5e129d51b8575c30bc55db9c76d50bd294","datavalue":{"value":{"entity-type":"item","numeric-id":4824483,"id":"Q4824483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$18A53F97-06A0-4E76-A434-9E6B9C6AF750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b286d85c0ec526c88453b961ee0940519b5e9a61","datavalue":{"value":{"entity-type":"item","numeric-id":1780454,"id":"Q1780454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$1F1DA8CF-6CDA-4585-8FDE-B021DB4ADB6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5781430c3bcca2b0df40d4fc7fd2bfdf2c1936f2","datavalue":{"value":{"entity-type":"item","numeric-id":1323323,"id":"Q1323323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$088D1BFA-ADE7-44BA-BE6D-82A4B2516DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e499ca4910168e9fcc3cd0ad40566cb27f72097","datavalue":{"value":{"entity-type":"item","numeric-id":4953401,"id":"Q4953401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$4F3DA5A7-53F5-4C41-BA48-6831C87DAEAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1244ef9d55a97d94520b6729d409dfbb2c8e3acb","datavalue":{"value":{"entity-type":"item","numeric-id":1300103,"id":"Q1300103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879597$CA2B398E-1A99-47C6-9B69-201CBEE7EFF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b2df1d744f59f10f9284c6141d1e369016e4b69","datavalue":{"value":"10.1016/J.IC.2006.11.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879597$05EB1492-05FF-4761-9C53-0F6039B0735C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8b56134ca2322152e144d48dc7841064c7a0d9c","datavalue":{"value":{"entity-type":"item","numeric-id":3124391,"id":"Q3124391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6391cc28758b3ff5331250c3ea093450a3efea2","datavalue":{"value":{"amount":"+0.8043760657310486","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":"Q879597$2E6B3F3B-1A66-4A43-9306-395DB4D8610A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a08b9742aed72fccf004aa83edda5ac5afff1dc7","datavalue":{"value":{"entity-type":"item","numeric-id":5899090,"id":"Q5899090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6391cc28758b3ff5331250c3ea093450a3efea2","datavalue":{"value":{"amount":"+0.8043760657310486","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":"Q879597$28D84101-9F7A-4779-BA8D-8A82A4B2208A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"029d7212acda62657402710fc7f189eed94aaef3","datavalue":{"value":{"entity-type":"item","numeric-id":294640,"id":"Q294640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c22be5bc57a074c7105808c0df3124243df3abf","datavalue":{"value":{"amount":"+0.7606297731399536","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":"Q879597$1DFE6914-8966-431A-BCB6-A2D0FC565962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f162c2a21cb056d5b5f98928bc7ee53929d3de6","datavalue":{"value":{"entity-type":"item","numeric-id":1300103,"id":"Q1300103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc683f31192fcc0ec622d957556a8f795f4bda3c","datavalue":{"value":{"amount":"+0.7448769211769104","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":"Q879597$CEBA6605-E963-4518-AC72-92DE7F8EECE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3e4d5046b08b94c0812c13542cbc27d33151858","datavalue":{"value":{"entity-type":"item","numeric-id":3434497,"id":"Q3434497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a873c39797f02e64ec31521776d467b21eb1b56","datavalue":{"value":{"amount":"+0.7448155879974365","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":"Q879597$0421B4D5-F8AC-40FD-95D0-FCF9A9299466","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:879597","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:879597"}}}}}