{"entities":{"Q1068538":{"pageid":1079290,"ns":120,"title":"Item:Q1068538","lastrevid":42852589,"modified":"2025-07-15T10:03:44Z","type":"item","id":"Q1068538","labels":{"en":{"language":"en","value":"An \\(n^{1.618}\\) lower bound on the time to simulate one queue or two pushdown stores by one tape"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3932389"}},"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":"Q1068538$988B16C5-42C5-4C08-AE98-447421E0E4EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d235101abae41f86ff8f7c056e9eb6b112fb678e","datavalue":{"value":{"text":"An \\(n^{1.618}\\) lower bound on the time to simulate one queue or two pushdown stores by one tape","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068538$B2F916B5-AC7F-4A8C-93AF-D73F47F02322","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"056138b7141909a314cba232c596be39bb561cef","datavalue":{"value":"0582.68019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$3BB60AB7-99C4-4E8D-8ADA-CDFC66E65BCC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03be7f6c71f755f67110b92971b312d32fc6a8a9","datavalue":{"value":"10.1016/0020-0190(85)90020-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$233B9247-ACBB-481E-AB65-B5A425DED1D2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60b2337bc50810374b4ca0c66cb11407509a5fbe","datavalue":{"value":{"entity-type":"item","numeric-id":354146,"id":"Q354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$55984C7F-E262-4351-8128-F230F870C8C7","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":"Q1068538$7E5E3FE4-3A82-4359-88FD-E7EDE6E06306","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":"Q1068538$E8A6BF92-2A19-4312-9921-BC7CC9B3F83D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$B4AC8B3A-7991-4B4F-B94C-7E1E1E1F338E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$97600C08-3747-40F2-8E4E-95F3C7B3BBF5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e578f5713eee8249355f0d575c86b3964546919","datavalue":{"value":"3932389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$E2BBBD78-C424-443D-8029-5E766A15223C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"949f0dd516e63c951a1a7bcd61a6b3198f3517cc","datavalue":{"value":"multitape Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068538$514EF0E6-0733-4D8E-8364-0375C408F46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068538$E7AD145A-B4CF-4BF8-93B7-110AE9B3F221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e183c8a08941707ab5d7fb8734989e592041855d","datavalue":{"value":"on-line simulation by single- head tape units","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068538$78E4F388-AB82-4216-8CE3-5CA326285725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068538$8F472456-E871-49C7-BD67-71376C203079","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":"Q1068538$5BEA8072-C292-4F76-B9C3-33FC33C8599A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c072eeef44a71b42f4f06c52acc5687df5fd0c20","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90020-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068538$22424A78-6ECD-45F9-A4B8-45A5A92E59A8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c437c57d51964108bb9df93b5bc631a53e01577d","datavalue":{"value":"W2023886101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068538$30EEFBF6-42E2-4485-A482-662347D729BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"248ec5667ec5a52c84f7c9aad98d22c2ca290e71","datavalue":{"value":{"entity-type":"item","numeric-id":4077448,"id":"Q4077448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$658B9820-5171-49D0-AC51-B19BC87B1A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"573f9451c18cb73fe59719b8f8cf8f07593917b3","datavalue":{"value":{"entity-type":"item","numeric-id":4137091,"id":"Q4137091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$1053F7AC-F0C7-4AFC-BF34-268976EC390A","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":"Q1068538$26ECF9E7-ECBC-4D51-8B78-4665AC7D5F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5f4a456f9910b4c4f2a1d73e4561be8a5dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3214803,"id":"Q3214803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$3E566962-FAB2-4608-BABA-50BBCFC34A54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609827d615096bb66d710b3f486ba33c91600d45","datavalue":{"value":{"entity-type":"item","numeric-id":3902483,"id":"Q3902483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$20020777-FFF2-4244-934D-506DE160CF56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e61503bf3e00baa669bf5e7642a44d7f25174d9","datavalue":{"value":{"entity-type":"item","numeric-id":792093,"id":"Q792093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$2E9614B3-A24D-4389-B8B4-B712DC986DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"938bca41e7809cafc24981e9a1a62381c68e7f76","datavalue":{"value":{"entity-type":"item","numeric-id":3321474,"id":"Q3321474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$3AB48AE3-6CC1-44AD-A60E-9C4448C3C4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f784fed1af1400bbd1a75108ed44085f78e30f5","datavalue":{"value":{"entity-type":"item","numeric-id":1156484,"id":"Q1156484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$02CAF677-7971-4ADB-A400-FEF4627A3F5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6f110f1fdd1b1965a6a71deaa20a3ec523c9cbf","datavalue":{"value":{"entity-type":"item","numeric-id":2526723,"id":"Q2526723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$535FA5A9-C3E7-4191-BD34-5E98086A0E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bf29982a8064df5e14442e03a8c9888bef4f260","datavalue":{"value":{"entity-type":"item","numeric-id":2544779,"id":"Q2544779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$3821BEE2-2578-408F-8212-CB82760805F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8692fa559fea4a62f9d4176a584cc0bc7752375e","datavalue":{"value":{"entity-type":"item","numeric-id":3886865,"id":"Q3886865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$D509C873-1210-4C33-9018-2CA8DC73F89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daac8fae6ddf50c84a2062c935ffd7f8954ea77b","datavalue":{"value":{"entity-type":"item","numeric-id":1348528,"id":"Q1348528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$1B076009-CB33-42EB-8594-E33EBD8235D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c00d9d20b3916ee6ccf7d763d594b224740cfc81","datavalue":{"value":{"entity-type":"item","numeric-id":1064067,"id":"Q1064067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$36174F23-98F2-43BC-8FF4-2BDCFD673FD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c3926725253ef4ab031c42140743ad86ac5bbf1","datavalue":{"value":{"entity-type":"item","numeric-id":3933743,"id":"Q3933743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068538$4E10E5C3-C900-435B-AC3D-4DFE0A38D64B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1068538","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1068538"}}}}}