{"entities":{"Q3766869":{"pageid":5796775,"ns":120,"title":"Item:Q3766869","lastrevid":110644781,"modified":"2026-11-19T05:22:38Z","type":"item","id":"Q3766869","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4024808"}},"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":"Q3766869$5CF860E7-F327-4AD5-A2A6-2EA4DCAD11F5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6de64ca76e2d593e0a16ceb4ec562a00b402ff17","datavalue":{"value":"0629.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3766869$F855A02B-ADFA-45AC-A346-6D75828D78AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d1514257d658e010131bff41324899be3f49134","datavalue":{"value":{"entity-type":"item","numeric-id":688712,"id":"Q688712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3766869$68A03726-F301-40EA-94D1-F4FB17F9DBB7","rank":"normal"},{"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":"Q3766869$71CCB68C-5888-441F-B7FD-14A69EC2D681","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q3766869$DD378236-81CC-4FA3-BB36-6FB68D9F42E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3766869$B098A443-7801-4221-9524-3F4388653C0A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3a40ce1580dd0021bbc5df7b043337fca8de7999","datavalue":{"value":"4024808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3766869$FE460F61-3B37-4CBF-9548-969A7205DFA6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c3eba28e84d76c269f1f00e8cbc2da936c75820","datavalue":{"value":"conflict-free vector replacement systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3766869$07254452-C759-4B40-9358-2B54C9EA61A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dbd4c054a1821baa230adbaf67218c169d2893f","datavalue":{"value":"NP algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3766869$9E71F830-2132-4C35-8646-5DEDCB7EF60C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bffca71a435ced51db72e4cc2c3e4d6cb1b9197","datavalue":{"value":"reachability set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3766869$61AECC12-64E5-4E33-8147-4BB477348033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23f221017ac632904454e33ff1904ed996f8e2ab","datavalue":{"value":"semilinear set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3766869$9901A863-473D-45EC-89C4-A2E341E21EDE","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":"Q3766869$4872C442-4A9C-4486-A369-C929C1FD18F2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c5c806c442e1d82360668a310f3f3ce5935ec2e","datavalue":{"value":{"entity-type":"item","numeric-id":1113674,"id":"Q1113674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c2dd90e89ee14b63530eefbf632f48106fb79ff","datavalue":{"value":{"amount":"+0.9587269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$66DA7E79-99CE-4D8D-9CC8-43B499CB4DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7800c78e1e747f1d45711eeefcb62a2fca213dd","datavalue":{"value":{"entity-type":"item","numeric-id":3774963,"id":"Q3774963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21534fdf14944e345927ab9f5bc03ac6b2002c4b","datavalue":{"value":{"amount":"+0.8664679","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$E5CCA124-19E4-44EC-860E-28E507D00877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9326ebb6bee8c485d423eb4ea4ab1f43457686e","datavalue":{"value":{"entity-type":"item","numeric-id":3343444,"id":"Q3343444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c315a1b80fc3651930ade61274b54060f01e0c23","datavalue":{"value":{"amount":"+0.86210835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$234E99F6-E8BB-446B-B6B9-4D6623C387AE","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":"8b06abb3fe3233e9127d39c5750db15c49c4b808","datavalue":{"value":{"amount":"+0.86201036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$BA95BBB0-1808-4D82-AFAF-60701D9D557B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9301864a61be7dff3378ca2289d4ff703065419d","datavalue":{"value":{"entity-type":"item","numeric-id":3584966,"id":"Q3584966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"770206a37d3b08bfa08743740fc9a553c1a9d3cb","datavalue":{"value":{"amount":"+0.85601354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$CA87100A-224E-4E58-9581-1C8F492EE531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53bd52d5af1e96a97733291109b10990211cb63d","datavalue":{"value":{"entity-type":"item","numeric-id":5212023,"id":"Q5212023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"248373c5ab6dc159e3fe9f9830341ccc8455aea9","datavalue":{"value":{"amount":"+0.8553619","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$0213AF02-78F0-4EBA-8374-FD23AFC68540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af4dbaefa5fd37cee193cd7d2f02cea2d1e141d1","datavalue":{"value":{"entity-type":"item","numeric-id":2280187,"id":"Q2280187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"248373c5ab6dc159e3fe9f9830341ccc8455aea9","datavalue":{"value":{"amount":"+0.8553619","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$845F7F16-DFF2-4481-A9A8-F031541C42AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c315bce74e8399ceadc368b7528cc44b0d829c0","datavalue":{"value":{"entity-type":"item","numeric-id":3820015,"id":"Q3820015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1166d078ef9673deb10b20d8a1476537570ecbe1","datavalue":{"value":{"amount":"+0.8487929","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$28BDCF96-730C-430B-91F1-86BB2722F9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32420d6e9720742a9639e589f237608e21268742","datavalue":{"value":{"entity-type":"item","numeric-id":4635791,"id":"Q4635791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d51a3f38ff98a8bcdcbcf8405c0f435a165e2e91","datavalue":{"value":{"amount":"+0.8468397","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$124BCA76-4785-4B7C-95CE-69ABB5B66425","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10fb9c9b4f493cf44e82ea63d1bbc0bc72dc42e9","datavalue":{"value":{"entity-type":"item","numeric-id":2786139,"id":"Q2786139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeebf9e25ebc61c039cf2763dbc800c9aa77d194","datavalue":{"value":{"amount":"+0.8453575","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3766869$80C4ACEA-775F-41B2-B0DB-2CA2BCA8CF1A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aebdb70d0857af40d76af42fbbe0eaa9521ea257","datavalue":{"value":"[For the entire collection see Zbl 0616.00013.] In this paper, we give completeness results for the reachability, containment, and equivalence problems for conflict-free vector replacement systems (VRSs). We first give an NP algorithm for deciding reachability, thus giving the first primitive recursive algorithm for this problem. Since Jones, Landweber, and Lien have shown this problem to be NP-hard, it follows that the problem is NP-complete. Next, we show as our main result that the containment and equivalence problems are \\(\\Pi_ 2^{P}\\)-complete, where \\(\\Pi_ 2^{P}\\) is the set of all languages whose complements are in the second level of the polynomial-time hierarchy. In showing the upper bound, we first show that the reachability set has a semilinear set (SLS) representation that is exponential in the size of the problem description, but which has a high degree of symmetry. We are then able to utilize a strategy introduced by Huynh (concerning SLSs) to complete our upper bound proof.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3766869$1DCA0D59-04C1-4E8F-BD39-AD7F9D2602F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3766869","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3766869"}}}}}