{"entities":{"Q1113670":{"pageid":1124419,"ns":120,"title":"Item:Q1113670","lastrevid":49233448,"modified":"2026-01-06T19:53:27Z","type":"item","id":"Q1113670","labels":{"en":{"language":"en","value":"Simulating two pushdown stores by one tape in \\(O(n^{1.5}\\,\\sqrt{\\log \\,n})\\) time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4080910"}},"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":"Q1113670$6B9388BA-47F5-4E26-815D-32144280FC3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"99dcdfd8cca062876f4602dbf7e011c240728f08","datavalue":{"value":{"text":"Simulating two pushdown stores by one tape in \\(O(n^{1.5}\\,\\sqrt{\\log \\,n})\\) time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1113670$9A60B70F-E3E8-4B50-A92C-0A3826C1D292","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f49dba23822f12691f3d052dc6d3bd66483bf4a1","datavalue":{"value":"0661.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$0EB3A90A-771D-4C8D-8CCE-5332E322C951","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b38416fc1d8475f3f482fe1fe8a5efcf2175d992","datavalue":{"value":"10.1016/0022-0000(88)90047-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$4F1C1930-E5CD-458B-815A-5F0078557F76","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$60B28B03-E7D1-4838-9B0F-00DAD280B3DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$EA82DDB0-5576-47A4-BC69-F94C8843C2CC","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":"Q1113670$DF067CED-511C-4A91-85BE-6BD2C9F4CB99","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"42f4aa1655020d017378cff86bb17d7659ab3860","datavalue":{"value":"Two important results are proved in the paper:    Theorem 1'. A one-tape nondeterministic Turing machine can simulate a two-pushdown store Turing machine in \\(O(n^{1.5} \\sqrt{\\log n})\\) time.    Theorem 2. The languages used by \\textit{W. Maass} [Trans. Am. Math. Soc. 292, 675-693 (1985; Zbl 0608.03013)] and \\textit{R. Freivalds} [Inf. Process. 77, Proc. IFIP Congr., Toronto 1977, 839-842 (1977; Zbl 0367.94079)] can be accepted in \\(O(n^ 2 \\log \\log n/\\sqrt{\\log n})\\) time by a one-tape nondeterministic on-line machine.    Theorem 1' disproves the conjectured \\(O(n^ 2)\\) lower bound which holds for the deterministic case. The proof is based on the separator theorem for planar graphs [\\textit{R. J. Lipton} and \\textit{R. E. Tarjan}, SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)].    Theorem 2 shows that the \\(O(n^ 2)\\) lower bound cannot be obtained for one-tape nondeterministically simulating two tapes. The proof is based on the separator theorem for doubling transformation graphs (a proof of this theorem is given in the paper).    As applications the following results are obtained: three pushdown stores are better than two pushdown stores for nondeterministic machines and one tape can nondeterministically simulate one nondeterministic queue in \\(O(n^{1.5} \\sqrt{\\log n})\\) time. A list of three open questions ends the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$4F32A798-9C19-4D35-9D9D-FA7DC13A3FDE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$A394EF28-9036-44BC-B2E4-9EAF9350CEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$384DFEAA-F313-4863-83C4-0B5A8BD157C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$AC0766F6-D9C0-4B25-A051-9F68DCF74986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$FA899A52-2498-4352-AA25-B55885657B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$3B39D7E5-5EB6-4528-98C3-6F45D65A809E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b131f72599555d3fe265029392581a2432dfc61","datavalue":{"value":"4080910","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$C1121CD5-E9D1-4A77-9C7F-980C53BB914B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"346d2cc3a657c4d33b736000a1ae6fcc72e0e172","datavalue":{"value":"queues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$210438A7-AC31-4F8A-9A71-8DA2578B1410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$C27731CB-5081-4AE7-A282-D4D4F22C3E60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"902868972549dcf2bbab4d564f2a80886b48e88f","datavalue":{"value":"nondeterministic Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$6BAB71EC-0D3E-4199-99FE-AA40AA1A8DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a99137465605efd4f55fd4fc54f21780255610d","datavalue":{"value":"two-pushdown store Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$D13B8DF2-5080-4DB0-9D7A-8E562B525910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3522f369b37f0a765caf643c9c11f9ce492080f3","datavalue":{"value":"separator theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113670$73F7C9D9-37EB-4B98-95D4-6116C435CC6E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$5C92921C-66E1-441B-8692-00354CE2FD93","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":"Q1113670$FF232F96-9B4D-4FE0-B746-071931600757","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"21d32467803f8508b393f6e07debcf5513aee4d6","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90047-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1113670$1FEC8588-F9A5-4F1D-A22C-3B9392663601","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cfc47d42b39b084f0d2504291f490d1862866e1d","datavalue":{"value":"W2985036451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113670$5FDC9A24-6B28-4E86-8058-A955F6E6F1F3","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":"Q1113670$7EDCA8B2-F9CB-4658-974E-1AB8B0410DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80840438dbadfbf434a3cf20cc51a4c646a82e17","datavalue":{"value":{"entity-type":"item","numeric-id":5582342,"id":"Q5582342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$6F40AD29-02B9-4A5E-8074-76F47C3338ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45e5401aed9934a90f07cd3768501024fc900e12","datavalue":{"value":{"entity-type":"item","numeric-id":2542726,"id":"Q2542726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$8058A82C-157B-49AB-8AE8-57D8DB192218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3d2070efa35255ffc99b902e96d17375260cd5","datavalue":{"value":{"entity-type":"item","numeric-id":3347301,"id":"Q3347301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$CBB7EBE5-B39B-4CCB-8BA3-3BAC0198AC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6ad89a01696e5095512d78d1f8332ce1eed1341","datavalue":{"value":{"entity-type":"item","numeric-id":4145647,"id":"Q4145647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$C5FD2894-00D6-447D-B6A3-F7FD809E13CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9991d12c610af612098995f36bb9f37d525e6bf2","datavalue":{"value":{"entity-type":"item","numeric-id":5557460,"id":"Q5557460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$079F886C-17C1-4EA7-9D6E-A1CECDB9574B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ed8c1c9b5cf85c3067f46e271b605235d5e997","datavalue":{"value":{"entity-type":"item","numeric-id":5339741,"id":"Q5339741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$A3697319-BE74-41AF-8BE0-A47E9F95899C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a1abf0ec1abf337ad5daf1409b3e69fe79a4c97","datavalue":{"value":{"entity-type":"item","numeric-id":5526975,"id":"Q5526975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$A5DD8C9E-4BCB-42C4-AC5A-D0970D114894","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":"Q1113670$205C8A53-F8ED-4412-8983-7C8D1F89A490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5822449779b6c77eb8ddb6754e1b3c46dfb96493","datavalue":{"value":{"entity-type":"item","numeric-id":3323289,"id":"Q3323289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$54A4BDF5-0FD8-4241-908D-3DA1F207BB4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e082245e1af6bf8382296cd29e786390ed4e9c72","datavalue":{"value":{"entity-type":"item","numeric-id":3690223,"id":"Q3690223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$EF3A42CC-EF2B-4530-B1D0-962CFF3EAABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9927aa899cce1acd990d42f2c4a306db844c80da","datavalue":{"value":{"entity-type":"item","numeric-id":1109567,"id":"Q1109567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$A4D36F6C-3A09-46C4-A32A-85B3A2466859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$04650E97-E1CF-4F70-AC5C-AB82CF907CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$DB71575D-76C8-41F0-B74B-D46D9691C9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187eda5eaa8b955a41f589e6064b1ece725cf0dc","datavalue":{"value":{"entity-type":"item","numeric-id":3748273,"id":"Q3748273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$D3BC145A-328C-48CD-8646-1C8D06290299","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":"Q1113670$A812C01F-C913-4558-A487-96B9024B21BE","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":"Q1113670$61AA987F-C95F-4047-9DA0-0B5D645330CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6b703cfcf5812872bc6151609542fc4e93201b","datavalue":{"value":{"entity-type":"item","numeric-id":1068538,"id":"Q1068538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113670$6A0D619E-7F97-4DA0-9F19-9F7A5E55C1FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a5c54b3421dded308ba9c52a30ca27b34353bac","datavalue":{"value":{"entity-type":"item","numeric-id":1122982,"id":"Q1122982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32d0d8311ed106516be7743a085f6369934b15d4","datavalue":{"value":{"amount":"+0.8499265313148499","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":"Q1113670$EBD911C5-31E5-49BE-BB29-A4F537C57D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fae9cf54a7bfbd0cca2b5e05b32bce25a3d7d92","datavalue":{"value":{"entity-type":"item","numeric-id":4206403,"id":"Q4206403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"837bf93a15b1333e01a2bb93f88aece27858adc1","datavalue":{"value":{"amount":"+0.8256785869598389","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":"Q1113670$C13BC28E-E6A2-424A-A8A4-AF99BCEDB7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7a5333ef902fd8785cb6020df6457c9b2dda6ad","datavalue":{"value":{"entity-type":"item","numeric-id":3718158,"id":"Q3718158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dab5e56c4f68f7c44151418f2d91c9af371ed33","datavalue":{"value":{"amount":"+0.8166481852531433","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":"Q1113670$E8E9B9E6-AE2F-40E0-9FE3-9F1E5CDA4AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cdc025ff4c0a8913438f9fee17bff838b697cf4","datavalue":{"value":{"entity-type":"item","numeric-id":918198,"id":"Q918198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c2153cd2d3b5877004cf67e13c6538f72c1423","datavalue":{"value":{"amount":"+0.8141407370567322","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":"Q1113670$06B44869-693F-4852-8AEF-8B79F3F5B6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53ff7a96f32539227a9ae444d661551a6b76f5be","datavalue":{"value":{"entity-type":"item","numeric-id":3809270,"id":"Q3809270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ca250d6ce011734a1052975cd3979b8b11307d3","datavalue":{"value":{"amount":"+0.8028144836425781","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":"Q1113670$2711257A-3BD2-47A8-8AEB-9BE7F7912D77","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1113670","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1113670"}}}}}