{"entities":{"Q5966461":{"pageid":8143257,"ns":120,"title":"Item:Q5966461","lastrevid":41767592,"modified":"2025-05-08T03:13:14Z","type":"item","id":"Q5966461","labels":{"en":{"language":"en","value":"On Greibach normal form construction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3986656"}},"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":"Q5966461$1C24CDFC-8BF1-41C3-8395-7F5D06AB15A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc21fddb644b6f40f3070f844f3d8750a1b7c55b","datavalue":{"value":{"text":"On Greibach normal form construction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5966461$D8106481-57A0-4402-A29E-788FEDA76585","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b22d058fa8d2b0c8700ba40bfd4f7fe3b1c287fa","datavalue":{"value":"0609.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966461$93EED0F5-918B-4341-A63F-4730F38583CF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03af44df093ae02ba66a5a324ee9fbac4484cb3f","datavalue":{"value":"10.1016/0304-3975(86)90120-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966461$F96246CB-3628-40E6-836F-F4504E506C14","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfa9051a33e618ddcfe8cadcfd3170afacb6df6c","datavalue":{"value":{"entity-type":"item","numeric-id":1084872,"id":"Q1084872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5966461$3D150FE9-0D55-4A9F-9D15-E20A02516C6F","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":"Q5966461$CED9F491-201E-41E4-BF43-625E9D87589A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q5966461$25539A13-7397-42A9-86A4-284DFABB37EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23a740bf9ec62bbe948ecb18a751f31a18d49063","datavalue":{"value":"We present an algorithm which, given an arbitrary \\(\\epsilon\\)-free and chain-free context-free grammar, produces an equivalent context-free grammar in Greibach normal form (GNF). This algorithm is a generalization of an algorithm recently presented by Ehrenfeucht and Rozenberg. Using this algorithm, the well-known GNF construction of Rosenkrantz can be obtained. Furthermore it is possible to rewrite a given context-free grammar by a GNF grammar which has at most twice as much nonterminals as the original grammar. This result is shown to be optimal (with respect to the number of nonterminals).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966461$5B4A4323-EA50-4E44-84FA-D5139798E7B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966461$7849F5FB-6DB0-4C96-80B8-031EF81B2F32","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"62fd5893e944a09bb5cd6fcbb97d0acfb8dc513b","datavalue":{"value":"3986656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966461$C912EB8F-3526-4BD5-8497-7394C186D68C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966461$887D9975-49AB-4EE6-95DC-AE778D1BDCE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d8f95104569681b12147407e1fc63bde7079389","datavalue":{"value":"context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q5966461$8E74E1AD-8B4F-46C6-B475-0993BF83FF26","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":"Q5966461$93434CC6-0017-46AC-9FE5-C335E6758940","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"57094de5328e773ae77517b22060f53ebb5e0af5","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90120-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q5966461$03EBE544-5A3C-41B5-B6C5-D6B769C7BB43","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"263fe338c5936f1c757480fc943fe5b787b4c70f","datavalue":{"value":"W2044227836","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5966461$F4961202-7561-45B5-8268-73CA7EFCEFE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd03d996bd1a123b124e8bc111c25dc61d956a1","datavalue":{"value":{"entity-type":"item","numeric-id":3718172,"id":"Q3718172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5966461$4DC788CC-0E6D-453E-B2CF-5FF20C0D3988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1849ab32e5f722603619b3b709b4b800dccb65f7","datavalue":{"value":{"entity-type":"item","numeric-id":5526989,"id":"Q5526989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5966461$072D7651-A589-46EC-96E5-83D8A6FC2099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5966461$5D93866D-BF37-417D-A6C8-22CFFBD5507B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fa2a09016d58a3906ccba4509610acd550a9a60","datavalue":{"value":{"entity-type":"item","numeric-id":5903291,"id":"Q5903291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5966461$7C3A03B4-1EFA-4D51-8CBC-B2F9406572E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7e1eb7aad5111a30c29ceff558cf732a8a6576d","datavalue":{"value":{"entity-type":"item","numeric-id":5903291,"id":"Q5903291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d21f0bbf0cc721b49da6898ce8a6097906145d1","datavalue":{"value":{"amount":"+0.9999996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$623E5901-3B75-4F8D-8824-E39274053E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3a3cd0fae2b90daa2f85b1b9d735a25a3b7b618","datavalue":{"value":{"entity-type":"item","numeric-id":2507685,"id":"Q2507685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"238d3f7d16bbfc52b9ec8e19dea143456daab6ac","datavalue":{"value":{"amount":"+0.88843215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$E19DFC5F-E640-4F4A-9DC0-B096FC975E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f594bcefccc8bc470a95a0a5df3a2c88c158ce91","datavalue":{"value":{"entity-type":"item","numeric-id":3468619,"id":"Q3468619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a320641cfcd13cbe3be61a4bebd38ed466585a7b","datavalue":{"value":{"amount":"+0.8830558","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$D187FFA6-5F4C-43C2-BC0E-81BB0A800208","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":"3fc80b6966c1061645109317cd5e7a41c8a5dc34","datavalue":{"value":{"amount":"+0.88035583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$6907DC8C-A1A0-40B9-BD0E-CA20E8B39EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22775bf698b9f83776faff4343b846f4cc304fba","datavalue":{"value":{"entity-type":"item","numeric-id":3508476,"id":"Q3508476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"701fde14d7da26a80cb0d3ff5c7cc27548a80838","datavalue":{"value":{"amount":"+0.86927307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$4FA2FD22-776F-4DD5-A76C-E0C9A34472DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b864c66f80271a5d369a7919782a697fa05c301f","datavalue":{"value":{"entity-type":"item","numeric-id":3975245,"id":"Q3975245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"947b81492786c909ec950869c14c70672706e4aa","datavalue":{"value":{"amount":"+0.8670922","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$A6378B50-834C-4E08-B8E5-FA24A7377E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3bde2e30c162894640ba94092fd36b1b05e3091","datavalue":{"value":{"entity-type":"item","numeric-id":5271041,"id":"Q5271041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1da4776212777f4e9a37676341cff66010174caf","datavalue":{"value":{"amount":"+0.85642856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$06C185E0-DE01-40B4-8A22-811FB43DF334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30d95d9120f1ef6987c64dcefdd62be1233b302e","datavalue":{"value":{"entity-type":"item","numeric-id":3718172,"id":"Q3718172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dd15c6adff69f09af1ce1716490912462592e3d","datavalue":{"value":{"amount":"+0.85482055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$72C14DAB-698D-486F-9933-BDA5D09CE1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"426ff016b47319c07594770c6c1cc646e65a2408","datavalue":{"value":{"entity-type":"item","numeric-id":2365320,"id":"Q2365320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28162a7aac4eddd2dbcd4a760cd32475ed11cc68","datavalue":{"value":{"amount":"+0.85480964","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5966461$82B88A04-3F9E-4130-AC75-39B2F25854B8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5966461","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5966461"}}}}}