{"entities":{"Q1107318":{"pageid":1118067,"ns":120,"title":"Item:Q1107318","lastrevid":69835752,"modified":"2026-04-13T10:40:23Z","type":"item","id":"Q1107318","labels":{"en":{"language":"en","value":"Remarks on languages acceptable in log log n space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064486"}},"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":"Q1107318$AA8214F1-D16A-4959-ACFE-9EC6D0B193C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5d6f5c5c8fd78a88e45bdf471857980251cf42b","datavalue":{"value":{"text":"Remarks on languages acceptable in log log n space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107318$FF814670-D128-43D6-BB35-79D7FBCC99C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c59c9d552fd14d3c43b078ad3c31650f63d55a8","datavalue":{"value":"0652.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$BD019031-16F2-43C7-9D4B-C0800FF996DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a596f9af4317bc74ed9abff306fd52b7569f1b1","datavalue":{"value":"10.1016/0020-0190(88)90026-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$0DE51FC8-2842-4FB5-AAE6-C6F7247D5837","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab04ccff5257bfd7d9df0e67238421f4fa3b71ef","datavalue":{"value":{"entity-type":"item","numeric-id":293472,"id":"Q293472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$183BF8E5-0089-460A-9ACD-22DD48F5ED19","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":"Q1107318$D852FFAE-4C6F-496E-97FB-A03937228FA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1107318$0A9E185B-907C-443D-83DC-EC3A34B7D2DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b21f0bb711de083aab3ea72d13584052f0af916","datavalue":{"value":"A language is acceptable in the strong sense by a two-way nondeterministic Turing machine when all computation paths on every input stop and satisfy the space bound. The following main theorem is established. There exists a language which is acceptable in the strong sense by a two-way nondeterministic Turing machine in log log n space such that: if the language is not decidable by any two-way deterministic Turing machine in log log n space, then \\(L\\neq NL\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107318$B9E9B23E-BA9A-419D-A33A-6A76698A38DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$24729ACD-7E62-483E-8AA0-AB43AB3557AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$70DD8BB8-D151-4C0A-9D1F-45CFB3FEA692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$60437E36-A950-4FCC-897E-19100992E87F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80bd5bca5d04611172edcf254573cb790d13cf93","datavalue":{"value":"4064486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$F2D0FCE1-0EDF-48CB-B3AE-8E9BF1D57185","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107318$F7DBED86-3E46-44F3-98D6-603DE4BD3AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ba6d968a7617d9b56b80603a9b30974da2b918","datavalue":{"value":"determinism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107318$09A5DBF8-E575-490C-BFF3-FA78AC295C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"902868972549dcf2bbab4d564f2a80886b48e88f","datavalue":{"value":"nondeterministic Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107318$652665E9-7BD2-44EF-9B75-F984B7FA0BA9","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":"Q1107318$B0B80328-C429-49F8-A2BC-D6C3D9FEC108","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2bdca4538b8aab964e53e139d5cd7bb01b67a466","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90026-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107318$FACD495F-A1B7-4A36-846D-6B9AD907ECEE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7dbe994e55bc66e7595bcbb1ac33a2f37a5e9f73","datavalue":{"value":"W2055191062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107318$AC3C579C-80F3-434F-8060-95B3FF416E1E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f9c22b32b28aec38b3413d783efe6c67d7e1b6c","datavalue":{"value":{"entity-type":"item","numeric-id":3692869,"id":"Q3692869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$5706DA57-B914-49E9-9088-C299A49A4F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d914273cf97c13bdfe89b39c3dfaad36c53610b","datavalue":{"value":{"entity-type":"item","numeric-id":3912023,"id":"Q3912023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$DBDC84F5-D71F-4F56-AC67-29C12D326662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5bee5357a250d05fef165e66d176475085e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":5180413,"id":"Q5180413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$04FCBD09-6BB9-4264-8AE9-E910827E8EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64bcabd30b51121548670b47077c47a576029697","datavalue":{"value":{"entity-type":"item","numeric-id":4039733,"id":"Q4039733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$BC750660-4479-41BD-939F-90F58E1A8224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47d753588d3e15901e017390d393815c34f9ede","datavalue":{"value":{"entity-type":"item","numeric-id":5636862,"id":"Q5636862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107318$07B89DDA-688C-49DB-B8B3-82630DA78D23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3595e4771037368cbdf88f0ea9efda5046659000","datavalue":{"value":{"entity-type":"item","numeric-id":1824397,"id":"Q1824397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51bee93a5296ba9affbb000947a8ac9895831e22","datavalue":{"value":{"amount":"+0.801225483417511","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":"Q1107318$1E47CA33-312D-4745-8EBF-D6706EDBCB69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf04093b71b323aeddef1c7080610429a665f70","datavalue":{"value":{"entity-type":"item","numeric-id":5096159,"id":"Q5096159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74c75401d48f9d0d163a0b4dff7567aae76a7f16","datavalue":{"value":{"amount":"+0.7902999520301819","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":"Q1107318$81B346D6-A0AB-4736-8522-77A3B605DBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df7e7a2f818446e98ed17e47305dbaa8ac1be22e","datavalue":{"value":{"entity-type":"item","numeric-id":3747727,"id":"Q3747727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170b1efdaec43e31117d4bceacd8e6364c9cf11c","datavalue":{"value":{"amount":"+0.7825378179550171","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":"Q1107318$084E6CC0-6663-4AC2-B124-D82BF3B0C334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03000a840c76ac929aeb850c3e71b3ab2929eae1","datavalue":{"value":{"entity-type":"item","numeric-id":2254505,"id":"Q2254505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49ded02d9a60a44fdebc0d95b7f971aac8b805fb","datavalue":{"value":{"amount":"+0.780091404914856","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":"Q1107318$D7739BAB-49BB-4B22-BEB9-001ECBA73D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"356850267bfe5786c05db0e8e549d89cf01534a5","datavalue":{"value":{"entity-type":"item","numeric-id":3971288,"id":"Q3971288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5ced13fee73733ed8ad773471ec29cc48e87d67","datavalue":{"value":{"amount":"+0.7772972583770752","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":"Q1107318$177E7DDD-1B11-4094-BA15-917C6EBEC60F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Remarks on languages acceptable in log log n space","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Remarks_on_languages_acceptable_in_log_log_n_space"}}}}}