{"entities":{"Q5958761":{"pageid":8135563,"ns":120,"title":"Item:Q5958761","lastrevid":47755915,"modified":"2026-01-02T14:57:05Z","type":"item","id":"Q5958761","labels":{"en":{"language":"en","value":"Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715806"}},"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":"Q5958761$CD72D13C-1420-4959-859C-BBB61D6AAEEA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"678782bc69367784a2a6c9e728fa7efa6a90c64c","datavalue":{"value":{"text":"Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958761$73E38693-5BE5-47AC-B070-A0DB1A7022CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51fe881b5aac236e312789a4d57605c5701bd729","datavalue":{"value":"0989.68134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$B9F31509-3367-461B-8FB1-5E70934F6722","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57f50098f57f89bc3e4a1252899c152f718caa93","datavalue":{"value":"10.1016/S0304-3975(00)00177-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$10FBED86-6830-4941-A5D9-8FF689FCCF8D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efac51dcc1eb2d5cac55235eaabda5656de44b25","datavalue":{"value":{"entity-type":"item","numeric-id":590526,"id":"Q590526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$0D2AB551-4AF8-41AB-AE1E-4D4B09889988","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":"Q5958761$BC1FA44C-DF85-4F5D-9FB6-7AA327532084","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958761$A9D16A65-8011-4F43-93A8-F1DE7572F5BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d73f705bde5a28b9fa540b9e46c057f061eaf002","datavalue":{"value":"We study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. We show that deciding consistency of a set of constraints in this class can be done in polynomial time. We also present a variable elimination algorithm which is similar to Fourier's algorithm for linear inequalities. Finally, we use these results to provide new temporal reasoning algorithms for the Ord-Horn subclass of Allen's interval formalism. We also show that there is no low level of local consistency that can guarantee global consistency for the Ord-Horn subclass. This property distinguishes the Ord-Horn subclass from the pointizable subclass (for which strong 5-consistency is sufficient to guarantee global consistency), and the continuous endpoint subclass (for which strong 3-consistency is sufficient to guarantee global consistency).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$D57B4510-78BA-4844-B118-6E9E3E3EB9BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$931D73BE-0812-4889-B48A-34EAF0654B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f66a3c6f6c4263d812ea49e5394cac6ea83ef9b","datavalue":{"value":"68T37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$59F36AC0-8FDD-4BFE-876A-20C0E7AFEC47","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0fbbdbbdfba125efedba5fbc0a76283da1a23b1c","datavalue":{"value":"1715806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$FBF113D8-E54F-43C5-A7B1-E74E43F7876C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92547f21222746690d4fcfd11099e70aa605287c","datavalue":{"value":"linear constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$77161AA8-72A9-48AC-B581-4DFA9E46925C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50eedba58bd14a3b7ea76b9e1071f65a108a0fee","datavalue":{"value":"variable elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$AC447FEF-52C3-49E8-9DB5-FB54957E4C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d780047ac39ad8365014826f4e9ae3d1d3cbc397","datavalue":{"value":"interval algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$EB1860C4-6F74-4EB8-A503-2EBB18E74F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed94a2bccc22f53c8e0b924181884a60e73a93ee","datavalue":{"value":"ORD-Horn constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$FCBF9D78-D275-4A03-8F3B-1C7BC30F0D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5544268a6d3ebb4de3bc8a936abe06a2ffd1f99a","datavalue":{"value":"global consistency","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958761$103360F4-6628-4BDD-8F31-768CB875E61F","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":"Q5958761$BE4DB3FA-58EC-4C89-AAB4-CF57FABF22B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8367121d54df3344ae45fb7bcd26909ca7d18f9","datavalue":{"value":{"entity-type":"item","numeric-id":64672,"id":"Q64672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$AA5309B0-EABE-4199-976C-66779088ACE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1dcbf7871c1ff53227c5ff389b961ae0ad02f7b","datavalue":{"value":{"entity-type":"item","numeric-id":1124348,"id":"Q1124348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$30944885-2A85-4EAF-B4F0-974FF170AB6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ae21862e335541805a61105154ab0dbdc1d3849","datavalue":{"value":{"entity-type":"item","numeric-id":1193482,"id":"Q1193482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$5DF1DE20-200C-47B3-8D70-537C05EE2198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec3e69cdcca7384fabc1c1a8e32f234be1bbc87","datavalue":{"value":{"entity-type":"item","numeric-id":1182161,"id":"Q1182161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$1AF81912-2088-44CF-90D7-C3930276FE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3322157bf6a01189b1807437698fe608048635ac","datavalue":{"value":{"entity-type":"item","numeric-id":4167597,"id":"Q4167597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$C87E6AC8-58C6-492A-8ED6-0C62E8AEFFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1958ff7e040b608ab81be40fc268247c86c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3933756,"id":"Q3933756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$FE59B04D-B024-48F4-9109-F5419E1AD09F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$0088AA23-5617-43E3-83A5-57069E4EC24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30b59cce907cd6230fee251f3914e5f8ab444162","datavalue":{"value":{"entity-type":"item","numeric-id":3140558,"id":"Q3140558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$3A14D605-7A0C-43B4-B337-912F7C357768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1c39230728710dbdbad9cfbac4df4bd9c36db58","datavalue":{"value":{"entity-type":"item","numeric-id":1274294,"id":"Q1274294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$174E9A41-E8BC-4EDD-9E0E-693D570C4ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$FFECCD3F-B07A-417D-B0F3-8A3762FC9A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53ff909517e1c9c3ac6244dd63705ee7e061981a","datavalue":{"value":{"entity-type":"item","numeric-id":1339729,"id":"Q1339729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$5477CBBC-122F-42C5-A8FE-3EEECE91C2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6b3cc8af5f7ebc8c7e49de7b5e82d63784ab1c2","datavalue":{"value":{"entity-type":"item","numeric-id":1391930,"id":"Q1391930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$9D108C4E-C36E-4EC6-A9E9-62BCDD4576CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"045eecf891187063747cb4e61ef88442c2a876ac","datavalue":{"value":{"entity-type":"item","numeric-id":1369238,"id":"Q1369238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$9FA565CB-DB02-4ECC-9A90-6F6017AB4902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fadc5cf24e278649059b488e3339f3114001128","datavalue":{"value":{"entity-type":"item","numeric-id":4305669,"id":"Q4305669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$0C9C8AEB-2779-4142-8F8D-C0A8C742607B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eafd1eb7cfc9c85a5ed540ab8f6356e006aaa99f","datavalue":{"value":{"entity-type":"item","numeric-id":1186697,"id":"Q1186697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$000B17F5-4A5F-4C26-BAAB-227688670778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d34da21d2e3fa3e67c2ba7ad8a54e7566b0adae6","datavalue":{"value":{"entity-type":"item","numeric-id":4369856,"id":"Q4369856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$F00B2E23-176F-4194-99E9-BCD369406C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$49AB1811-DC03-4220-A0DA-C166B4B1CFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfce0c06de5645e33e81141a9d32398ea1f4d485","datavalue":{"value":{"entity-type":"item","numeric-id":1063589,"id":"Q1063589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$A290E05B-2209-4E77-9343-1BE32E925C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35aa0794bdae11886d3f804870a70001df3c61ee","datavalue":{"value":{"entity-type":"item","numeric-id":1204871,"id":"Q1204871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958761$780D451F-82DA-4381-B45A-8711D757EDF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1419e0dcded1251217cd2ed6e6667ea87edad388","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(00)00177-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q5958761$976DDB5B-CDE6-4591-9D24-FFB3C4CCC4BD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99f5c842929916ff2e583fd47b015d3088c35fe8","datavalue":{"value":"W2081744921","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958761$7F9AED29-8980-493B-989E-6E53E6CE7E59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbeb9100ea31946b72f2a7a1be41c62b876b730c","datavalue":{"value":{"entity-type":"item","numeric-id":4369856,"id":"Q4369856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ef172d75ad32376c5ddc7c91c17207ad327287a","datavalue":{"value":{"amount":"+0.828277051448822","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":"Q5958761$F110D6D5-EA25-4F63-A534-F8CA0D71B285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3322460689d578fd149859be8c1c0e6380cd9056","datavalue":{"value":{"entity-type":"item","numeric-id":1274294,"id":"Q1274294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cb6b936d04b8e3e1eae67c3823c982adc1b9504","datavalue":{"value":{"amount":"+0.8098092079162598","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":"Q5958761$FEA32CA3-2C39-41B1-8375-BE6FBCA3E992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3c5b5769412647de07e381584a77f6ef3e1792b","datavalue":{"value":{"entity-type":"item","numeric-id":1402726,"id":"Q1402726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ffd636df31b720670dfeb748bc45dbe746cabff","datavalue":{"value":{"amount":"+0.8055627346038818","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":"Q5958761$D4555404-6B4B-408E-B5BB-F2497B0A2103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a67dec3a4167df1718bfcda27a02d236bf643d98","datavalue":{"value":{"entity-type":"item","numeric-id":360099,"id":"Q360099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ffd636df31b720670dfeb748bc45dbe746cabff","datavalue":{"value":{"amount":"+0.8055627346038818","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":"Q5958761$7FF9B8E2-9242-4101-AC61-13FE06DDB2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db71374b13fec07431b0e278e8cda46534e68542","datavalue":{"value":{"entity-type":"item","numeric-id":3452504,"id":"Q3452504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02034ade4501ac4145ef359c19d8196c9cdd6937","datavalue":{"value":{"amount":"+0.8009980916976929","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":"Q5958761$38220FC8-DF92-49CB-A427-94C9D959B569","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958761","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958761"}}}}}