{"entities":{"Q800088":{"pageid":801936,"ns":120,"title":"Item:Q800088","lastrevid":64503129,"modified":"2026-04-11T20:19:33Z","type":"item","id":"Q800088","labels":{"en":{"language":"en","value":"Deterministic two-way one-head pushdown automata are very powerful"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3876595"}},"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":"Q800088$3948A535-B514-4B97-9C3A-DFC809F0C3F2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cbb3189abc1c117712df13726e0716ded6b74fa9","datavalue":{"value":{"text":"Deterministic two-way one-head pushdown automata are very powerful","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800088$8B933F9B-5F41-470F-84FA-C3674911E502","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d948e8fd6b5577e0f38c52b361d8f67688cc461d","datavalue":{"value":"0549.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$39AC7E3D-EDF0-4569-B417-DD5EF2D996DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4190f941c3d5ed1a120ea7380c45865b28f705a5","datavalue":{"value":"10.1016/0020-0190(84)90001-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$7F4A89EC-6F22-41A1-9B20-9F426212295F","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":"Q800088$69FDE221-97E2-4144-8E14-EA01FEA71ED0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q800088$3574D057-1293-420D-8032-20C249EF83E4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a0ea246786b31d92293039d1f4786417547f487","datavalue":{"value":"http://nbn-resolving.de/urn:nbn:de:hbz:466:2-4388","type":"string"},"datatype":"url"},"type":"statement","id":"Q800088$E2CD87F1-F3C3-4C1C-A22A-4455B0F076B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"50a4a3f6a52836ae9e6410f671c891c17a4c8357","datavalue":{"value":"Recently \\textit{P. Duris} and \\textit{Z. Galil} [Theor. Comput. Sci. 21, 39-53 (1982; Zbl 0486.68084)] showed that a deterministic two-way pushdown automaton is more powerful than a deterministic two-way counter automaton by constructing a witness language. The straightforward generalization of the counter is the pushdown tape. Restricting the input alphabet to only one symbol makes the device even simpler. Can we find a natural language over a one-letter alphabet not acceptable by a two-way pushdown automaton with one head? Apparently there has been done work in this area over some time and there was a rumour that the language \\(\\{a^{n^ 2}|\\quad n\\in {\\mathbb{N}}\\}\\) is such a witness language. In this paper it is shown that deterministic two-way one-head automata are very powerful even when restricted to a one-letter alphabet. The author shows that if the ''binary version'' of a language belongs to \\({\\mathbb{P}}\\), the class of languages acceptable by deterministic Turing machines in polynomial time, then its ''unary version'' belongs to 2DPDA(1). Here 2DPDA(k), \\(k\\in {\\mathbb{N}}\\), denotes the class of languages acceptable by deterministic two-way k-head pushdown automata. For words \\(w\\in\\{1,2\\}^*, w=a_ 1a_ 2...a_ n,\\) the bijective encoding \\(f(w)=\\sum^{n}_{i=1}a_ i2^ i\\) is used and for a language \\(L\\subset\\{1,1\\}^*, un(L)=\\{f(w)| w\\in L\\}.\\) Then \\(L\\subset\\{1,2\\}^*\\) and \\(L\\in {\\mathbb{P}}\\) imply \\(un(L)\\in 2DPDA(1).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q800088$B706420C-94BC-422B-9847-8EE74A34633F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$AB5E7436-7D92-4795-8845-DF06563B7D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$9B117980-89E6-4401-BF9D-FC74C60BCA28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$A35F8397-3166-4ACE-AA6E-B61726644EC4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d72377ec41f006c893663f1235aa327e69c7379f","datavalue":{"value":"3876595","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$0910CE1A-90C1-47AD-894E-284F3FD51611","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q800088$27B87D11-44E4-484A-B0F5-E9E9104CB069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b8e6a69d5187e24416116126c9514dd77c9c5f1","datavalue":{"value":"random access machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q800088$2EFAF57C-B1F3-4407-9070-1DE115AB9348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb2f0de02d262d04e2662ebc233c52925645bb33","datavalue":{"value":"one-letter alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q800088$FB04B508-3E93-4FA9-8C3E-717FDDBA364B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72f4ab16119e030fd33fd6035c0dc314d8442449","datavalue":{"value":"two-way pushdown automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q800088$0563192A-34D0-4370-A590-7CDC2E8FACC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9f391e6322208fe1ff9282b50ef9e948c0574c","datavalue":{"value":{"entity-type":"item","numeric-id":284584,"id":"Q284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$485E8360-1E56-4790-B266-9B5EC552D800","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":"Q800088$1C07DCDC-F34F-4A79-9CC2-3A5CB2C5A90B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb71af2297f2d4637f6aefa8621d2a1ed05cfc22","datavalue":{"value":"W2017672035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800088$6D476F40-C214-4295-9E07-A0D021DD654E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$A391AF88-3587-464A-A78B-81C2939A1489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fad0eea4713b5529216bb11b7cda5de141fe05c","datavalue":{"value":{"entity-type":"item","numeric-id":1165027,"id":"Q1165027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$B4014E11-D50B-4BB1-816C-F3724E1E578A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668859a5c221011b50c76e98065c8225ab79fca6","datavalue":{"value":{"entity-type":"item","numeric-id":4128015,"id":"Q4128015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$96E76869-01F6-4F3F-8C67-DA885B0C75F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654da187d4372cd016f5d177803660f8d9e36d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1836312,"id":"Q1836312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$7D0F6EDB-3CE5-4562-84AD-91E1A8A06662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5fceb2bd9c7d07fcf97a47a3cc2f3f7fc5055e4","datavalue":{"value":{"entity-type":"item","numeric-id":2559145,"id":"Q2559145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$8FFB869D-F783-4584-A19C-E7422E83D8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c8012f35b74a26d79be75daa81504827353a6c9","datavalue":{"value":{"entity-type":"item","numeric-id":4778268,"id":"Q4778268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$C12D917F-E923-4923-99C5-49CBE442028D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2031f8bb3115f52425ff4dd04c9a69b45d8420a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241509,"id":"Q1241509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$22E9A256-58B8-43A1-9E58-BECEBA1A411A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af525ea1fd445c05898a9991b61369483b6c7c29","datavalue":{"value":{"entity-type":"item","numeric-id":4142696,"id":"Q4142696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$34A0ECD0-90A3-4C33-883E-2D02870E29C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8b46364e633fd6e8829251e5ac30abfc60735d8","datavalue":{"value":{"entity-type":"item","numeric-id":4148951,"id":"Q4148951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800088$0292A891-F8DC-4DEF-89BD-17DECFFB9C1D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6abf6cea898a80b0b21b70709d2541fe76caf338","datavalue":{"value":{"entity-type":"item","numeric-id":3395134,"id":"Q3395134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23384149f05a94df8c8e97e84890e065cf4df505","datavalue":{"value":{"amount":"+0.8079459071159363","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":"Q800088$DE50D333-D485-4B6B-92EC-C1A798D739C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3b76d2e4c5b18eef2944a4147d205dd092feb78","datavalue":{"value":{"entity-type":"item","numeric-id":3602818,"id":"Q3602818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d9354713b783421af4cc25b0d7ececfa20469fc","datavalue":{"value":{"amount":"+0.8067030906677246","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":"Q800088$B153A4F0-833F-494A-9044-20F4ED171EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9c987ac663afeac06745dd74ba20f53634e7883","datavalue":{"value":{"entity-type":"item","numeric-id":3687746,"id":"Q3687746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf2d675ba969d0960a3ec6f0885ce99431686eac","datavalue":{"value":{"amount":"+0.7804834842681885","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":"Q800088$A2E59C0B-6853-4F7B-AB86-623B815284F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4634c47007b7b99615e2eb37a990f1a12ac9a92a","datavalue":{"value":{"entity-type":"item","numeric-id":1109579,"id":"Q1109579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6894b6dd1c83444fdbda4111fe8109bcd321a976","datavalue":{"value":{"amount":"+0.7780645489692688","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":"Q800088$F808981E-0FCA-4113-B0D6-020E740A0153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7ed6e273484bf4a1aabe031d482383505b7e815","datavalue":{"value":{"entity-type":"item","numeric-id":3192259,"id":"Q3192259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febfb35abf8538bd847b45da6bf68122c6d7b564","datavalue":{"value":{"amount":"+0.775184690952301","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":"Q800088$ABACBD47-DFFC-4D08-A8B2-94FE2CA9217F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deterministic two-way one-head pushdown automata are very powerful","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deterministic_two-way_one-head_pushdown_automata_are_very_powerful"}}}}}