{"entities":{"Q1184994":{"pageid":1195743,"ns":120,"title":"Item:Q1184994","lastrevid":66791559,"modified":"2026-04-12T12:53:07Z","type":"item","id":"Q1184994","labels":{"en":{"language":"en","value":"Some properties of space-bounded synchronized alternating Turing machines with universal states only"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 35371"}},"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":"Q1184994$343199BF-6F17-49D7-846F-DDDE22B6F022","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"67c2f6aafef778443b5a92496409798569873738","datavalue":{"value":{"text":"Some properties of space-bounded synchronized alternating Turing machines with universal states only","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1184994$9D6E90CF-0699-4D6F-9AE8-E72D3BABD864","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d58f79311cb1b00c6b2ace895849b4071b82e90e","datavalue":{"value":"0754.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184994$44058649-9C80-4A56-BCAE-9217A012E77D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67fda3d4a323a8bd6afd59b5bba11efaa0894e56","datavalue":{"value":"10.1016/0304-3975(92)90346-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184994$09E253F0-8F70-4BAB-9FB0-0590C6AE44C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7111f8cdfcaa17d78bd49cd299bfdaa6f0991de7","datavalue":{"value":{"entity-type":"item","numeric-id":811117,"id":"Q811117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$DC2AEEBB-42C4-4007-AF14-9AA9C9C549CF","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":"Q1184994$5FEFB48E-094A-4993-AEE0-F321D68FEB79","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184994$1AD6E880-E3E2-43E3-B8BF-D694FDB1E3FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d90f5e4737492a06d6d8def3a96e1f1c2317a71f","datavalue":{"value":"Synchronized alternating Turing machines (SA) allow communication among the parallel processes during the computation. When some branch of a computation enters a synchronizing state with a synchronizing symbol, it stops and waits for the other branches to reach a synchronizing state with the same synchronizing symbol or stop. The paper investigates synchronized alternating Turing machines having only universal states (SU). It is shown that such machines can be simulated by universal alternating TMs, the price for synchronization is paid by an increase of the space complexity. If \\(S(n)\\) is a space-constructible function such that \\(S(n)\\geq\\log n\\), then \\(SU-SPACE(S(n))=N-Space(S(n))\\). It is also shown that if \\(\\lim S(n)/n=0\\), then 1-way \\(SA\\)-machines with space bounded by \\(S(n)\\) are strictly more powerful then 1-way SU-machines working in the same space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184994$E0C68C0F-3C16-41C4-953C-EBDD1E3E0A8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184994$D5490A7C-6B82-4C62-8234-8FFB0BD0D8CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184994$DD07E643-FE15-4E78-9EFC-AA2636DAA3B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7125307e2eeb01fd4fa53812d5f3420f7882a28d","datavalue":{"value":"35371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184994$151DAA39-5D34-4842-9328-E209121E58F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d7c785826a7b700aa1fe69c478f8405b925566","datavalue":{"value":"alternating Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184994$CBD1EFE7-47C9-4D10-9A32-86D629C22D2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fa36130e82077da1500a611dfdd0f247e985b15","datavalue":{"value":"synchronization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184994$3B7649BE-E486-4934-A822-A28C165541B7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$D9AFF860-D0BE-45A1-83F8-CC231E5A9C93","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":"Q1184994$237505FD-A59D-43B9-A947-BA036A467866","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":"Q1184994$66B0AE8B-A78E-47AD-92E9-9167D3F2E356","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":"Q1184994$F3DCAE0B-192F-45EC-867C-BE9C0856BE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fae4499e5b4eb7878c24773f588cee9d3fd69ad","datavalue":{"value":{"entity-type":"item","numeric-id":1117697,"id":"Q1117697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$230A757A-714A-45CE-9ACB-65F59D39192A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"390a4c55d81f60fc04de11c79b4bb75544936c5f","datavalue":{"value":{"entity-type":"item","numeric-id":811118,"id":"Q811118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$7713E561-1A02-4D20-9CFC-6655E939D278","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":"Q1184994$64388224-11BF-49BF-8FD0-338D67FF222E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bbb1354bf58b6999e043393c5f0b79a0ba709ad","datavalue":{"value":{"entity-type":"item","numeric-id":1057650,"id":"Q1057650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$BA253624-B05D-433B-9EBD-2975F82B05B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c65c9058fead942bf47f23417bfbe75bebe25468","datavalue":{"value":{"entity-type":"item","numeric-id":1083207,"id":"Q1083207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$86B2139A-45A2-4A39-A79B-9BB3354071D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd458b5ca27c84f14f31b35d48e036e43ad2d739","datavalue":{"value":{"entity-type":"item","numeric-id":1364133,"id":"Q1364133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$15573D86-EB82-4766-8727-CD15C1C5BF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184994$46AE3E77-253A-4501-B7C7-FB92E68DA181","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"701f0cb69ef1c230672caa5278e024d2edaa6de6","datavalue":{"value":{"entity-type":"item","numeric-id":1193901,"id":"Q1193901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f34b3481c9a86f05e858236b7c48d208945a4a38","datavalue":{"value":{"amount":"+0.8810548186302185","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":"Q1184994$6DBAE2CD-15CC-4730-94C0-F5A43EE30A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5dec98ba9bd8d399ce16241f49b822bac04e6ef","datavalue":{"value":{"entity-type":"item","numeric-id":1334670,"id":"Q1334670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffe910285c34499a1e49ca1b4d9af3f525dc78b1","datavalue":{"value":{"amount":"+0.8784828186035156","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":"Q1184994$3FAD79E2-CEB1-4DE6-8FB7-28ABCF50E820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abc182b45e450a6898f99588cf47d89467f0d6e4","datavalue":{"value":{"entity-type":"item","numeric-id":4020282,"id":"Q4020282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f438def33207bb607519afece8d5ca6c80fcdcd1","datavalue":{"value":{"amount":"+0.859351634979248","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":"Q1184994$6277893A-5D2F-4C65-9E99-397373FA187E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53569800bebd5d64ee7f0c461864b5bbdf8f31d1","datavalue":{"value":{"entity-type":"item","numeric-id":1338889,"id":"Q1338889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"511b0c2a0d1074570d3171cd52cf7956e0168a25","datavalue":{"value":{"amount":"+0.858627200126648","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":"Q1184994$4C4E9344-6757-4D64-949B-1AECF79C8616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09af81fbbdf4f4a1b4e3b55f2ed8c967a692010d","datavalue":{"value":{"entity-type":"item","numeric-id":811118,"id":"Q811118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ab761249cf96e69c37ed94e59539a57b7a0a41a","datavalue":{"value":{"amount":"+0.8313923478126526","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":"Q1184994$282D33EC-3A3E-4DCC-9F09-C606FEF67914","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some properties of space-bounded synchronized alternating Turing machines with universal states only","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_properties_of_space-bounded_synchronized_alternating_Turing_machines_with_universal_states_only"}}}}}