{"entities":{"Q1736491":{"pageid":1747232,"ns":120,"title":"Item:Q1736491","lastrevid":72377115,"modified":"2026-04-14T04:29:45Z","type":"item","id":"Q1736491","labels":{"en":{"language":"en","value":"The smallest grammar problem as constituents choice and minimal grammar parsing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042108"}},"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":"Q1736491$14E09A2D-5D31-43D3-AA2F-9E80D1D37D24","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6795f9ab0b3b499fdb56531667a028d31a3ed8b","datavalue":{"value":{"text":"The smallest grammar problem as constituents choice and minimal grammar parsing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736491$CA250A3F-16F8-475B-8A2F-350A996C9044","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"822f2082f86f74be70f0c06c209d0edf2bc8b738","datavalue":{"value":"1461.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$7D50EBA5-6100-448D-A925-962AD4EA1845","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d569c090f241100389ff770085c8024cc2a7eab3","datavalue":{"value":{"entity-type":"item","numeric-id":414448,"id":"Q414448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$EE172EBF-42E6-4D96-98B7-18AF337FD3AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38f3144bded2d7aca75d66522b53d42ce6eca636","datavalue":{"value":{"entity-type":"item","numeric-id":414449,"id":"Q414449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$A99249D6-8820-4106-A633-FC8BD9F8A21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e4d53e6680a54d7bfd7215b14855d33e3fef2a5","datavalue":{"value":{"entity-type":"item","numeric-id":414450,"id":"Q414450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$3B92500E-78D3-4849-AAD3-63BB80E64032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a937fa71410549635cf80ab8ea310d3a62aae46d","datavalue":{"value":{"entity-type":"item","numeric-id":414451,"id":"Q414451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$2CD2948B-EA6E-4C3A-9390-C2B8F2460E7A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$490F5D45-57FE-4308-A689-8D34D215C6F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736491$A5640EB2-3F92-4F0D-BADC-F7A3CB10B3C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85960473ae14c22aaf23149ffb42cb1e023461a7","datavalue":{"value":"Summary: The smallest grammar problem -- namely, finding a smallest context-free grammar that generates exactly one sequence -- is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. We propose a new perspective on this problem by splitting it into two tasks: (1) choosing which words will be the constituents of the grammar and (2) searching for the smallest grammar given this set of constituents. We show how to solve the second task in polynomial time parsing longer constituent with smaller ones. We propose new algorithms based on classical practical algorithms that use this optimization to find small grammars. Our algorithms consistently find smaller grammars on a classical benchmark reducing the size in 10\\% in some cases. Moreover, our formulation allows us to define interesting bounds on the number of small grammars and to empirically compare different grammars of small size.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736491$03C2F910-7667-45CB-A1E2-27C71E5EEC18","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$C976E748-5DB8-4C68-9F87-89C893977B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$BF85B0F5-31C4-42EC-93CA-32E2CE62DA01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66889389d21a45a0d49e9adbe995df89298b86ad","datavalue":{"value":"7042108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$594B9491-7572-4DA1-BC8D-05D0D586FB32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d8bfd47d72b66d6ede4fbc32745b628059bc816","datavalue":{"value":"smallest grammar problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736491$DB4CF096-18B6-4909-9A70-818A0DA737C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fce1dfaad2e72ec72b85673320f86e67841b2af","datavalue":{"value":"hierarchical structure inference","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736491$8549F7DE-34B7-4A54-8230-5FBBF1E01B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc611c599097acd7ac14ad7ca88a55e458528409","datavalue":{"value":"optimal parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736491$04D320BB-3898-44C8-91BE-9155ABD3F645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ee31a04d7dad26a40eb7577683806848688b162","datavalue":{"value":"data discovery","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736491$FAEE81D5-605A-4CF1-981B-3D0267FA8355","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":"Q1736491$7BEA46F4-3A0E-4AD8-8F66-2EBABF56DA7D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"87d4ced3cf169cfad68c64fea75c7b7ef24123a4","datavalue":{"value":"https://doi.org/10.3390/a4040262","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736491$CD642BC6-97EE-4797-AD79-C5AE7D56E4A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"70f8e78f4e53fc9788ecb82b268549a4a0aa3342","datavalue":{"value":"W2120469941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$B28F8C83-DBC6-4B1A-B949-BCE088CEC67E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3070c0519dcd5c6a76b393c3edf1244e326b734a","datavalue":{"value":{"entity-type":"item","numeric-id":3546682,"id":"Q3546682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$DDB0BDE7-53EB-441D-8CD7-C561502677FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4398a001fabea33eee52a30a71cfd3a06816389b","datavalue":{"value":{"entity-type":"item","numeric-id":1401326,"id":"Q1401326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$E12293F8-5023-493F-92F3-6639555CDBA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cc19e791edae5e8627a6e4d51b2d96428236e6","datavalue":{"value":{"entity-type":"item","numeric-id":4503585,"id":"Q4503585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$6C62F421-9BE3-42A0-B406-A49DDE8455B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e57fccc8c00238fd458ec81341321c0921c881c","datavalue":{"value":{"entity-type":"item","numeric-id":4174617,"id":"Q4174617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$C10477B0-F794-4540-9777-1272364FB6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88d206d4cbc8d8e320cb9ec4bf8947ea28927767","datavalue":{"value":{"entity-type":"item","numeric-id":4158937,"id":"Q4158937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$80040C0F-7E8C-4862-895B-9C0C4B4CACCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e44bc733ffdebee1fd5f4c42df2fbbccf3446dee","datavalue":{"value":{"entity-type":"item","numeric-id":1662518,"id":"Q1662518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$439F778B-128C-48A6-842C-C55688292B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d8bfe2b1db5784579aa52b41e4fb8610eb152ae","datavalue":{"value":{"entity-type":"item","numeric-id":4952646,"id":"Q4952646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$977D156B-8B80-4CA5-9401-C1D99A126AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d47ec4bf230b762d5c82f8bac81eddabc36456","datavalue":{"value":{"entity-type":"item","numeric-id":4386970,"id":"Q4386970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$FAF9D0F8-DC8A-42F5-BEE4-0FD670E9807D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"829a26bf5c2632f72926fc206d00a26bd3ea52ab","datavalue":{"value":{"entity-type":"item","numeric-id":1186808,"id":"Q1186808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$819091E8-B206-4CB8-B73A-1F6CE1534FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b91011b6579f71193018736fde2407421deed1a4","datavalue":{"value":{"entity-type":"item","numeric-id":3564857,"id":"Q3564857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$3FD9F12E-57DE-4C0E-95E7-FA6747664A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5be4288db1580f5486fedd45c0ec394688fe6541","datavalue":{"value":{"entity-type":"item","numeric-id":4347161,"id":"Q4347161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$B909F7EC-832D-4CDF-AF1B-125F33518308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$22B9EE50-CF4B-4172-B60C-4F3CFC41931A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c826bc97ee907b4fffafeb38dcc063b69619cf57","datavalue":{"value":{"entity-type":"item","numeric-id":4053104,"id":"Q4053104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$4D60CA04-5E9A-4613-A6EC-3E561D919D7F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0749bc487adf18aafe76bd63a761b36c24728feb","datavalue":{"value":"10.3390/A4040262","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736491$86FF84D4-41D9-41D6-8864-D873970356EC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6778d9f3ea83f4eb07db49c45170ee1b57387b1c","datavalue":{"value":{"entity-type":"item","numeric-id":3564857,"id":"Q3564857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc14ec8be45b8d3a819d6486fcf8987b24aba5c2","datavalue":{"value":{"amount":"+0.9193570613861084","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":"Q1736491$D3C16359-F177-45F5-BA90-04BDDD04653E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0586fb8377b7949fa69f40f33f256473a0c734f0","datavalue":{"value":{"entity-type":"item","numeric-id":414452,"id":"Q414452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfaab2633f62ba978622dc1525815d515e66fa18","datavalue":{"value":{"amount":"+0.875382125377655","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":"Q1736491$93551D89-DDC2-4D55-A375-7969B29D7A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e7bab5503195384aa77abbb8581ba285def1a9d","datavalue":{"value":{"entity-type":"item","numeric-id":3546682,"id":"Q3546682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a661e247eb5590410cb1348ea82a2cb93e0a547","datavalue":{"value":{"amount":"+0.8547639846801758","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":"Q1736491$9DE73E81-328E-43D5-95C6-BCF5E1AD2243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38f66834e0d815d0c04c2cae986775359302216a","datavalue":{"value":{"entity-type":"item","numeric-id":2035481,"id":"Q2035481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4d28186b17a659a9c5448ade179180236f9b715","datavalue":{"value":{"amount":"+0.825668215751648","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":"Q1736491$00BB40D8-8898-4231-9B34-27F0BB904687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a46d1ab80192cd269001e813631804fc11a5c14","datavalue":{"value":{"entity-type":"item","numeric-id":1796825,"id":"Q1796825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad17fd52f7e0b43e8985e1036e4694822899efd0","datavalue":{"value":{"amount":"+0.7995421886444092","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":"Q1736491$FCB630B2-00DA-4870-A6DA-17D1415F08E2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736491$CF31A5AD-E89F-4D75-95F1-186188B90D95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The smallest grammar problem as constituents choice and minimal grammar parsing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_smallest_grammar_problem_as_constituents_choice_and_minimal_grammar_parsing"}}}}}