{"entities":{"Q1067789":{"pageid":1078541,"ns":120,"title":"Item:Q1067789","lastrevid":69771555,"modified":"2026-04-13T09:16:51Z","type":"item","id":"Q1067789","labels":{"en":{"language":"en","value":"An undecidable problem for context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3930364"}},"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":"Q1067789$4159B2E6-91C2-4708-A096-AE19C15842EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"267f14e37e02271fb07c2b0908e62bc9ca8935d2","datavalue":{"value":{"text":"An undecidable problem for context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1067789$50FD5F30-C55F-459F-8B40-F96704CC76AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28256f8a183d49188925cf9a3aeb8c0832518a6d","datavalue":{"value":"0581.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067789$97C3F6CD-15C2-47E4-996B-10A2071A3E7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fbb846b1cf915e55d8417fba7b740db47fff119","datavalue":{"value":"10.1016/0020-0190(85)90081-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067789$D97E2F58-BC52-4E33-B839-BBC46AB57C69","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":"Q1067789$40413B52-4DC6-4CBD-B87A-2BAC08FECDF7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1067789$5CCECB0E-05C2-4E8C-A771-2FD800FF2C94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1c09324d43e41f413d38cfc7671457616d67b3d3","datavalue":{"value":"This note deals with the following problem: Let \\(G=(V,\\Sigma,P,S)\\) be a context-free grammar and let \\(h: \\Sigma\\) \\({}^*\\to \\Sigma^*_ 1\\) be a homomorphism. Are there distinct words v and w in L(G) such that \\(h(v)=h(w)?\\) It is shown that the problem is undecidable by reducing the ambiguity problem for context-free grammars to it.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067789$ADC4BD78-64D8-44A7-B17E-17B0221B80CB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067789$A7589A54-1DCC-4B6A-8153-53ACEAA51EE9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03a178e0815d7bf3f13df0b2c5ea7cac7ee3bf80","datavalue":{"value":"3930364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067789$2E9A36F6-F191-4857-A09E-CF709152F71D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067789$0C9D678A-4173-4418-9A03-768BBB81FDA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"940ee4d935a333d1740d34446ca9b672ac685808","datavalue":{"value":"left Szilard language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067789$0D3BE35B-5FB6-4F61-92CB-C0EDFFD51BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dece2b67a16f221be015e3ceddb4de928543fdd9","datavalue":{"value":"ambiguity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067789$7F467626-A315-485A-9E50-374A5F165722","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"294e1560b692bac1dd7a61f0104c714c0eb36374","datavalue":{"value":{"entity-type":"item","numeric-id":594603,"id":"Q594603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067789$36E5D814-CBAE-4D1E-837E-2061D465AF1A","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":"Q1067789$16CF6BE3-DCF3-4C0D-9F71-57052FFB0C76","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d996a816abd38109b90210d439b8ff3e8911ba62","datavalue":{"value":{"entity-type":"item","numeric-id":5592247,"id":"Q5592247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067789$2BE58078-77CD-4961-9A43-9CA3D3FFA583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4482a4cfdf60186d43e6c116d90cec57b6bdf53","datavalue":{"value":{"entity-type":"item","numeric-id":1253937,"id":"Q1253937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067789$A1868F96-4E77-4566-9314-00271326F8DB","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":"Q1067789$FD670399-10BA-461D-AFC6-A529C7C4B224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5acae39981c04bee67afb40be4d3b17e459e9d6","datavalue":{"value":{"entity-type":"item","numeric-id":5668008,"id":"Q5668008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067789$4F1E9FAF-D5E1-448E-A5E4-22E9456583CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d96da853402d962fc2ea8044a3acb16792aba716","datavalue":{"value":{"entity-type":"item","numeric-id":3315498,"id":"Q3315498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3183de9c5a02fe2c43884b5b8d8f1fe1b93e24b","datavalue":{"value":{"amount":"+0.90260094","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":"Q1067789$15C40144-E23A-4A34-9757-8535A17D0632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1ed6d3b3c4e117521de24f4626014fcc232fec0","datavalue":{"value":{"entity-type":"item","numeric-id":2729233,"id":"Q2729233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"467456976b094a2c9c4cbc7af3696c868afd9dab","datavalue":{"value":{"amount":"+0.89707816","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":"Q1067789$6C9F774D-3F5A-4B93-ABE1-9F0B67897AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22c1d0931c80c83aa0150f932a6812802d90185e","datavalue":{"value":{"entity-type":"item","numeric-id":5384531,"id":"Q5384531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b66cea90546a8424c7e06f86438048dd7ceb976","datavalue":{"value":{"amount":"+0.8952961","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":"Q1067789$4045FE67-B2C4-4810-BDC5-B047BF99877A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1f13ef25f16581cb3eaca03a613bd82df9d9547","datavalue":{"value":{"entity-type":"item","numeric-id":1318696,"id":"Q1318696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7c787cdc730509a5ad30a4e7b473d7b582742d5","datavalue":{"value":{"amount":"+0.8943292","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":"Q1067789$0925E7CD-6601-40A8-95D5-BCE10EC21F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5c662ca755656966bfc350f76a335dd4ee87da1","datavalue":{"value":{"entity-type":"item","numeric-id":5526126,"id":"Q5526126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28df6a0bbec3622d52cc511aa200a03a784ddbcc","datavalue":{"value":{"amount":"+0.8913181","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":"Q1067789$2C991C5C-94D3-4065-A3DB-4E8E76434D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea9f5f44b49c7406375f54094e53c018ceffac78","datavalue":{"value":{"entity-type":"item","numeric-id":2947427,"id":"Q2947427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1d7b30bcd5bd199de6950fa4c5a09f6e86acde","datavalue":{"value":{"amount":"+0.891048","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":"Q1067789$7DBCD654-6CD8-422B-AB37-CD2EC35E5E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85783b0432d08b11b10626bee1d443db50c19256","datavalue":{"value":{"entity-type":"item","numeric-id":1285581,"id":"Q1285581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a54688256a28025ec73b5da4de51c3000bb381d","datavalue":{"value":{"amount":"+0.8890152","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":"Q1067789$D2C951D1-319D-4EB8-9192-74B24E2F0B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"511ac0c67ae689e097d202562d1cf1627a6e936c","datavalue":{"value":{"entity-type":"item","numeric-id":1826642,"id":"Q1826642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e12c72dda5c361d442f05df2b57ebd3302d4d5b","datavalue":{"value":{"amount":"+0.8879512","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":"Q1067789$614A496A-39EE-482D-932A-4B67F97FC605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac0679d9018337dc02588f7ff6a9a6d70fd43075","datavalue":{"value":{"entity-type":"item","numeric-id":3704908,"id":"Q3704908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f5d1455f58ca019a9b2ff960d2fbce301decd36","datavalue":{"value":{"amount":"+0.8868196","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":"Q1067789$6E5E8061-44AA-4B4A-B249-FDA44B15B8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3cc2687e0704d1592d98eb993779e988d1643a7","datavalue":{"value":{"entity-type":"item","numeric-id":1099961,"id":"Q1099961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55d1ad918d74c89d8d3f6483af8f458b39aa3297","datavalue":{"value":{"amount":"+0.8831128","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":"Q1067789$E70FD370-8421-445E-BE31-4F0C153DB29C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An undecidable problem for context-free grammars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_undecidable_problem_for_context-free_grammars"}}}}}