{"entities":{"Q1096400":{"pageid":1107152,"ns":120,"title":"Item:Q1096400","lastrevid":66956697,"modified":"2026-04-12T13:58:24Z","type":"item","id":"Q1096400","labels":{"en":{"language":"en","value":"Parallel time O(log n) recognition of unambiguous context-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4031020"}},"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":"Q1096400$F0386E42-2C9E-4B70-AF83-B276AC37953E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eded3730a649138f2c7a6d36b86541156938d047","datavalue":{"value":{"text":"Parallel time O(log n) recognition of unambiguous context-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1096400$DC4A83E6-6728-459E-BE61-B211D802E05E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b024669d70de40aaf519e6be1888559163b2e3a4","datavalue":{"value":"0633.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$F2E1B571-A788-49B4-9917-030E83C40C67","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"039f6981d51219d51f0fef8df9d7eccc036928a8","datavalue":{"value":"10.1016/0890-5401(87)90041-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$1A0CFE6A-C9CB-413B-B8FF-0F0B04095F07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"446a873621e510ca421dac98a0ecf4b1b1cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":313971,"id":"Q313971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096400$C20DA637-308D-465E-BA30-E0FE383B5D91","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096400$C1F0642A-2023-48BB-AF38-A4A36377257F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1096400$0F706414-C5B5-42B8-A005-AB23A589BF3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52db065f0cd7ef00e7790d082d98c9f0d29642f2","datavalue":{"value":"We prove that every unambiguous context-free language can be recognized in O(log n) time on a parallel random access machine without write conflicts (P-RAM) using a polynomial number of processors. This strengthens the result of \\textit{J. Reif} [Proc. 23rd IEEE Symp. Found. Comput., 114-118 (1982)], who proved that every deterministic context- free language can be recognized on a P-RAM in O(log n) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096400$CCE888DF-25A7-4480-A90A-AB7895AB5BBD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$4E852B41-92AA-4E31-BD0E-A6DCEBA0798E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$AB5B680C-E893-4863-AF28-3DB843DFDA68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8132793e3b9c3cc7bef433a5127856415645dc41","datavalue":{"value":"4031020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$97BAA3CD-DFB9-4587-9911-A09F3DD9054C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1b87f21a63142faf91e2c14b95e47a6a253cd0d","datavalue":{"value":"unambiguous context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096400$E08E68F1-820E-450E-B6A5-7332F5E6ADD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3b1af11f932c20dbc5a129b29d8d5d19e1d9d96","datavalue":{"value":"parallel random access machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096400$97B4C94F-32B8-4CE3-8CF5-551071EEA485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc68e48ba3c8d693c7ec3942cf84a34a20017dfc","datavalue":{"value":"polynomial number of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096400$440AF55A-4277-4980-8E42-6D6BF9CB2D30","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":"Q1096400$04165D26-5158-4711-BB41-76C44C3C7C73","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd3268d411e984c529cbbeb108fc9b3fe024116f","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90041-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1096400$1AA36DBE-E09C-49C1-8F64-348A9CFAB1F3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42b4409a89579fd8a292b6df49c03ee73f283f10","datavalue":{"value":"W2085339857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096400$B7DC6B33-5AB8-4F0A-81E6-431D51403541","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096400$6A09A877-70F1-4CFA-A4E6-FA5A8E7C538E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096400$B491D89D-22D1-4363-A8B5-D3716FAA57F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39a2b77e64dbb3ecf2e5ef657d6c92508e375a38","datavalue":{"value":{"entity-type":"item","numeric-id":3700838,"id":"Q3700838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096400$AD6FA341-65EC-4FD7-BCE1-8857DBDD38E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b40d39f12bb02ccbbda54b9592582dae720db34","datavalue":{"value":{"entity-type":"item","numeric-id":3692896,"id":"Q3692896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0799832d687205d48fcee224f51d23d9b7c49a8","datavalue":{"value":{"amount":"+0.9910153150558472","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":"Q1096400$A81FD0F1-6362-42C4-AE32-A7D9F65CAFF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"119b5c007b89db9521ed8070525a550443d2c13d","datavalue":{"value":{"entity-type":"item","numeric-id":808269,"id":"Q808269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32fbf34882ea867fd8cf1fe433cc87d5f0361ebc","datavalue":{"value":{"amount":"+0.9434708952903748","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":"Q1096400$463E8E55-FD5C-472C-809F-5D6C6D0F58E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98b6fa7b98b64f1fc1501f78978322023e8a54a8","datavalue":{"value":{"entity-type":"item","numeric-id":1209354,"id":"Q1209354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df8d30f4c8fcb6994d3efa7db6f703200227c5b1","datavalue":{"value":{"amount":"+0.9036421179771424","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":"Q1096400$6FE9CAA1-5FCD-45D5-8BB3-ED4A557AB8C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73ab280c84f5bfd6699340fa34ec7994c7253dfe","datavalue":{"value":{"entity-type":"item","numeric-id":3730022,"id":"Q3730022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fa0e96c563c7f0b11f3d460790e6b83c92e1e10","datavalue":{"value":{"amount":"+0.902984857559204","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":"Q1096400$205129E3-1EE5-4BE9-9525-E49A513B492B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94e1ce4f398767ff1dc3b51c26e7e73856bd7c05","datavalue":{"value":{"entity-type":"item","numeric-id":5096817,"id":"Q5096817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f60c991b25be8c62ccba9fae116141798d2b84","datavalue":{"value":{"amount":"+0.8630686402320862","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":"Q1096400$36E7E061-0654-41FB-B51A-858A2AD2CF21","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel time O(log n) recognition of unambiguous context-free languages","badges":[]}}}}}