{"entities":{"Q1083207":{"pageid":1093959,"ns":120,"title":"Item:Q1083207","lastrevid":48991789,"modified":"2026-01-06T10:28:33Z","type":"item","id":"Q1083207","labels":{"en":{"language":"en","value":"Alternating on-line Turing machines with only universal states and small space bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976342"}},"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":"Q1083207$68E14DC7-A6F8-4AD3-BBDE-C4A55A291435","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f7d64e1570c7bae3f7ca0a066e4c2b44b7d3d1dd","datavalue":{"value":{"text":"Alternating on-line Turing machines with only universal states and small space bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083207$3068F1F2-975F-4658-9A1E-A6AD6061D8BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c11d8300443517ecb2ba23ea4954eccf64305710","datavalue":{"value":"0604.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$C5422FE1-B8FC-4FB6-A446-CCFF2078DB83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"98467b9c667a5e1a6fd0897cf542c288c8b036f4","datavalue":{"value":"10.1016/0304-3975(85)90080-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$6B2C6E2C-BBC9-41C2-876B-B4BCA2EC5E3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31bccc448a658f3cebcea86acdb202419da8ddc4","datavalue":{"value":{"entity-type":"item","numeric-id":235704,"id":"Q235704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$6F3E7EB1-A927-4030-AAAE-0BBA7194F864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7ca1ef17249af5269bfc02ced493a4476940cd","datavalue":{"value":{"entity-type":"item","numeric-id":593782,"id":"Q593782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$FA83A396-9327-40EA-AC15-4995EF9917C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"232fb444de3957a3d60196a63591bffd75c95192","datavalue":{"value":{"entity-type":"item","numeric-id":1077164,"id":"Q1077164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$E46EB2B5-7274-44D4-842A-EC24C9061E01","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":"Q1083207$BCF72284-191B-4A78-9738-05D2D16E0D0B","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":"Q1083207$E76A3E45-7FC6-463A-9CF7-F7B7D823C76C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b5c9c3da62cbb36d30793a6a3387e77a89e10c83","datavalue":{"value":"Let \\({\\mathcal L}[AONTM(L(n))]\\) be the class of sets accepted by L(n) space bounded alternating on-line Turing machines, and \\({\\mathcal L}[UONTM(L(n))]\\) be the class of sets accepted by L(n) space bounded alternating on-line Turing machines with only universal states. This note first shows that, for any L(n) such that L(n)\\(\\geq \\log \\log n\\) and \\(\\lim_{n\\to \\infty}[L(n)/\\log n]=0\\), (i) \\({\\mathcal L}[UONTM(L(n))]\\subseteq {\\mathcal L}[AONTM(L(n))]\\), (ii) \\({\\mathcal L}[UONTM(L(n))]\\) is not closed under complementation, and (iii) \\({\\mathcal L}[UONTM(L(n))]\\) is properly contained in the class of sets accepted by L(n) space bounded alternating Turing machines with only universal states. We then show that there exists an infinite hierarchy among \\({\\mathcal L}[UONTM(L(n))]'s\\) with log log \\(n\\leq L(n)\\leq \\log n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083207$1FA78962-1D30-425E-B343-099B193F4FB8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$62702BDD-81D3-40CC-81EE-0E7093C212E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$19BD0065-533D-4F7A-8E3F-F0E1F3B6FE83","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37b26947e6640ff253b721b140759ef31969763f","datavalue":{"value":"3976342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$E8A5B693-BC02-44D2-9699-4BEC886B3BAA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083207$DBB6953D-2712-4273-90F5-F05B381A5A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61aad99fe0220675fe4421c0a74f84b421d2a310","datavalue":{"value":"space bounded alternating Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083207$0BC36780-C3E1-43ED-9507-A5E60D49D224","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":"Q1083207$470855B4-19BF-415B-9B62-13FA9149BC39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"952e0869e88c9d996c53c44189de7b3eebafd639","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90080-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1083207$42EEE970-4CC9-4B1E-A6B1-B047B87DDD73","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b214109a884bc7a3b33ec0fa5b83638121585a9b","datavalue":{"value":"W2021044407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083207$361309E5-C07E-429D-844D-77DC5ED9D44F","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":"Q1083207$CB9677E9-8AFD-4F4F-A5FF-7BB9E78B91A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$B0AE870C-B935-4705-AD58-B313D2310025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b29697d8f3dda53db49300c16b49a4c72896f8e","datavalue":{"value":{"entity-type":"item","numeric-id":3221411,"id":"Q3221411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$AFC9FDC9-3785-4020-AE3D-994C7B737351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60b8301705a3ce1d74a4ff40fbb8c15fe771fc9","datavalue":{"value":{"entity-type":"item","numeric-id":789181,"id":"Q789181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$D85E8E60-BE29-4E80-9DF0-53BAE8E6FCA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a589b2b8385ccd4be46b5ea02a14f7621bb80bc","datavalue":{"value":{"entity-type":"item","numeric-id":1141480,"id":"Q1141480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$ECAAEFB0-F212-4D53-97D0-9B1CC36EB2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$7F214883-7BB5-46C4-98DB-1A5541A690EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f200ddc20c2d33390fb94670a066f08d95c0e9","datavalue":{"value":{"entity-type":"item","numeric-id":1215271,"id":"Q1215271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$B459FBA5-2B1E-4D64-B143-F8C901C5D4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977c0a28e22a20f1da6609124ac2c8bd23eb43d0","datavalue":{"value":{"entity-type":"item","numeric-id":791316,"id":"Q791316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$F1A59C6E-114E-478B-8103-6E62A6A99120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"173002dfec884ea3ca9ffd82acac676a83274a5a","datavalue":{"value":{"entity-type":"item","numeric-id":1151259,"id":"Q1151259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083207$E0229E33-D27A-4308-946A-5B9681FAFDD4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20ebe08b5534e68ea269dceace55b8843051cde2","datavalue":{"value":{"entity-type":"item","numeric-id":1097697,"id":"Q1097697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8578f24ec51793bf496116747f35c6ae9809555b","datavalue":{"value":{"amount":"+0.8707958459854126","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":"Q1083207$7214B9D0-7AFA-4D64-9575-E177838F205F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3ebb0a258916f4e95f4b7b53e12ef7fd6e26807","datavalue":{"value":{"entity-type":"item","numeric-id":1312177,"id":"Q1312177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d786174247687841ba42c8883d7dc15f390f4da","datavalue":{"value":{"amount":"+0.8416160345077515","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":"Q1083207$24C002BC-B23A-414A-B876-42D339C3651E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25d33dc6b10d13b746c028f34eb5d3289ee06e47","datavalue":{"value":{"entity-type":"item","numeric-id":1057650,"id":"Q1057650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8f6e3d44edc765fbc245f96f8b11f8b1cec4da2","datavalue":{"value":{"amount":"+0.8400465846061707","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":"Q1083207$D6DE5413-1FD0-499D-A537-95AAC5B65632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a83215681a489cfd30e3a8b6e04c8f12de809a14","datavalue":{"value":{"entity-type":"item","numeric-id":4895832,"id":"Q4895832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed35bbbd0c5be706024f1c055834cfd4e029fd5f","datavalue":{"value":{"amount":"+0.8360403180122375","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":"Q1083207$F86CFDA5-424E-4A1D-9304-CCBE7B35DF1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e88174857e11c73fba0dbcc04bdfa4680f61b3fe","datavalue":{"value":{"entity-type":"item","numeric-id":1825656,"id":"Q1825656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"012eef206ebc0ec0ff01abbb587b5d2aee5ee203","datavalue":{"value":{"amount":"+0.8351307511329651","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":"Q1083207$A0734117-3077-4C8C-BA49-C844F745BA64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083207","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083207"}}}}}