{"entities":{"Q1067412":{"pageid":1078164,"ns":120,"title":"Item:Q1067412","lastrevid":66200481,"modified":"2026-04-12T08:13:18Z","type":"item","id":"Q1067412","labels":{"en":{"language":"en","value":"Alternating multicounter machines with constant number of reversals"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3928352"}},"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":"Q1067412$6B458EC6-08A9-4A98-930E-F4E24C05B095","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"11b926f093dcaac7a98838504a9c02902107f3de","datavalue":{"value":{"text":"Alternating multicounter machines with constant number of reversals","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1067412$2F347E4E-4AF0-4767-85C0-ED2AD4D9C5EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c280f763a5f38e0055cee456d40466f79cb8bbc8","datavalue":{"value":"0579.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$4C7F018F-28F4-4E4B-9CFC-CE93EAEA78A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1586751d2d946883986561f2e39469f046f95229","datavalue":{"value":"10.1016/0020-0190(85)90100-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$9313F3A0-ADAD-48EF-B4D3-2F7766EC07B9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7330faa8aa9bfbfa602624605066aa6301d76b4","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$5229C443-AE95-490D-8C9F-575A75D2F209","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$863CC3B2-EE1A-44FA-819E-EC3A7ADE97C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1067412$45436C02-EA3F-4361-924A-1CD99085EDEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db73a258423db955f1ec930a5c49159049afd9be","datavalue":{"value":"The alternating multicounter machines with constant number of reversals are investigated in relation to Turing machines. It is shown that two-way and one-way versions of these machines working in polynomial time define precisely the class P of languages recognized by Turing machines in deterministic polynomial time. Further, it is proved that one-way alternating 4-counter machines with one reversal allowed for each counter are as powerful as Turing machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067412$AC039250-8483-4CED-8862-A293F560E105","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$6B04A766-D6BF-42EE-9071-0A301465B364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$5E6A0C65-5F59-4747-B81D-173B6AA3D6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$F31396F3-98F8-4D96-A17A-6E5C5C76DB15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"257cc819518336b8f51fa7c1dbc2832d5f736571","datavalue":{"value":"3928352","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$DE81DFF1-B2F3-4D8F-8E1F-5D5C4A75DC25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067412$05EA66A6-4F58-4C03-BE42-9D66A2F0CD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dfb8855877f0ff77a18a0b07eddf358c3fddd4b","datavalue":{"value":"multihead automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067412$0D5EC378-4FAC-4F56-885E-045861D8C694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067412$7F49366F-16FD-4496-9D6F-5B924F48B122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067412$8028AF81-3241-42AB-BA19-3B06ADEB7454","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":"Q1067412$E2539CFE-D0F0-4A67-8C58-24C8FE21F076","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"87e45c84600203a43b0a556ead2b502307744cd4","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90100-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1067412$589C2EDC-82EE-4AF4-A827-8539A94E12DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19d0d5559918571a802784556718155668e8ae6b","datavalue":{"value":"W2067825920","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067412$D233C7D8-4D09-4E04-BDEB-225795D07D8F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$50BA53B4-A084-4120-B1FA-75FE48591890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ac23ff0d4cd9001f838ae713deecaccdfe50ad","datavalue":{"value":{"entity-type":"item","numeric-id":4089754,"id":"Q4089754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$E28FA9B9-C213-4F26-8A25-228F4A277944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$7760B469-4FD3-4BD8-9F35-BE732B006994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e9d9c496e0f763ac6d0129aa8798a5b071b043d","datavalue":{"value":{"entity-type":"item","numeric-id":1228202,"id":"Q1228202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$D01F4618-A4B5-4017-A255-B689BC11CCB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c592fb07f8b15749494843390ad585b655a9b65e","datavalue":{"value":{"entity-type":"item","numeric-id":3687716,"id":"Q3687716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$0E468726-5912-41F2-9A1C-F9C1C48ADF8E","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":"Q1067412$1E27EEB5-671D-415D-85DC-B46D6993E074","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":"Q1067412$80BB7707-E2F9-46AE-8B9E-A9D276CF8132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f01762fa8f7ded31a8f52ad73e1fb766d8ae424e","datavalue":{"value":{"entity-type":"item","numeric-id":1116353,"id":"Q1116353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067412$29A538FE-2921-4556-959E-AC798A2159A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0da37db6bebb29a7d06637509e230a9cbd5ec50","datavalue":{"value":{"entity-type":"item","numeric-id":3210175,"id":"Q3210175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dd10280f484cda5c011c128fc7a5a3619d84e10","datavalue":{"value":{"amount":"+0.8649012446403503","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":"Q1067412$969293A3-63D0-4A65-9A4C-0689A6B9D111","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":"6d56888e4ba26e9910dc17fbc8602de50bd7fa54","datavalue":{"value":{"amount":"+0.8483184576034546","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":"Q1067412$216EB678-A42F-4CC7-986B-87E878E8650C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c23aa60d11637ed897c383513347f57b90c0e620","datavalue":{"value":{"entity-type":"item","numeric-id":809610,"id":"Q809610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1f8d174b0c1697dba72d2a2f7ada27daceda943","datavalue":{"value":{"amount":"+0.8428232073783875","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":"Q1067412$6247A144-DB30-4209-9AFC-F1E35B93A911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9f5ddcbd68d8762cbc31059a6a7b6249136ba27","datavalue":{"value":{"entity-type":"item","numeric-id":3034821,"id":"Q3034821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3df39fdb53cb49ff98cb121888bb5709cdce5578","datavalue":{"value":{"amount":"+0.839713454246521","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":"Q1067412$AA221B05-902D-42C0-8634-0CC426F8FF04","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":"98af0f98440310c025bd4515f10c1e1c080e69ce","datavalue":{"value":{"amount":"+0.8346412777900696","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":"Q1067412$BC09F987-81B8-4304-B0E2-A937C1BF6AAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating multicounter machines with constant number of reversals","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_multicounter_machines_with_constant_number_of_reversals"}}}}}