{"entities":{"Q759487":{"pageid":761336,"ns":120,"title":"Item:Q759487","lastrevid":48764350,"modified":"2026-01-05T19:43:46Z","type":"item","id":"Q759487","labels":{"en":{"language":"en","value":"More on the power of chain rules in context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3881892"}},"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":"Q759487$619940BD-F175-4042-BB38-6A8D2A4E98A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35e97b6129d91efdb1cf9ce5ad9d318a6377b864","datavalue":{"value":{"text":"More on the power of chain rules in context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q759487$E069ED84-77C7-40DA-AE6B-FC7C520C70F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af6304d4ecfe8cea193047f087257a40164b75e2","datavalue":{"value":"0553.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759487$E378BA19-62A3-4BC0-9F68-AB467F8F1282","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c93de975e540238981ade7d4ce8955fc2a5a9935","datavalue":{"value":"10.1016/0304-3975(82)90122-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759487$A7C3570E-6486-496C-BFA0-4C698EFECB1D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"08131e7df347bd9f8c4a917a9f56590bc7002234","datavalue":{"value":{"entity-type":"item","numeric-id":672726,"id":"Q672726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759487$D1B7E50D-827F-4EC1-9605-16955233F6BE","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":"Q759487$C63C9051-9E47-4863-B43A-36C42A224D1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q759487$304FB25F-4256-4CC0-8AE3-39A30074F855","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5682e2331ceb9bac25fb796ea5d3ce3ad91740f2","datavalue":{"value":"For all \\(\\epsilon >0\\) we prove for every sufficiently large n: there exists a context-free language \\(CL_ n\\) with the following properties: (a) \\(CL_ n\\) has a cfg of size O(n). (b) Each chain rule free cfg for \\(CL_ n\\) has size \\(\\Omega (\\epsilon^ 3n^{3/2-\\epsilon}).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q759487$7E3923A5-257F-45EC-95FE-A2BCBB5FED64","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759487$1DC45EF5-DD75-4665-9806-A596E98A5769","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3461e1a14e9b8659d5b01b6955c362e37633462","datavalue":{"value":"3881892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759487$B3A1C24A-22C6-4752-80B2-E1A7D89BB682","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3f95e606128bc14fa7512200099baaf2c1faa4d","datavalue":{"value":"size reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q759487$57CC94DC-DD70-4D21-9714-5B891AC1B978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d75d448735778f46c4e9667e177539a844422b26","datavalue":{"value":"context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q759487$05E94D53-B4AE-4A77-A11A-6CE0E65CC4AE","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":"Q759487$EA49871D-B5E1-4C92-B23B-BDE0C4670746","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"13f75550f150c1fba2769146d54fc5e5967a9057","datavalue":{"value":"https://doi.org/10.1016/0304-3975(82)90122-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q759487$44770FAA-A267-4480-B45F-B3FDD1CBFB90","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c6dd7b783230429f13d045a10e4b4b5a0fa5af6","datavalue":{"value":"W2071991779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759487$DA295DBB-E8FE-4E65-AED1-0E9A36CC4EAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"846773ddc0e790ec1eb038f139d068f54c6f888c","datavalue":{"value":{"entity-type":"item","numeric-id":1168748,"id":"Q1168748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759487$03332451-19BE-4C0F-8F08-DF9EF0370F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759487$B873ADFB-F346-4705-9463-8A0C6286318F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344f697a74f08c27dbfe2d6124ad1eb1876a2d05","datavalue":{"value":{"entity-type":"item","numeric-id":5567713,"id":"Q5567713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759487$006C7481-341F-4C39-ACEE-F28A6D47CC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759487$CAE64198-5F03-40B6-BF25-5820DBB870C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"327dca9d6f8ae94ca8a09bbbd95fdc9f90912811","datavalue":{"value":{"entity-type":"item","numeric-id":1944159,"id":"Q1944159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90f63ded1370521c71af9491a3a148583ed4095f","datavalue":{"value":{"amount":"+0.772000789642334","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":"Q759487$4A8FFE40-9A36-41C8-B370-2586B9D92F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"579f428a62999347c2a08ad8a8dd66d99c484a99","datavalue":{"value":{"entity-type":"item","numeric-id":1098318,"id":"Q1098318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a58aaec3f4978f3b0dac92e688029c9ab5dea64","datavalue":{"value":{"amount":"+0.7509542107582092","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":"Q759487$270DFBD8-63DB-40B9-95BE-115DAAABF0DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c9b7bc434f55242ac24cffc4a19e3c5d95a5c49","datavalue":{"value":{"entity-type":"item","numeric-id":1854266,"id":"Q1854266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7df0d6a82a288f7e0d00f1987169a8745627ff24","datavalue":{"value":{"amount":"+0.7488687634468079","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":"Q759487$9E3184EB-EEEA-4CE1-BF4D-6F67A2DE8F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1bab57a16badfe8b5ef723f46cbd0bb8b45456","datavalue":{"value":{"entity-type":"item","numeric-id":1892201,"id":"Q1892201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5de8d1d279fa4fb792799f21455cefc7c8674032","datavalue":{"value":{"amount":"+0.7479202747344971","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":"Q759487$2160113F-9362-40C3-A409-842AFDB90923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba54aea4f172dfe2fed68136c14cb5d4ed990616","datavalue":{"value":{"entity-type":"item","numeric-id":3321486,"id":"Q3321486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5de8d1d279fa4fb792799f21455cefc7c8674032","datavalue":{"value":{"amount":"+0.7479202747344971","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":"Q759487$900FB8F8-319E-4E08-BDEB-E77D7709E933","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:759487","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:759487"}}}}}