{"entities":{"Q688231":{"pageid":690080,"ns":120,"title":"Item:Q688231","lastrevid":63490701,"modified":"2026-04-11T13:30:52Z","type":"item","id":"Q688231","labels":{"en":{"language":"en","value":"On the reduction of \\(LR(k)\\) parsers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440380"}},"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":"Q688231$6659A3F4-193F-44EF-BE6C-B42A38CC6C02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"62dd07dd4ac6eb61ccc5dfb95793b191c366097c","datavalue":{"value":{"text":"On the reduction of \\(LR(k)\\) parsers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688231$B53FFAF5-1244-4530-8837-E91247A32F73","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42bee827b962dd5b68f188699f7564c6ab6b9135","datavalue":{"value":"0818.68105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688231$06493AFA-0330-4502-B24B-AC5CBDFD21A4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8732065efab3cedad71de38e2296b9113dd1d08","datavalue":{"value":"10.1016/0020-0190(93)90134-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688231$0326C2F9-4E31-463B-AACE-3F216D96EA4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d8e338f45fb448f09a2773fcae1c6955dd15c78","datavalue":{"value":{"entity-type":"item","numeric-id":688229,"id":"Q688229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$6375E098-96AA-4FC8-898E-A996AAD9AF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f41246828b23ef0232623458ac39b07835bfdfd","datavalue":{"value":{"entity-type":"item","numeric-id":688230,"id":"Q688230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$29E86F8D-E11C-4011-A729-C2948ECBF936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2124b2f1dbc31bc9ff8d394053874ee5358b7f4","datavalue":{"value":{"entity-type":"item","numeric-id":578923,"id":"Q578923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$E8E6C84D-2B16-4D75-BE1C-DD8ED9019019","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":"Q688231$400EAE1E-8E40-4863-A1A4-7BDFE87AAE58","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"307580e22f2d20de23b936c4fce7539a5342cbe9","datavalue":{"value":{"time":"+1995-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688231$C24C10CA-1BCE-4A27-AC8A-66C42CB1A538","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"50cf8c37465c3c2a6a708a54af06a261284f979e","datavalue":{"value":"We propose a new formalism for merging \\(LR(k)\\) states without any conflict, after constructing the full \\(LR(k)\\) parsing table. First, we define a new relation compatible \\(C\\) and \\(C\\)-covering for a core block, both of which are different from the notion in dynamic reduction methods. Then, we propose well-defined reduction (WDR) which is a set of \\(C\\)- covering for each core block which reflect the rationale for \\(LR(k)\\) state reduction, as a new formalism. We present algorithms to compute a WDR and an \\(LR(k)\\)-based parser for the reduction. Furthermore, we introduce a useful core-restricted method, a locally optimal reduction as an approximation to an optimal reduction. The contribution of this paper to \\(LR(k)\\) parsing theory is summarized as follows: (1) to discover that set of \\(LR(k)\\) states of a core block after the merging is not a partition, but a covering of the block. (2) to propose WDR which provides a new formal view for the computation of an optimal reduction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688231$737EC3AB-6F41-4BF6-B4D9-6E48B4E01146","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688231$5EF50667-84CC-4F9A-8D55-F217C7902F6C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b502e68602470ec9007657685f22a4bf8dd5fff9","datavalue":{"value":"440380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688231$B79818E8-AED7-4AD0-8504-D49375D5F022","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a8e0481f2d0a5bd6b52b85f64e9aba09c25bdb0","datavalue":{"value":"well-defined reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q688231$E54545EA-2F00-489F-B0E9-63982C78F3B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1b30407a14684b78d0b920fb58636ed4c0505d0","datavalue":{"value":"parsing theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q688231$15D82888-C8A4-4F26-A780-76CCC567FAE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"397f0fcfe559cfe37f2292b68dfe99c79c811e52","datavalue":{"value":"optimal reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q688231$23E296BB-6872-45DF-9688-B80B5591B3A8","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":"Q688231$5038167F-01F6-4A26-9B17-21B4D65FDA6C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d63b2a711efc064ad4439829471749b3bcf75e64","datavalue":{"value":{"entity-type":"item","numeric-id":4068115,"id":"Q4068115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$8BC4EF2B-1DC5-4C40-A4EB-6956C369B5C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39384d14d7e157246680597fc7ae9d1b624930fc","datavalue":{"value":{"entity-type":"item","numeric-id":5632153,"id":"Q5632153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$5854EC4C-20CB-4ED8-A105-7F9412A4350F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e87bc171c31b1d27fc0d0111fa2fd74fbb9c7ad3","datavalue":{"value":{"entity-type":"item","numeric-id":1157181,"id":"Q1157181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$4C2CE3AA-2480-4EBF-A71B-99F7323F693C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce2958c69fc0ffe7706f790c429d92fee458ed25","datavalue":{"value":{"entity-type":"item","numeric-id":5639365,"id":"Q5639365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$CB86FB63-9E60-4375-A850-1EDA517F1E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"716cd1bbd8197c5f8943a201585fd02a369d380d","datavalue":{"value":{"entity-type":"item","numeric-id":751291,"id":"Q751291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$71B92550-FF09-4EF6-82F0-6AB5BE90065A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7e273d45d44d09952b70dabc45fec7ec7c89bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1238429,"id":"Q1238429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$BBB5D3F1-6FB9-4D55-9762-4F662761F032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21c12e50b08df7c65a8b09d0727bb0004586fa55","datavalue":{"value":{"entity-type":"item","numeric-id":3341936,"id":"Q3341936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$EC8CC4F2-1160-4441-B0FF-26C473386966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed7cf71594ecde4ea017738b06b15c3808240ac6","datavalue":{"value":{"entity-type":"item","numeric-id":688231,"id":"Q688231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$071F1DA7-A9B8-4126-A249-965BFDA00DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e320d5ab20d9378e83c08a862b63bf2725892d4a","datavalue":{"value":{"entity-type":"item","numeric-id":2653567,"id":"Q2653567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$B77516F1-070B-4416-9C4A-11090F06E6AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1ddbad64cbd5143153cb26e8ef463a3c21e4944","datavalue":{"value":{"entity-type":"item","numeric-id":4072797,"id":"Q4072797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688231$4E80D7DA-8424-4E2E-8AF3-F26EA4B22B2D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9220a0200d03a052a1d37ed0878d09c5731b83b9","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90134-u","type":"string"},"datatype":"url"},"type":"statement","id":"Q688231$8F1C043B-D6B9-49D8-A4BF-B38898034CF8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"52766913ebf6de49d6b6a896af192bdfd0e1ebba","datavalue":{"value":"W1996765415","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688231$99B6F508-85F9-4AB2-B69A-B91F32A8B047","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d7d6692f7933f4f396a152c577c4a7289e9d6c9","datavalue":{"value":{"entity-type":"item","numeric-id":1186566,"id":"Q1186566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03a1522564b2c2dd3e64edb82cdd4d8bf78d5e00","datavalue":{"value":{"amount":"+0.8352824449539185","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":"Q688231$3CE68B4F-361D-41FE-A735-0D3B533DAEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cfeddef1c458f95893ff9951f1557551f45b8b7","datavalue":{"value":{"entity-type":"item","numeric-id":3826121,"id":"Q3826121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b665479c99e99cc376f01f142cc0125fe5ef437","datavalue":{"value":{"amount":"+0.832947850227356","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":"Q688231$97C9C512-13FB-47F2-B14E-56E62E6D5905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a74ae468baaa469ab6516f408981f3252052d2","datavalue":{"value":{"entity-type":"item","numeric-id":3139285,"id":"Q3139285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e026f759b8b54fe41a84c8dc344f201695081c75","datavalue":{"value":{"amount":"+0.7928614616394043","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":"Q688231$A90B31F2-77D4-4036-828C-62BEE7A8C556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2f1274aad55f58be3a74aaa87f9b26459f3d1f4","datavalue":{"value":{"entity-type":"item","numeric-id":1196299,"id":"Q1196299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"974fcdf139c03fa51b0cbbb277eab8b366de7686","datavalue":{"value":{"amount":"+0.7916205525398254","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":"Q688231$3F37A0F3-9F08-4B29-9711-22EA73E85944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d7d52e5ccd486945a52884e87a611c453fbdd1b","datavalue":{"value":{"entity-type":"item","numeric-id":4040864,"id":"Q4040864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e83f4856b17a446deb39990f2f286bd2a6b6f06","datavalue":{"value":{"amount":"+0.7915553450584412","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":"Q688231$5AB4C364-A5CC-4A18-8E87-2CBEFD2E923A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the reduction of \\(LR(k)\\) parsers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_reduction_of_%5C(LR(k)%5C)_parsers"}}}}}