{"entities":{"Q758201":{"pageid":760050,"ns":120,"title":"Item:Q758201","lastrevid":49480960,"modified":"2026-01-07T05:57:44Z","type":"item","id":"Q758201","labels":{"en":{"language":"en","value":"Priority systems with many identical processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4195174"}},"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":"Q758201$52CEFFC2-E25C-41B8-8199-BE97081578B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c11495ee4dcfbf0e8654806ee65bcbc6277162a1","datavalue":{"value":{"text":"Priority systems with many identical processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q758201$6738733C-76D8-49FC-A273-86C3762EA8AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db771825ede632cc75844e8163c166da36bd32de","datavalue":{"value":"0724.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$FF98B906-E770-44BD-9091-CC88860576A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2f814e32a9013b3ff4475a643092ae22024ed16","datavalue":{"value":"10.1007/BF01178682","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$CF4EB1F9-6F72-4E0A-9A68-D286BBB474ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef70989854b46304c6274e59f7064331acfcdafe","datavalue":{"value":{"entity-type":"item","numeric-id":344509,"id":"Q344509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$B5CF6FB2-C481-4820-BA3B-998C3D0ADABB","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":"Q758201$D47B7C13-5390-4F66-BE1B-9994507D303E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q758201$AD9358E4-19EC-4591-B8BD-A22E87488E23","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34c8beaffe05b752b1bf11be629ce87a70123ec5","datavalue":{"value":"We consider the termination problem for systems with an arbitrary number of identical priority finite-state processes. In our model, the number of finite-state processes involved in the computation is arbitrary, and a priority is assigned to each transition of a process to indicate the degree of importance or urgency. We show that the termination problem is undecidable for such systems, even when the underlying interprocess communication structure is a star. The undecidability result holds for systems with acyclic processes as well. However, if we require that no two processes reside in the same state (except the starting state) during the course of the computation, the termination problem is PSPACE- complete. Finally, we show that if the priority relation is empty, the problem become PTIME-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q758201$98975D3C-FE9B-4491-AD7D-201186BA3BA9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$E277660D-D2BB-415F-9FF9-859EC66F9060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$4AED43F5-5124-4055-9280-4B766BC8A609","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e59111ce2ee97be14d4d41dc746288e3d1e6c9f5","datavalue":{"value":"4195174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$60EA63F5-F853-4F9B-A2E8-A19CCFE04EF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3564cfb2f1ef130c73c02739f2143815aa63770","datavalue":{"value":"priority systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q758201$9D8383D6-FCF8-4694-B069-B2B35B069A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e5da8d739bd6e8497332d812db4110025659caa","datavalue":{"value":"processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q758201$392CCC97-84D1-4CE8-9968-41732629813C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4befa4ca20f2beabcfa09e8a92ae13c21cb4934a","datavalue":{"value":"termination","type":"string"},"datatype":"string"},"type":"statement","id":"Q758201$1E3A2051-AE04-4674-AE6E-AF2CBB402FE8","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":"Q758201$BAF1885A-2711-4B51-B6E9-5401E827B496","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"731fff832e7711198e063399154f72f88c50c123","datavalue":{"value":{"entity-type":"item","numeric-id":3719811,"id":"Q3719811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$205CF272-3C82-4E4F-83CA-FAC98C50A5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11ce10f2c105db58ec72d58d5665464175b07498","datavalue":{"value":{"entity-type":"item","numeric-id":921983,"id":"Q921983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$1A2A9A7C-3DF7-47DE-BDC7-21492CD02921","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":"Q758201$36F81AE6-AD94-4333-A282-817C88B2D9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$99D28FFE-9A82-4A43-AC1C-8B36646CBA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$11DCE4C9-920C-4EE3-8538-C4BA93CDA7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c6f47cc4b63b7396b12f080e9f12aef7d17d05b","datavalue":{"value":{"entity-type":"item","numeric-id":1111384,"id":"Q1111384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758201$F01692B0-FC96-424A-8FBB-42867E28544C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5c090c15d2fe10361fc7b407ee3e655101b6c12","datavalue":{"value":"https://doi.org/10.1007/bf01178682","type":"string"},"datatype":"url"},"type":"statement","id":"Q758201$5D49BAD0-80CD-4D70-A00D-DAF7772FFABA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7b36080e1e7561d07fc270183a96ebc650985dfb","datavalue":{"value":"W2063886314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758201$03BAFD1A-FA17-4E26-A890-875120670006","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e528144a2fe1e93b801ef9ab63404b50b115589","datavalue":{"value":{"entity-type":"item","numeric-id":3034829,"id":"Q3034829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5a39cf811d30f7370d93b1406f26027a7d13e60","datavalue":{"value":{"amount":"+0.7861233949661255","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":"Q758201$437B40A9-9F11-4C67-BD8F-48F25C4A3693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aeb892c23045d1f7d36b4bad8c60f0dadbe4936","datavalue":{"value":{"entity-type":"item","numeric-id":3677157,"id":"Q3677157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a78dd8e4f29b6d57d2dfa2f210654652a3e5992b","datavalue":{"value":{"amount":"+0.7571424245834351","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":"Q758201$F10F0E48-732D-4794-9269-51FA154C898F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf7295fcd5233cfdcf83fc78f131cbe89109e0c2","datavalue":{"value":{"entity-type":"item","numeric-id":3216146,"id":"Q3216146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eddb80a5326c686ffa4e7807bb0a5ae565fd42c","datavalue":{"value":{"amount":"+0.7482705116271973","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":"Q758201$99D33790-8F99-4F80-B698-5E945388612B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8de0636c483e9b3bc4b2de85f173747e49c5095b","datavalue":{"value":{"entity-type":"item","numeric-id":5891112,"id":"Q5891112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62eec904a3b28a2c490701f9d6711456dbae5c72","datavalue":{"value":{"amount":"+0.7395594120025635","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":"Q758201$6114F49E-B93C-455E-9697-FEAF3F011AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a725b6a2c8eb1af8742bf241c2640dde44596361","datavalue":{"value":{"entity-type":"item","numeric-id":1111384,"id":"Q1111384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb509670dc20222625d86f3a2953cdcc1e453760","datavalue":{"value":{"amount":"+0.729735791683197","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":"Q758201$61A59586-AFD0-4157-B833-6595231426C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:758201","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:758201"}}}}}