{"entities":{"Q1825044":{"pageid":1835786,"ns":120,"title":"Item:Q1825044","lastrevid":49318861,"modified":"2026-01-06T23:10:05Z","type":"item","id":"Q1825044","labels":{"en":{"language":"en","value":"Nondeterministic multicounter machines and complementation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4119649"}},"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":"Q1825044$559FB9DE-7F21-46EF-91AB-EC8D969E59C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"37ea07d31f95d68efdf78466f2065b1a92fb82f9","datavalue":{"value":{"text":"Nondeterministic multicounter machines and complementation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1825044$68DB4B07-BDF8-4BCE-AC16-AD8C9E9600FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"99ce79c16d3c309c04afd61267f2c8089cfb99c6","datavalue":{"value":"0683.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$3D5BB9D7-A778-4EBD-8548-7D747FB7BFBF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f1f46ed5f79b952b07f1a204d812fbd5224f519e","datavalue":{"value":"10.1016/0304-3975(89)90026-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$88D9417E-5AA8-496E-B8FA-8DB7AA4A72C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3212848045c6198d4947b543bd946247b05e53fa","datavalue":{"value":{"entity-type":"item","numeric-id":620960,"id":"Q620960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$A23122D6-7880-49FB-B06F-8826E568FBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"683c75677bb04b2f3b10e7e51bfc2f72673c21f5","datavalue":{"value":{"entity-type":"item","numeric-id":809594,"id":"Q809594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$A3C655EA-6E51-40E0-B24A-739A0B29B390","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":"Q1825044$61D765EA-8192-492A-B49B-0B4C9D2D2A0C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1825044$880C83CA-D0C4-4EAE-94F3-FC50EF91BDCB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd2a08130b52d484e92c1250d86d7c5afd8d5320","datavalue":{"value":"For any polynomial f, the class of languages accepted by nondeterministic one-way multicounter automata within f(n) steps is not closed under complement. This is shown by exhibiting a witness set using a counting argument. The same is true if multicounter is replaced with k counter for arbitrary natural \\(k>0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825044$A3C5B094-D9A4-427E-8DA5-8E40FE336D66","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$6D088168-E1F7-41D7-AF2D-37B87A2B58BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$D659A6F9-BD71-4E42-A2FB-E594BCB95531","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0b60254856dac1fcf4eaf7461767cdc67d69d116","datavalue":{"value":"4119649","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$9A592C98-87D5-4837-B7A5-F228BFACB9C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4567dfcdca2a16710dfa78fc6c9ca84fdc95530e","datavalue":{"value":"counter machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825044$D96EDE4D-FC23-4B5E-B3B3-4BEF5646FF8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d019f267726c10f843380062c5c81e16c7cdcf0b","datavalue":{"value":"closure under complement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825044$48CEF243-DDAE-4DC4-BAA5-FACCBB964B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c60798cf6850c7609065221c4c25cac57dce3834","datavalue":{"value":"counting arguments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825044$27B6CF7A-D1BA-4E37-B5C7-461CE93035AD","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":"Q1825044$5B231D9C-D607-4C36-BC28-2482504F2968","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"efea711a488a20cb6fe125bf9a49700c86ae93c0","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90026-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1825044$FB47165E-7295-4AC0-85A5-838262657AE7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"55bf8052f3841466132f23df1fbe10b349a730b9","datavalue":{"value":"W1974506786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$A684C463-0722-4683-B3D9-2C8821BBACFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae220d6f84b63b4e513440dfeebdd74487d42a4","datavalue":{"value":{"entity-type":"item","numeric-id":3674059,"id":"Q3674059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$176FFC43-86E1-4CBE-9CE2-BBAF0B49D827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4009a8047b1ef3c087d1c16b6cac73da0828f71","datavalue":{"value":{"entity-type":"item","numeric-id":3704912,"id":"Q3704912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$C1ABDA70-1CEA-41DC-96AF-0E74FF30D689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa71b027a73e7e140353cb0ecbea546629b16264","datavalue":{"value":{"entity-type":"item","numeric-id":3702514,"id":"Q3702514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$0A39D3AC-0E9B-4CA9-9A79-2C9342ACD615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"131a577080a6bafcd20f0a7c17a110b8d5407c39","datavalue":{"value":{"entity-type":"item","numeric-id":1094884,"id":"Q1094884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$95B6AB8C-D422-4BBE-ADB5-B25F2FAB1210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182981e0e770b39d22d2da0fccd0d6dd8798182f","datavalue":{"value":{"entity-type":"item","numeric-id":4140393,"id":"Q4140393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$5291F4EC-8178-46AF-AAED-9352EC5FFBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"656a88094d3818a28a699dfaea22a6fc84ea05fc","datavalue":{"value":{"entity-type":"item","numeric-id":3707407,"id":"Q3707407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825044$2D468B11-D114-4888-A5DF-103E46841CA9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"37fbd362c87d2ab87a69fc381f5c936c8bc803bf","datavalue":{"value":"Q126670813","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825044$CD5C6289-4382-4489-B4F2-3EAB1BF1D7EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95233dd9f5e671f52527e031446fbba8db3f2dd2","datavalue":{"value":{"entity-type":"item","numeric-id":1094884,"id":"Q1094884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44ba2615c0a9c8527e76727ca352271dcd0d9f1a","datavalue":{"value":{"amount":"+0.8715513348579407","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":"Q1825044$7706EB23-43C1-4982-AFBD-F627C2B034C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb25fd3deb0753eda2201f0a958374a05f3db620","datavalue":{"value":{"entity-type":"item","numeric-id":3758246,"id":"Q3758246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa8d75e717f00ca55ecadf7bcf71cf6e8a6f829f","datavalue":{"value":{"amount":"+0.8060786724090576","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":"Q1825044$9EF56FCC-74D7-418F-95FD-B65698239317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6df03bc7273c5ca9019f2ba9f07a2636b9a5295e","datavalue":{"value":{"entity-type":"item","numeric-id":3219134,"id":"Q3219134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d91f5b14b288bfdac08668f3e92ba89383b72b4","datavalue":{"value":{"amount":"+0.7958788275718689","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":"Q1825044$6B510334-863C-4BAA-99AA-A6017E4E6CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f55946453d448833fe2d6dc669ce84237c311310","datavalue":{"value":{"entity-type":"item","numeric-id":1763706,"id":"Q1763706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11a8a04994cc270d053de56e3eb365463bd68580","datavalue":{"value":{"amount":"+0.7798526883125305","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":"Q1825044$D39CAD42-798B-4A7C-B835-968B6FF85269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9b649a29afd8c606bdb4c35a918813d6e2dbffc","datavalue":{"value":{"entity-type":"item","numeric-id":3746886,"id":"Q3746886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96b4d65712a527307bd538bc69e302e64c801531","datavalue":{"value":{"amount":"+0.7793038487434387","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":"Q1825044$46ECA688-D89E-48E5-A54C-5838665D6B46","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1825044","badges":[]}}}}}