{"entities":{"Q1098622":{"pageid":1109374,"ns":120,"title":"Item:Q1098622","lastrevid":66127104,"modified":"2026-04-12T07:43:49Z","type":"item","id":"Q1098622","labels":{"en":{"language":"en","value":"The complexity of reachability in distributed communicating processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039276"}},"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":"Q1098622$1EDB3796-331A-4456-81F7-4815ED2575DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b3c2bb30ee8b307a8fd9cdc9e3c1adff9d162ce2","datavalue":{"value":{"text":"The complexity of reachability in distributed communicating processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098622$6C61C63F-0F45-4790-8691-BEB018BDC94C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"351bc19b9a571754b2a70e9686dff5eab20572f7","datavalue":{"value":"0637.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$6D1DED1A-1E12-4304-A488-D8124BAE5E80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"37c502775fab8330f538a6252107a5a58354fa2e","datavalue":{"value":"10.1007/BF02737107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$4EFF9EE3-E8BD-4AA3-AC2A-8F67FDF2E2D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$3CC11EC5-915F-4A09-AE30-D783B54703EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f8d39e08371c895d256df63166d986e8797f46b","datavalue":{"value":{"entity-type":"item","numeric-id":498914,"id":"Q498914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$6C899DA4-F41D-41D2-9923-64B5FE96EF21","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":"Q1098622$72C781AA-8D08-4298-A4E1-E70527D5E7D3","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":"Q1098622$18268BF5-EA38-40E1-91AE-6E9F335A5106","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a436a2a48bc4a8de6f3f7198165dc86e1eea756b","datavalue":{"value":"A crucial problem in the analysis of communicating processes is the detection of program statements that are unreachable due to communication deadlocks. In this paper, we consider the computational complexity of the reachability problem for various models of communicating processes. We obtain these models by making simplifying assumptions about the behavior of message queues and program control, with the hope that reachability may become easier to decide. Depending on the assumptions made, we show that reachability is undecidable, requires nearly exponential space infinitely often, or is NP-complete. In obtaining these results, we demonstrate a very close relationship between the decidable models and Petri nets and Habermann's path expressions, respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$92F62BEC-518C-415A-97A6-CCD202138FE2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$9B73C37E-1610-45B6-A4D8-F28F1E26D6BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$A60FE29A-58D1-4755-89F6-4B1CC88810B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$C11C6D43-381A-4D1E-B72C-8411AF7748B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"081f0a907cbef7500cc87b18579ab159e1a801f6","datavalue":{"value":"4039276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$61074F4D-69EC-4243-8CCC-44DC02A813BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb30f6fb39388d1fb612150f5e69372740c7cc58","datavalue":{"value":"communicating processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$9AFFDCD9-C4C8-44E0-B90C-11C1858FE6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce9a6aaefc6b8b4a31a4503712ed9a9e2b300d87","datavalue":{"value":"deadlocks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$F047CBA1-6735-4743-A126-8716CC611522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$E6199B02-D80D-45B5-9AE9-9C854661D0D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a618b40b0e1c60d8f3695a0363009e29e3d436f0","datavalue":{"value":"reachability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$7A28D8A6-505A-4F46-95FD-CF10C23AE350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b40a0d0101dc1820317a5d5ac8f390d8512ded80","datavalue":{"value":"decidable models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$B869F94F-73E0-4A94-B00E-BE1885C296F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01a2e30b6f10c98d548518426a25a350ad19ecc5","datavalue":{"value":"Petri nets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$DDF7F8D2-4876-42FD-866B-5B353D4442B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5f63c488034aa9603e93163be3fc1ea3a704856","datavalue":{"value":"Habermann's path expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098622$AB2FBD82-707E-44BA-B23E-931A3B842E1F","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":"Q1098622$BAF2B3F9-2998-4AC1-BD14-1A91A0090411","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a05f05f61b46a8fd8bda9fb47a75f81f498f2f8","datavalue":{"value":{"entity-type":"item","numeric-id":3657436,"id":"Q3657436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$55CA8EAC-7769-4C58-B6FB-2A862AAA3140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$536CB825-6EAE-42EB-B802-4F0AB04EE1E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"517c6335b9751d14b2fc9631b27156b3bf1ac609","datavalue":{"value":{"entity-type":"item","numeric-id":4194422,"id":"Q4194422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$12B504E6-826E-464E-89C3-5C28560E255D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acd1e2ae2bde1209612fa64c464d43a7fd5c9616","datavalue":{"value":{"entity-type":"item","numeric-id":3780411,"id":"Q3780411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$8CD3502A-AF84-43DC-A57A-FE4A5BB09287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f70028e31ae896a0df7dcbc67d83856a5a6ec6a","datavalue":{"value":{"entity-type":"item","numeric-id":3677157,"id":"Q3677157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$230EDFA8-C5ED-4FD4-B67F-AC21C6E39044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d13b2baaeba9578e51f0f16124df9d341fafb29","datavalue":{"value":{"entity-type":"item","numeric-id":4162449,"id":"Q4162449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$8EF776E5-2D1B-4C08-8FDE-5820331BB404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004642c985382b5c70e78b542aebcb6240614609","datavalue":{"value":{"entity-type":"item","numeric-id":4162644,"id":"Q4162644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$C15E4463-9233-417B-BA07-B6CD9CE9E53C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57375aaeb2518d9af85d4868f1b2eb7c14017efa","datavalue":{"value":{"entity-type":"item","numeric-id":1146980,"id":"Q1146980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$AF51647E-201E-471B-B8F4-0B5771B44226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbc8272a2eed684dcc743719a6651c947badf1e2","datavalue":{"value":{"entity-type":"item","numeric-id":1836661,"id":"Q1836661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$594FFA9F-8891-43C6-B29C-C4B88BFFDB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60da585cac100a31c125360c9cbd2d207cbfe7df","datavalue":{"value":{"entity-type":"item","numeric-id":1148667,"id":"Q1148667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$B6EAD4F7-67B4-4F46-AF1F-2FB6C33DD596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1b26bdc210a3d291b796088837bddd84cce8b4c","datavalue":{"value":{"entity-type":"item","numeric-id":775202,"id":"Q775202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$A7107B94-81E5-480F-8245-9CC8332EF505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b5467bac8c2b14c65957d9305470ea5fcf1d67","datavalue":{"value":{"entity-type":"item","numeric-id":3911403,"id":"Q3911403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$98E233B3-072F-4CD0-9907-B3F5AE7B3171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"840c3498537d17d4f80bc9be5196dacc95600a62","datavalue":{"value":{"entity-type":"item","numeric-id":1242682,"id":"Q1242682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$D65F1048-D971-4A87-9391-094C7000DED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d41130d929b557eb6098b4637331c9cf6c8ff15","datavalue":{"value":{"entity-type":"item","numeric-id":1064050,"id":"Q1064050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$4609FC6E-7DE2-4968-9ED3-08E02D589F3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b952c0db66a7d048480e0afa7ee8b9fcfe34b91","datavalue":{"value":{"entity-type":"item","numeric-id":751233,"id":"Q751233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$C1D579A3-969D-4F27-9F4B-A10BFC2C4B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"969b23c15bda365fef0dcb143b85f2f64b2e439b","datavalue":{"value":{"entity-type":"item","numeric-id":1819938,"id":"Q1819938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$43603300-2989-47F5-AA27-FB740EBFEB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47e08e646cc60a69173bacb6efb1dfd0d6227f05","datavalue":{"value":{"entity-type":"item","numeric-id":1819939,"id":"Q1819939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$0CB7E010-234D-4F44-A883-CF498117E5A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a7be8e298cb87bd430b3e305916df543385d249","datavalue":{"value":{"entity-type":"item","numeric-id":3912034,"id":"Q3912034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$2AFB0D35-18BE-4D1F-9134-1B33CABA02BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53ff0a420feecc8124e674d6ad3dd21b8ae9afad","datavalue":{"value":{"entity-type":"item","numeric-id":3912035,"id":"Q3912035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$F87A314B-C1BA-4BCC-AF5B-88E24236C281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175f563c238c6df4ddc789404abf4b9fdce5a158","datavalue":{"value":{"entity-type":"item","numeric-id":1054479,"id":"Q1054479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098622$6A143EDA-3003-4EF9-953F-646468FB7556","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd4b12a4d1cc673012a944e778d0693fef621d0c","datavalue":{"value":"https://doi.org/10.1007/bf02737107","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098622$C90FB88C-B3B8-4BDC-8C0A-09A1509BED6E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"608b2a863ecf4dc7b489082844a58a1f8dfed4cb","datavalue":{"value":"W4253760428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098622$3A4E9874-D7DC-4B22-BF2C-1E7116EB36F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a196d9c5f3bff794461cf0bbea2064fec39a530e","datavalue":{"value":{"entity-type":"item","numeric-id":1323365,"id":"Q1323365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c42e483b854eb3782c2a02897e5797a1cd9ec610","datavalue":{"value":{"amount":"+0.789394736289978","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":"Q1098622$9DFF9B85-AA92-4009-ADD5-539715F1C2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"554bf77d78742feda939905c06b60601fbbaf191","datavalue":{"value":{"entity-type":"item","numeric-id":1064050,"id":"Q1064050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a63fa704994b704b960f4eca1f95f3f320b5948","datavalue":{"value":{"amount":"+0.7767444252967834","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":"Q1098622$8E658128-85B1-46A5-8065-3428611A1E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50181b29e5d2a25af61306fd84291fe65c150e96","datavalue":{"value":{"entity-type":"item","numeric-id":3201754,"id":"Q3201754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"956e45bab121de9dce50f45d5ccafbfe8cf687c6","datavalue":{"value":{"amount":"+0.7754923701286316","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":"Q1098622$70036102-8E5C-40CC-8760-298B9C36243A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb492f3a744c276b7ffd4c481bb1baf3a481b0f","datavalue":{"value":{"entity-type":"item","numeric-id":5894957,"id":"Q5894957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd9296fa2e517c032f8fc6984adca73886cde4c6","datavalue":{"value":{"amount":"+0.7642159461975098","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":"Q1098622$C6302FCA-7575-4439-A2E3-C79E2A8B42D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"409c70f02aac18578df15bcd918a7c2cc9ebfd82","datavalue":{"value":{"entity-type":"item","numeric-id":3700823,"id":"Q3700823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ac2394d937b5daabfdc2b8a793eb31dac227ba8","datavalue":{"value":{"amount":"+0.7562210559844971","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":"Q1098622$5D0F36BD-5827-4507-A5AF-99777397065F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of reachability in distributed communicating processes","badges":[]}}}}}