{"entities":{"Q1819938":{"pageid":1830680,"ns":120,"title":"Item:Q1819938","lastrevid":69402378,"modified":"2026-04-13T06:45:51Z","type":"item","id":"Q1819938","labels":{"en":{"language":"en","value":"A multiparameter analysis of the boundedness problem for vector addition systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3995066"}},"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":"Q1819938$BE5746B4-8B66-4E99-9BBA-13FF83B03377","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a78ff98b7a942d692475cafa2e9c061bc7cb25f9","datavalue":{"value":{"text":"A multiparameter analysis of the boundedness problem for vector addition systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1819938$17582EA1-BE27-426A-83E0-7CA02A06DDE9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6573e75845c378b0716d3dfa32921c94b455f9e","datavalue":{"value":"0614.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$8A5D67F2-EEE0-4738-86C7-C972D63C42D4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79d8e66e42a9528b3ec0b09f4c5d043f5c068d62","datavalue":{"value":"10.1016/0022-0000(86)90006-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$CEE0D296-6B02-48B5-AD0D-DF7BF44037AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fbe9a2f35bfbb97131fdd4f5f88a8af0c602f0","datavalue":{"value":{"entity-type":"item","numeric-id":688713,"id":"Q688713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$7C32FFAA-7DB1-40AE-BC2C-AB3A97BA08A2","rank":"normal"},{"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":"Q1819938$B167F7C0-E196-424D-8528-2855CADFF10F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$356CADCA-5AFC-44D6-B92C-B072D2F3D1BA","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":"Q1819938$7D6E92EA-DA36-4DE0-8C70-16965F361748","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"123f3f867a2f8c9d4f381326881180d2f2480fa1","datavalue":{"value":"The authors give a careful analysis of the complexity of the boundedness problem (BP; ''is the reachability set infinite?'') for vector addition systems (VAS) and vector addition systems with states (VASS), which are known to be equivalent to Petri nets. Upper and lower bounds for the complexity are given in dependence of three parameters: k: dimension of vectors, l: maximal bit length of vector components, n: number of states. The BP for such VASS(k,l,n) can be solved in \\(O((l+\\log n)*2^{c*k*\\log k})\\) nondeterministic space for some constant c (an improvement of Rackoff's result). Lipton's lower bound is improved to \\(O((l+\\log n)*2^{c*k})\\). Furthermore, some complexity results for fixed small k and connections to nets of communicating finite state machines (CFSM) are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819938$EA151022-1AB5-481D-A4F7-DFE7EE7DD5A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$AE776123-28B6-4E3A-803A-7C15D9DD9D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$AE64B6C5-B26E-4727-BA19-DD2F6A44A634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$AD22E80C-E310-4842-A241-B5B964703542","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4d5a02d0ea3d2763cc45aa59945d2749db9e650","datavalue":{"value":"3995066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$9A0D143C-F572-4B89-84A8-49754D31CD62","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89ce97fe74f8bf0ae7fae5601455f6e504f2f09a","datavalue":{"value":"complexity of the boundedness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819938$08EA144E-B4D6-47F7-8530-BCF99C574CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bffca71a435ced51db72e4cc2c3e4d6cb1b9197","datavalue":{"value":"reachability set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819938$7055304A-D977-4040-A799-787ABCCA0086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01596681fec0062ebe65a0738936e768a85631a0","datavalue":{"value":"vector addition systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819938$B6062F2F-BABF-49D1-8AD3-015D2802C859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77f3393ee1bf5e04c83e196aa8891cae0cc3cb71","datavalue":{"value":"communicating finite state machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1819938$49F44225-2BFD-4514-A9F8-D012184E9B00","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":"Q1819938$5EDE10AC-2AA9-454C-BF93-7CF5AC00D4DE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ce271df04d3decb8793934dce296b9fa1d0f0e5","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90006-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1819938$A9D0FF69-1125-4BC8-9ACD-B7AEEC26AF7E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b99b3ec945363ab615a1283c5aea746cfedfa9ca","datavalue":{"value":"W2066238373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1819938$1AF4E340-3DD0-4CA0-BEE7-2BAB0BDC8C18","rank":"normal"}],"P223":[{"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":"Q1819938$8EBD3159-904A-4D6A-B951-673AD7185CFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$BBB83728-33AD-4C6F-8720-B739DDD40FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$84A467B8-8753-4136-A05E-991411DB766E","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":"Q1819938$50C76026-06A8-4BB4-B49C-6DFAFD0E6E74","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":"Q1819938$B5D928A8-08E8-486F-8ED4-0DA0AE56A68B","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":"Q1819938$8E74E237-4F34-4F28-9B77-AE004E85EA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$1A97D6AA-DF1A-4019-A1EA-C6BD32924644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"990393bd70b90fd085a53f98d66454d70d95783b","datavalue":{"value":{"entity-type":"item","numeric-id":1238999,"id":"Q1238999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$54B7F62A-A9CE-40B6-A1C3-8B931D608812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd23d993698a0223d91c56a5d6cb2616616568f","datavalue":{"value":{"entity-type":"item","numeric-id":3700836,"id":"Q3700836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$12C69FC3-1B5A-4649-8E44-B61452AF5132","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":"Q1819938$70AA61D1-76DD-46EF-8A3C-773B652E4452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$968B216D-07A2-4F13-9E15-EFB9A1A301AC","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":"Q1819938$57755BB3-B5EC-48DC-8444-92C615DAFC21","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":"Q1819938$D01EC695-0F4B-4ECE-944F-87179457F2FA","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":"Q1819938$6E783C22-5F88-479D-84A6-E47B3CC79707","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":"Q1819938$0C04E35B-B157-4DE6-A88B-7F91EBAB16BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f760c4d44975c8a679fe0f7dec55589ceb7bfc7","datavalue":{"value":{"entity-type":"item","numeric-id":3685206,"id":"Q3685206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$5935D082-96F5-4DA1-81AD-DEA085ABA298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1819938$1BF46764-EF20-4DB7-A45D-DDCA253F2DED","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":"Q1819938$BBE78031-0D2B-447E-9283-404BC38974B2","rank":"normal"}],"P1643":[{"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":"083c6421b2d36ae7c706c769fe6cfb40897a8e0b","datavalue":{"value":{"amount":"+0.8722745776176453","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":"Q1819938$CFE0AFE6-9E13-4789-A201-F401F21BE7B2","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":"0570394385fcabc5e29037b85af0adfcccbefd55","datavalue":{"value":{"amount":"+0.8689371347427368","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":"Q1819938$871CA0B1-6938-4AED-AD4C-B40A681AF81D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9fb447d140e46b4f739a141f844de61cbc10feb","datavalue":{"value":{"entity-type":"item","numeric-id":1097037,"id":"Q1097037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"542d4c643e07ea9a52ae992e31e3942d2b4ff105","datavalue":{"value":{"amount":"+0.8288373351097107","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":"Q1819938$6246696D-8CFF-4626-97F5-E72EE3206DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5596a72298c186cb84ca422afff9dd10b0413d9c","datavalue":{"value":{"entity-type":"item","numeric-id":4853328,"id":"Q4853328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144bb28752b46695245a7c1eca2e24e39ea8faa7","datavalue":{"value":{"amount":"+0.8056488633155823","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":"Q1819938$70EED5B3-C683-4EDB-AC0B-BC6226DDB95A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"601f15ff30906f1e05fc5f946e83231333863e77","datavalue":{"value":{"entity-type":"item","numeric-id":5145613,"id":"Q5145613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8a8565cff6b7b1da088caec4142c56b75404a34","datavalue":{"value":{"amount":"+0.8056488037109375","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":"Q1819938$0E57DC51-168B-4BD4-BFF5-612C075E256B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A multiparameter analysis of the boundedness problem for vector addition systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_multiparameter_analysis_of_the_boundedness_problem_for_vector_addition_systems"}}}}}