{"entities":{"Q1193887":{"pageid":1204636,"ns":120,"title":"Item:Q1193887","lastrevid":66825318,"modified":"2026-04-12T13:06:45Z","type":"item","id":"Q1193887","labels":{"en":{"language":"en","value":"Partial memoization for obtaining linear time behavior of a 2DPDA"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 65321"}},"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":"Q1193887$F3C5302A-E0F4-4B80-80AB-11D32B348354","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"68334d9c63e1e06a075a22e32c4a8249d4ba505c","datavalue":{"value":{"text":"Partial memoization for obtaining linear time behavior of a 2DPDA","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1193887$597CAFF7-3607-48C6-A406-94A991D95203","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b3c9aae93abaf0f3057e5d09b19360923091efd","datavalue":{"value":"0763.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193887$983BCEB0-75FE-4BB5-BD29-1A7C88B34840","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4a463178cd0b9e9ad0ca2129cd0753cb0d5401b","datavalue":{"value":"10.1016/0304-3975(92)90008-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193887$94ECDE92-D612-493D-BC35-7115363F7272","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6c99b545c7552dc10b633a7e0065b9914032c04","datavalue":{"value":{"entity-type":"item","numeric-id":859951,"id":"Q859951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$6D41FFEA-BC8B-4576-B5AB-D86EC39305AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"59b8f8883487dfee0363ea1582bb9efab74a0784","datavalue":{"value":{"entity-type":"item","numeric-id":436807,"id":"Q436807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$47702CC9-D856-4F41-914C-7D23E1CCAFA7","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":"Q1193887$5830AB92-9581-419E-BFD2-C7BCBF2B51C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1193887$94518EA4-4C10-4FBD-B1A1-79769A3E996C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20f624ae55b1e761c15158aeed7e9dfcd992de7b","datavalue":{"value":"\\textit{S. A. Cook} [Inform. Processing 71, Proc. IFIP Congr. 71, Ljubljana, Yugoslavia 1971, 75-80 (1972; Zbl 0255.68015)] demonstrated the possibility of simulating any given 2-way Deterministic Pushdown Automaton (2DPDA) in linear time in the length of the read-only input tape.   It is shown how this result can be obtained by means of a generalization of the well-known concept of memoization. This clever evaluation strategy will be termed partial memoization. A straight-forward simulator for two- way deterministic pushdown automata is presented, and it is shown that this simulator --- if memoization is performed on only a subset of its input parameters --- will run in linear time in the size of the tape input argument. Hence the idea of partial memoization provides a new and surprisingly simple proof of Cook's theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193887$E007069A-A5E5-4866-AA47-3347312F4163","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193887$FF837E51-4850-4F30-8C8E-C3E756CB3D44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f51305856ed84401bb7be28903e225437f368a4","datavalue":{"value":"65321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193887$713C79C0-829A-43FB-9A98-AEF55D522F32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f84741d92afe8fc80c594aed6b861040ad27899a","datavalue":{"value":"pushdown automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193887$22DCD5E4-C31D-43F6-822D-FD01D232F783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32089794c559051e9fe3202986acc490c45fac8d","datavalue":{"value":"generalization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193887$51245D5F-F277-4C8E-B23E-191A4C73719B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2ef000af645fb54d4f204d80d410ec6dc82f4d3","datavalue":{"value":"partial memoization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1193887$98B77471-DECA-4511-8EE1-900174992E8E","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":"Q1193887$0645C005-0E25-4540-96F7-063937174278","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b34783f5db7bb96f4c8e8e2b4de79285696ed8b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(92)90008-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1193887$A03F7B01-16CA-4C75-A550-D81DB0849334","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3cd6c8afa19f02ad88bd0d76a22708b5a445314","datavalue":{"value":"W2031853502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1193887$AB5FFC9B-9106-4E2B-A18E-4C957436CAB2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$06410DDA-018C-448D-82ED-7886605034A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0c3d18dc1c22b123ff3891ccae6b075b5a1e922","datavalue":{"value":{"entity-type":"item","numeric-id":3826542,"id":"Q3826542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$1528FA6E-A49C-4F8A-8905-0E290FFE8A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b473f78d5f73a668f3283cc9b347a4a7e4dc1e0","datavalue":{"value":{"entity-type":"item","numeric-id":3919065,"id":"Q3919065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$C7835B1D-7FE3-4A59-A37E-1A1541EC74F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afd5865a7797cd1dbdcd00e31ed475893f29a8de","datavalue":{"value":{"entity-type":"item","numeric-id":3040478,"id":"Q3040478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$0906142C-E25A-4A0D-91EA-057700EC6765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7698ce631f410b3716c906843b5288c4644af32","datavalue":{"value":{"entity-type":"item","numeric-id":5670175,"id":"Q5670175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$B5010795-1BB1-4DDF-BCA6-8997E0760C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84420e850e3a03895bf09a52e836bfaa644de8bd","datavalue":{"value":{"entity-type":"item","numeric-id":1245694,"id":"Q1245694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$1C6037A3-2CB7-4D56-AC4E-9D2BF26DFA62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1193887$356E2FD7-38F3-4935-847F-D295B0BAAC2C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"750697d9490900b612477d755577285baf5db933","datavalue":{"value":{"entity-type":"item","numeric-id":4875449,"id":"Q4875449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b48bd44bac0fefdef33f683052736e9c9343246","datavalue":{"value":{"amount":"+0.824544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$7E8BF72D-9DA1-4C04-9E20-8C60A2669F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ffb942f91cf36ce666a67e2ac72c9fe09c33b60","datavalue":{"value":{"entity-type":"item","numeric-id":5348874,"id":"Q5348874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"610ffe0843b16bda82570292ecd38552d6682889","datavalue":{"value":{"amount":"+0.81426525","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$F9AD7BE4-8F17-4813-ACBF-EA001206A472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420aca7cf2be3d53678c5d760369ab1760342dca","datavalue":{"value":{"entity-type":"item","numeric-id":1791205,"id":"Q1791205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc4d6929fe8b815d8b0d5f59bf6cba40df247789","datavalue":{"value":{"amount":"+0.8130386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$4921510F-FFF4-4994-B3D0-E121F8CA850C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef8a9d39207d063719adc7679fb5311152274a0b","datavalue":{"value":{"entity-type":"item","numeric-id":459939,"id":"Q459939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cda3e96cf5f46cba61262ca11c35cd1620433ad","datavalue":{"value":{"amount":"+0.8123532","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$DF25E739-5671-4C57-835A-7F0C91BD53BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14fbb7b8319e1ed58def5a038528e0f52ed67a99","datavalue":{"value":{"entity-type":"item","numeric-id":4414778,"id":"Q4414778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61bd21a6e12d89f6e926aa25efb19f84d44f203d","datavalue":{"value":{"amount":"+0.8104032","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$D0E877C0-A3EB-4474-8439-D0255F4C82DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e00e5dec0da9ac748509085e3805a37f115a905","datavalue":{"value":{"entity-type":"item","numeric-id":3409863,"id":"Q3409863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"326cec41afb4a93f79f37fc30d65feaa8c9c06c6","datavalue":{"value":{"amount":"+0.8085207","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$C2C862FE-5B32-46F0-AFE7-E6838A08709F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98771251f7533844510a9ff24221734b0c022106","datavalue":{"value":{"entity-type":"item","numeric-id":1640979,"id":"Q1640979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19479306a6a7cfe5066804ece092f4c52731a29e","datavalue":{"value":{"amount":"+0.806705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$E06C2E13-17E7-4B48-8EF9-5FE545ACC27C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65f7fa9de17a993f47a1633e52fc3c2361223d42","datavalue":{"value":{"entity-type":"item","numeric-id":2954984,"id":"Q2954984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19479306a6a7cfe5066804ece092f4c52731a29e","datavalue":{"value":{"amount":"+0.806705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$B523F3CE-693F-4E11-B33E-49EC42EF386A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60246c29112d6e5f16162a042eee91f52753d210","datavalue":{"value":{"entity-type":"item","numeric-id":3352925,"id":"Q3352925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fa89542d25049b4235b05d25a53bc55fe67ed4d","datavalue":{"value":{"amount":"+0.80660933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$199C10E9-610B-489D-8316-216BF9ACAA11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"610ad2003cb521662242ca50c21f624606e1ed4b","datavalue":{"value":{"entity-type":"item","numeric-id":2911644,"id":"Q2911644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"673f23c3fe09dcc204ff13469feb50ea3567961e","datavalue":{"value":{"amount":"+0.80145454","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1193887$C69E56C1-1813-414C-8A66-438584CAE81C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Partial memoization for obtaining linear time behavior of a 2DPDA","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Partial_memoization_for_obtaining_linear_time_behavior_of_a_2DPDA"}}}}}