{"entities":{"Q1819937":{"pageid":1830679,"ns":120,"title":"Item:Q1819937","lastrevid":69402369,"modified":"2026-04-13T06:45:51Z","type":"item","id":"Q1819937","labels":{"en":{"language":"en","value":"On the finite containment problem for Petri nets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3995065"}},"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":"Q1819937$9EDE3956-7C45-4044-A9EA-F3CA9B81F95A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a29d6db6960df4baf3f94db9b1a4b9d1abbe886f","datavalue":{"value":{"text":"On the finite containment problem for Petri nets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1819937$C44F1D6F-8257-41DF-A67C-8E170949ACEF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84177110c63362fe6d152438f127952c9aecb17e","datavalue":{"value":"0614.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$C54011FA-7236-4B19-A56D-FB29E9578D65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1c6d8fc2111769f7f3ff130204b71f167b951672","datavalue":{"value":"10.1016/0304-3975(86)90169-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$4F6F10C0-EBB8-4A2D-BAB1-EF63A13E53BB","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":"Q1819937$9B70015A-C955-41AA-8B2D-863137F3CB8C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1819937$C7BBD940-0625-4F50-9E98-0A0B2BA21D8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e117aa9e19bf025760443fe5b7be2bb2ced277fa","datavalue":{"value":"The finite containment problem (FCP) for vector addition systems (VAS) is to determine, given two VAS with finite reachability sets \\(R_ 1\\), \\(R_ 2\\), whether \\(R_ 1\\subset R_ 2\\). The paper shows that FCP is DTIME(Ackermann)-complete, sharpening previous results due to \\textit{K. McAloon} [Theor. Comput. Sci. 32, 173-183 (1984; Zbl 0569.68046)] and to \\textit{E. W. Mayr} and \\textit{A. R. Meyer} [J. Assoc. Comput. Mach. 28, 561- 576 (1981; Zbl 0462.68020)]. The principal technique is to replace an application of the infinite Ramsey theorem by a certain finite Ramsey theorem yielding an upper bound for the height of the Karp-Miller- covering-tree (coinciding with the reachability tree in the case of finite reachability sets).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$CDCAADE2-C615-402D-9BA0-16735F07088C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$4F458BB5-D0F2-4B12-9AB4-0A0243916EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$5CDDA4E2-0434-4F22-A3CD-E4BD70247229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$6CEB07BF-A62F-46B6-8603-514E64DCE086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$208AB627-154F-4BB7-AB53-48D8D1F1159F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$FE91E4B1-C507-47E9-B9C1-5C04189635CE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02b0ef92d72cf204f9dd967ccaaf5dca1f741623","datavalue":{"value":"3995065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$68D7C575-C66E-45E0-AAF6-928861682F66","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c366d9e44e0d6a9e2cdc753868eab05ee1b2ecc","datavalue":{"value":"Ackermann function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$FF5383B9-37A8-4E05-82B1-3075BA9E90F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"082b40668ec602906f70044eeca5ef4c25b0216d","datavalue":{"value":"finite containment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$6F65B85D-7EBA-4271-94EF-56CC6251E2B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01596681fec0062ebe65a0738936e768a85631a0","datavalue":{"value":"vector addition systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$5E78FA36-8375-49E1-8A9D-1D2127D48A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4cb1ac7b9b5d3abab510302311a9c6ed936475c","datavalue":{"value":"finite Ramsey theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$32204CE7-F9F6-495B-85AB-7BC76E63E620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87960966b829079923127df88d1cef9d43b4053c","datavalue":{"value":"Karp-Miller-covering-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819937$36F56430-C4A1-42F6-8858-57DDAB4E3854","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"156c797a905a5f3fee298ee2b9f132ba806e98a8","datavalue":{"value":{"entity-type":"item","numeric-id":455764,"id":"Q455764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$8BCFACD1-EE31-4C27-A769-053CD9A915C0","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":"Q1819937$1246A414-E0D3-414D-AB9F-C09D5A92DCF6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"54dffb120cb495a363093a222df3755c39ec8ce6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90169-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1819937$A90B4E1C-4A7D-433D-8D02-F00E295E688C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec07173f009869f1a1edeb50e709ec57c3b73630","datavalue":{"value":"W1985986492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819937$A73A5177-A5E4-49ED-8606-BC6C5DBED497","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8029b47f81e182b3772dcb12d41202333d7553de","datavalue":{"value":{"entity-type":"item","numeric-id":3035687,"id":"Q3035687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$1D15ACD1-30F5-4CC8-AD2E-DEC0E381D2D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0755527dc26ccf06e69cd62ec76a91e4b8d0335c","datavalue":{"value":{"entity-type":"item","numeric-id":3903002,"id":"Q3903002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$7D7A083D-4639-48C5-B34D-631D84D7F4DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6981775c3bdaad566fe065afd3c04ece6176878a","datavalue":{"value":{"entity-type":"item","numeric-id":1238997,"id":"Q1238997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$EB8CBB41-8AB6-4EE0-BD5A-7EA1B2502695","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":"Q1819937$C3AD9E21-98F1-4506-A816-BD84965DEDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e243aafa636ab09d990564f754a991e6ab8e8228","datavalue":{"value":{"entity-type":"item","numeric-id":1168967,"id":"Q1168967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$0FC6E9A6-A35C-4077-B639-6F0B00B5E85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3959ffb868545a66d56438fcd6e21698cad3375e","datavalue":{"value":{"entity-type":"item","numeric-id":1060848,"id":"Q1060848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$563FCE5B-73A3-4356-B3C7-96E859F013ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ec5d09b5c750f80e0bef8173b6beb42d02f375","datavalue":{"value":{"entity-type":"item","numeric-id":3912016,"id":"Q3912016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$2FA7DC05-3ECD-41E6-A887-C8D4F8272179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d756a2dbfc42ad957c96a9182383cf86faa5a35","datavalue":{"value":{"entity-type":"item","numeric-id":3893931,"id":"Q3893931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819937$F03A0C08-C47B-4EE5-AD33-2BF530F86697","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":"Q1819937$02695E49-7A93-4365-B23B-0ADDA7A5C00D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c85481ba63d7b439b9c15b3e542b096bdde2fb6","datavalue":{"value":{"entity-type":"item","numeric-id":1060848,"id":"Q1060848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b1b771de09e7fece1432d0b0bf3ecfd643a11d5","datavalue":{"value":{"amount":"+0.8429815769195557","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":"Q1819937$5ECBCDF9-0423-4AFF-9527-9E3AD08EBDB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ee6bc36eb8240d0762a30665c49e403a3cebfe0","datavalue":{"value":{"entity-type":"item","numeric-id":1096388,"id":"Q1096388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a28846d2f9723dac87e5756b29006d7d4dfc1cd","datavalue":{"value":{"amount":"+0.824021577835083","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":"Q1819937$8BE2BB0B-28EE-4E83-A629-031899BD2D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"418b676e5712991c8624e5454b553ba95105ba09","datavalue":{"value":{"entity-type":"item","numeric-id":3776647,"id":"Q3776647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2ae73403a992568ebb8884a2351d25759d9b101","datavalue":{"value":{"amount":"+0.8119863271713257","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":"Q1819937$3F93C8F6-4B89-4B6C-9C60-1367100B5FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b97a0ffecde032f3cf497744f901e6271492bd","datavalue":{"value":{"entity-type":"item","numeric-id":3677184,"id":"Q3677184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d805a636511dd7874e944a4fc5e001c91422356","datavalue":{"value":{"amount":"+0.8098891973495483","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":"Q1819937$225843CA-CAFE-440C-B226-5ACFFCE6B57E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38b3ac7f8e47a33fbc1855fe7f9e764cc79b640d","datavalue":{"value":{"entity-type":"item","numeric-id":1819938,"id":"Q1819938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34ea65eeed1d7ff14c3f6170d40ad53a0d9d6ae8","datavalue":{"value":{"amount":"+0.7831778526306152","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":"Q1819937$FF8ECD0D-C293-457F-83CE-8795231277E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the finite containment problem for Petri nets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_finite_containment_problem_for_Petri_nets"}}}}}