{"entities":{"Q1184737":{"pageid":1195486,"ns":120,"title":"Item:Q1184737","lastrevid":66792018,"modified":"2026-04-12T12:53:14Z","type":"item","id":"Q1184737","labels":{"en":{"language":"en","value":"A unified approach for deciding the existence of certain petri net paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 34935"}},"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":"Q1184737$5505EAE3-6777-4327-8355-C9A53FEAAAF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"871542bd40dd2363fc8164cc2af5463a39a86f05","datavalue":{"value":{"text":"A unified approach for deciding the existence of certain petri net paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1184737$027138A2-F5A8-43BD-9739-DB530AA494D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4b577a63d1fa52c7b314e77fdac50b603aee718","datavalue":{"value":"0753.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$AEBF5585-F10E-4DD0-ADB0-960A3CF367B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4005d6001ad955fc458ecf8ca3ea1d10d9913156","datavalue":{"value":"10.1016/0890-5401(92)90059-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$5D10DD7E-B2E8-42C5-96B1-2068E2A41210","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":"Q1184737$CB9E8484-B9EB-4123-A7A9-96C6BC9E26F1","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":"Q1184737$090C6FB4-34C0-42B6-97BC-4B0CCD7BFA6E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184737$F2172FA5-FBB0-4CFE-910E-A8B9291E608F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a64b40328ef06cf07f3e978092466273482c6ae","datavalue":{"value":"An elegant unified approach for deriving complexity results for a number of Petri net problems is developed. First, the author defines a class of Petri net path formulas, each of which consisting of marking variables, variables for transition sequences, terms, transition predicates and marking predicates. It is shown that the satisfiability problem for such formulas is solvable in \\({\\mathcal O}(2^{d\\times n\\times\\log n})\\) space in the size of the Petri net and the formula (i.e., \\(n\\)), for some constant \\(d\\). Consequently, the satisfiability problem is EXPSPACE complete. The usefulness of this result is that many Petri net problems, some of which were previously unsolved, can be reduced to the satisfiability problem and hence they can be solvable in EXPSPACE.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184737$594897E0-E510-443E-B5E7-C4DDB956DFD0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$4F8DB618-2F36-498C-95DA-3CA8F840D9C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$636E24BD-A2DA-440B-8CB8-2560BF2EE27A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"57ab155a0bf59d7e8a31bf3961a66cff61071263","datavalue":{"value":"34935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$7E032F75-4CE7-4BF6-B6F1-D82D6EFC32F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7057b793a44103d2176761b3825cd1f52f5d58ce","datavalue":{"value":"Petri net problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184737$E0E04307-1C6C-4331-B74D-4A600291B652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184737$7AFFC989-8B30-4015-8015-941E3756D91E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6157837de11f2e28fe479554c99ef4c02d4ee00e","datavalue":{"value":{"entity-type":"item","numeric-id":172108,"id":"Q172108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$4ECB3F54-FBED-4EF5-B119-9F4F0180D8A0","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":"Q1184737$2600B478-3F32-4C50-822E-749C54B49836","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"92e73c5809efba966dd12389416c0f754a75bc58","datavalue":{"value":{"entity-type":"item","numeric-id":1240066,"id":"Q1240066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$E0D3EE5F-1784-4C46-9D1C-CAE3E46F4F89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2017a809bb67b92a95561991b03e86159fd32773","datavalue":{"value":{"entity-type":"item","numeric-id":3740249,"id":"Q3740249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$EC5CD9F3-FC46-47A0-AE6D-928F1655E348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007d28020364fa61db482d0ee2e50a45e3976a32","datavalue":{"value":{"entity-type":"item","numeric-id":4041633,"id":"Q4041633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$8CBA00B6-64A6-427C-B7EE-F8A25E15088F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c1db53f2b2dc3c091a66e9ebd6a9baed7c71a2","datavalue":{"value":{"entity-type":"item","numeric-id":3766856,"id":"Q3766856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$4E553256-EA33-41D2-8479-C780D1F6BAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07aba6a9c1e60cd1f9f1767cc72a1ddfd6ac66d5","datavalue":{"value":{"entity-type":"item","numeric-id":1216050,"id":"Q1216050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$593F4145-CB54-43C9-8B19-8FDCD1F52D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54b608000f5f07a4eff9f7596994ae2cbf76d666","datavalue":{"value":{"entity-type":"item","numeric-id":3771630,"id":"Q3771630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$39E999B3-398D-4DBB-98D8-3F8AF09D0301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6a514364685ad809c293991d2f0f3260bb9c4a","datavalue":{"value":{"entity-type":"item","numeric-id":1146002,"id":"Q1146002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$5C2931A8-0C19-43C1-A2DC-D02B62F2979C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08663cfc9ad28dad7443bdb814e24552eb8a9051","datavalue":{"value":{"entity-type":"item","numeric-id":1155361,"id":"Q1155361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$EEE2CD5E-EF82-4DC7-9F23-41ECC3D586B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81a6a60ad6cc5c143aaeaca19302c9e964fced6c","datavalue":{"value":{"entity-type":"item","numeric-id":1113674,"id":"Q1113674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$E859E0CD-7177-45E0-8076-687E6C8E5D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"478785c1dbc366c9782cb19b7db71424ec4c2e99","datavalue":{"value":{"entity-type":"item","numeric-id":805257,"id":"Q805257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$5AEB8DC5-F150-4FF6-B3E9-477174C54870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9efc2cab8ce7c81fa33b9ff2dfc566045d4a2a05","datavalue":{"value":{"entity-type":"item","numeric-id":3974867,"id":"Q3974867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$97D610F9-EFE0-4423-8C17-B331D5122549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e742a7f7b01578489aba7482eacdf4a4dd311e40","datavalue":{"value":{"entity-type":"item","numeric-id":1096388,"id":"Q1096388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$6C58869A-DB55-4085-A7FF-C2A175A902B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"423a50d203c459166907527e3eaa024aafe810dd","datavalue":{"value":{"entity-type":"item","numeric-id":5096177,"id":"Q5096177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$33BD8DB5-B707-4C96-BB86-1A23012F94E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a33b862f7d8441651d4cdc6c39e4250de110d1","datavalue":{"value":{"entity-type":"item","numeric-id":2540014,"id":"Q2540014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$B1CAFE1E-AF3C-41FA-AC14-1F3A26589E51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31cf1d5d871fd5755b77acd01deaa51f98e63eb0","datavalue":{"value":{"entity-type":"item","numeric-id":4164838,"id":"Q4164838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$5F890535-00FB-4ADF-A9E8-9BD70B3D2A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b270385c5f87646a288a84003f4b23432d904d79","datavalue":{"value":{"entity-type":"item","numeric-id":1149775,"id":"Q1149775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$9408D612-3D3B-42F5-ADCB-9C7FF3368E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c16932bbfeea8ec33ad70f0a2658fe162ed5cde","datavalue":{"value":{"entity-type":"item","numeric-id":3677184,"id":"Q3677184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$6FEF9E4D-5AFE-41C9-90E1-6C047CB4C49F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22bc7377b33701ee32696da1432f50457849d48e","datavalue":{"value":{"entity-type":"item","numeric-id":3891773,"id":"Q3891773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$3DD59C26-BFD1-4372-ADC7-DACFEDB1FDF3","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":"Q1184737$1466D010-FBE1-4E1D-949C-4098D0726FD6","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":"Q1184737$BF236575-31AA-4C56-BBAB-143A212F178A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5fcefe476c99319c38711cb0ff921d1e620fec1","datavalue":{"value":{"entity-type":"item","numeric-id":1836303,"id":"Q1836303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$EE9BF84F-3C7B-4905-8EE2-D3AA7FB79F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0863235db59889cae8e307ac033932805be9713f","datavalue":{"value":{"entity-type":"item","numeric-id":797285,"id":"Q797285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$A006D567-4AEA-409E-9254-FA2256D907B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e4742fb3b3c48c73bcf3c896ebed6b9469ae658","datavalue":{"value":{"entity-type":"item","numeric-id":1158763,"id":"Q1158763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$1C6D61C5-A669-4BAF-BF1B-7FCD997C440A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69a3953b3ff68b1c4568f11da96aef064e716710","datavalue":{"value":{"entity-type":"item","numeric-id":4136592,"id":"Q4136592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$2CADA668-1277-41DF-8500-63844E96943C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d111f686b4278fdf8b58b1d04a8ed095951a5ec","datavalue":{"value":{"entity-type":"item","numeric-id":1158764,"id":"Q1158764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$251FBDB7-4E49-4E10-AE98-91BC30C5C4B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b42ebd88cc89172ff9db3c6cc6a1cd238e586f0","datavalue":{"value":{"entity-type":"item","numeric-id":1057065,"id":"Q1057065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184737$C9C75762-22F0-4FE8-9B6F-EF63AAE11924","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ba3927404f29671e48c27e846bb0e8e743a3f59","datavalue":{"value":"https://doi.org/10.1016/0890-5401(92)90059-o","type":"string"},"datatype":"url"},"type":"statement","id":"Q1184737$7AE4A3D8-6F44-4DD4-BDF3-19930157BF18","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b815864dc664d373f46ae3d7607b99d8237d38c5","datavalue":{"value":"W2044858512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184737$05C46347-D152-4490-8D87-AEEAD1604D4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a2720362e7457cc1e97744f038f45859755eb89","datavalue":{"value":{"entity-type":"item","numeric-id":1364130,"id":"Q1364130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80ae651610cd0a66a5e986320888aea8b6be34aa","datavalue":{"value":{"amount":"+0.8401484489440918","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":"Q1184737$E760E08D-F78A-41A3-B183-4A7607A65821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc5091980047d98619a4c1c8c32465bc3af4bef4","datavalue":{"value":{"entity-type":"item","numeric-id":3646251,"id":"Q3646251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ceb29eb8ffaa30446b7fa9581069209d20c57de","datavalue":{"value":{"amount":"+0.823026180267334","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":"Q1184737$539C7480-C13B-4D27-B703-0CF2BC5C88BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f10ebd27a7f9566847e998f1de3407a6db90066c","datavalue":{"value":{"entity-type":"item","numeric-id":3016216,"id":"Q3016216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0435c69c5a67789a619ed189d3787e8917762f2d","datavalue":{"value":{"amount":"+0.8229273557662964","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":"Q1184737$81B907C4-3709-4BAF-9830-9DF6A0C66D2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f27b0685b28cd60f94d63ebc03be03f4eeb199a8","datavalue":{"value":{"entity-type":"item","numeric-id":3082923,"id":"Q3082923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89a258c220468398822845ea1fac3e7fc9e550c8","datavalue":{"value":{"amount":"+0.8145371079444885","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":"Q1184737$EA8C2C04-9D15-4BAB-9F5C-D43DD1917280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be169180d9229e1d0ebd919932db621a9bb6e7b1","datavalue":{"value":{"entity-type":"item","numeric-id":3766867,"id":"Q3766867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"603cd12b81c5f0721e7da847d4eef4fd6e05a5fc","datavalue":{"value":{"amount":"+0.7814446091651917","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":"Q1184737$01FD104E-F206-43FA-BAB5-2C32EF450064","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A unified approach for deciding the existence of certain petri net paths","badges":[]}}}}}