{"entities":{"Q799380":{"pageid":801228,"ns":120,"title":"Item:Q799380","lastrevid":64501560,"modified":"2026-04-11T20:18:23Z","type":"item","id":"Q799380","labels":{"en":{"language":"en","value":"Complexity of normal form grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874639"}},"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":"Q799380$254DB948-DCE4-457F-A56F-983C604C8CA4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51fbad8d2fd2852736b02b65c0fdd4fe271a7233","datavalue":{"value":{"text":"Complexity of normal form grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799380$4FEE8FE7-B4A8-4B75-BD6D-13697CDE6655","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"448ecbb97dce8c45b58ef6dc38f4e450ecb9bb3a","datavalue":{"value":"0548.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$C92E4391-92EC-43FB-B2BF-B9916836459D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96e6209bc14514fcbf935b8892fdac04dccba584","datavalue":{"value":"10.1016/0304-3975(83)90026-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$FBE89EA0-9280-47F8-B3EA-C2147BA0444F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"94099811c0ee6ac99cdc0241f20de4621e078456","datavalue":{"value":{"entity-type":"item","numeric-id":700789,"id":"Q700789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$43951A89-7799-4778-840E-5E5D887E4F4C","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":"Q799380$7047AC32-A3D8-4C66-ACCA-CAA256B61626","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q799380$7F157D2A-35E2-4AD6-9301-28092CBB4430","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dee0c80914a7653e4e9c42cb9b8f601f5c3a920f","datavalue":{"value":"This paper considers various descriptive complexity measures for context free languages such as the number of productions, the number of nonterminals, or the total length of the corresponding context free grammar. It is investigated, how those complexities increase when going from \\(\\epsilon\\) -free chain-free reduced grammars to certain normal forms, such as weak Greibach normal form or position restricted grammars. For example, the number of nonterminals increases by at most a factor of 2 when GNF is used. For weak GNF-grammars the number of productions goes up from n to at most \\(O(n^ 3)\\) and examples are given where \\(\\Omega (n^ 2)\\) are needed. The same result holds for the total length of grammars. Transformation into position restricted grammars may rise the number of productions or nonterminals from n to any arbitrary high value, i.e. it cannot be bounded by any function on n. However the total length of the grammar goes up by at most a constant factor for some special cases of position restricted grammars especially for Chomsky normal form.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$8C7DAABC-2E5D-435D-98ED-14DAA85B0E9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$01E5C672-3850-4BAC-BAA4-841BFDB2D91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$51F1489F-7D22-4D4C-B05D-5C103E300990","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b1c0256086f8cd84d9983e42382f7b20de99d9b7","datavalue":{"value":"3874639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$CBED620E-A47D-43B9-BACA-F5BC7C9E735C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$3DD3F3DD-D573-45FA-9246-69B3E307F6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dd5f26409163ea00d953c452775bbb96da624ca","datavalue":{"value":"description complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$23BDD1C6-EDAF-4A98-87DD-6335890B8FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44d2f2957b6a571bacf97ef6be5a6945b29311c7","datavalue":{"value":"context free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$ABA68502-B701-4396-9A90-0556AE20F105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d55dd22c47fd825c1b9f4ee367faf31219dec8a","datavalue":{"value":"context free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$0E98FBBE-D33A-49F5-B735-0860DE41D7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8af76bfbe81b16541cca3b1ddbd068d9d6b8d69f","datavalue":{"value":"normal forms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$B92E9808-2423-4C20-9F2C-65EE5F1F9DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fca14b9ed07293be35740aa4f7371a9ca98962d","datavalue":{"value":"position restricted grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q799380$AC9D7503-112C-4F9A-A7D9-671D90894B55","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0aa8d3ac5bbff6b41e0a3e53ebafb780beece760","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$361D68BF-9DDA-422F-89ED-3B4A7D810E43","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":"Q799380$736A1010-F5D2-450F-8E95-5AD6CE0938BA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b39be2d1d2d52133140b89377379acd5024099d6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90026-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q799380$BA8E1B67-0607-445F-94FC-517350D1BAB2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6b85d0e8dab1175d29247a6dea51506c8f18ed0","datavalue":{"value":"W1998938240","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799380$582CF23A-E30C-433A-9651-F89F26850CBB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e37d3cd89bf56058a2b19db5dd9a0a78bfe825f","datavalue":{"value":{"entity-type":"item","numeric-id":2561843,"id":"Q2561843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$958124C0-D8B7-4456-B8C0-7DD4A51A2290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03440478e8a977a09546a178f2902fe3049f0099","datavalue":{"value":{"entity-type":"item","numeric-id":4041111,"id":"Q4041111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$587E7824-A038-47FE-9B03-F4250F6A80F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3fa3a0ed87723dc781c874f27a11688451900e","datavalue":{"value":{"entity-type":"item","numeric-id":4128026,"id":"Q4128026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$D63919E3-30AD-4740-B993-9897526CC942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df339d46fcf03edbcf2f1cb39950fc86b5055035","datavalue":{"value":{"entity-type":"item","numeric-id":1160492,"id":"Q1160492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$88F29378-C817-4684-960B-1C9AD4266054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"842925c3f00729504114c782c00814cfad550931","datavalue":{"value":{"entity-type":"item","numeric-id":5562596,"id":"Q5562596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$9A1D391D-FDCF-4CC2-BF1F-A1DC4B43C9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1925789218688c1086435c0d25d8ed6efeb1a6f0","datavalue":{"value":{"entity-type":"item","numeric-id":4061989,"id":"Q4061989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$9D064D03-E0C8-4404-9B6E-76813A228401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18a53ca570dc0817a413f0d97dff02d9e887338c","datavalue":{"value":{"entity-type":"item","numeric-id":4105792,"id":"Q4105792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$53B009D9-A3F1-4651-B89D-1B91065AB0CC","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":"Q799380$2B7A3708-8F2D-452B-BA67-792C7D01F13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"899dcad7dcb405eb1d1fc1edbed4fe43562297f0","datavalue":{"value":{"entity-type":"item","numeric-id":3660936,"id":"Q3660936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$0514612B-CE8A-4FE5-BFF1-06E7910C978E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd50a72917f212c79c5848d292387c5257dd7e8f","datavalue":{"value":{"entity-type":"item","numeric-id":4080744,"id":"Q4080744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$456561AF-EE6D-4B8D-915A-9FD3078DB51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f60764865641217d564887c22fdd45b8531bb7","datavalue":{"value":{"entity-type":"item","numeric-id":3948608,"id":"Q3948608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799380$38990138-7B34-487D-8222-A3874E9354B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c480d9e0b8a12ae15bf0d7f21b050f762fae582","datavalue":{"value":{"entity-type":"item","numeric-id":4922674,"id":"Q4922674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f57c56bfb49c3c1360d21f6eb11e8786f8ba7a7","datavalue":{"value":{"amount":"+0.8834912776947021","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":"Q799380$C4B43782-C71A-443D-B03E-0FD6EAB19944","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":"3a9b3294dc6368878c0fae273c5394690d701755","datavalue":{"value":{"amount":"+0.8447144031524658","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":"Q799380$2A5E6B4D-6266-4716-8041-199AA6479EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d04c61fdb6b8a1245a3b8746e97444dfb0d79e1","datavalue":{"value":{"entity-type":"item","numeric-id":5966461,"id":"Q5966461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e4d76d31a4c30ba39e9bf126b49ea499f3b6b4f","datavalue":{"value":{"amount":"+0.8253071904182434","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":"Q799380$8E603824-A655-4EEA-8078-A961C7780E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69124e327e3b951e06dee0ec104ac3ad1e00cdc","datavalue":{"value":{"entity-type":"item","numeric-id":3777485,"id":"Q3777485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"404e79be8438bb0feba2625af05bbd8c01fabb02","datavalue":{"value":{"amount":"+0.8160926103591919","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":"Q799380$FC17E950-D7E3-4462-903F-B8CE02819348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5966343384db0a1b6fc0c2d812e7340bfe4df7ad","datavalue":{"value":{"entity-type":"item","numeric-id":5047158,"id":"Q5047158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7f10ff23d99e0c5d614cd762dad1eaf0cc492fc","datavalue":{"value":{"amount":"+0.8142289519309998","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":"Q799380$CFFD2250-0AC0-4B1C-B3AF-F733307AD4E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of normal form grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_normal_form_grammars"}}}}}