{"entities":{"Q2265818":{"pageid":2276561,"ns":120,"title":"Item:Q2265818","lastrevid":78536645,"modified":"2026-05-06T11:49:43Z","type":"item","id":"Q2265818","labels":{"en":{"language":"en","value":"A note on undercover relation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3892610"}},"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":"Q2265818$E1EA14BA-9394-49A1-8425-A9EF74885306","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d855f45ff79dbc82db8d503a3327155695377036","datavalue":{"value":{"text":"A note on undercover relation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2265818$A5812F78-6610-48BF-B4A3-3CC6265BBB64","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"77ee591e5406b43a6b8f74a12968875ea05d173b","datavalue":{"value":"0559.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2265818$542CBFC3-533F-4D27-98CC-19CB5D8ED3B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d90bffca9a9d227cf3633350300bcdae0fb90f21","datavalue":{"value":"10.1016/0020-0190(85)90124-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2265818$92D80E9E-99F6-4122-84BB-8CB95EFCE14E","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":"Q2265818$03B0050E-1407-4765-B024-37AD4780044D","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":"Q2265818$1C8F96D8-9671-48DD-9F40-CB87449D09A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0336171fc8df5a232ebfd77a1480b4868b60f698","datavalue":{"value":"The paper gives a new characterization of the undercover relation between context-free grammars [see \\textit{E. Soisalon-Soininen} and \\textit{D. Wood}, Acta Inf. 17, 435-449 (1982; Zbl 0478.68086) for definition and motivation] in the semi-Greibach normal form (with right hand members of rules of the form \\(b\\alpha\\), where b is a terminal symbol or it is empty and \\(\\alpha\\) is a string of nonterminals). Based on this characterization (which involves homomorphism equivalence problem) it is proved that it is decidable whether a context-free grammar \\(G_ 1\\) undercovers a context- free grammar \\(G_ 2\\) with respect to a homomorphism (both \\(G_ 1\\), \\(G_ 2\\) are in semi-Greibach normal form).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2265818$56D5BB6D-3AE1-4559-A7E2-3661F6883125","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2265818$E6BA3FEB-5EBC-42C9-AB5E-92EB6F44DE10","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36afed68be4f1efff8583524ed6ab03fd1881291","datavalue":{"value":"3892610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2265818$2DB55D53-50FC-4F6D-B2D9-35051324C90B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a37f1b310a3dab2e44459244c624b1e251e5b8cd","datavalue":{"value":"context-free grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q2265818$4D75323B-B036-4744-91E6-E5FA4915082B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3021bab1248edbda1db8812b613ad25e90fbe2aa","datavalue":{"value":"semi-Greibach normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q2265818$30372FC4-899A-494D-A610-6AC93EF37060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb032af3fb98ff28d75c95a613a6bf7c142b1c7c","datavalue":{"value":"homomorphism equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2265818$CE8E9A4C-35CC-413D-A75F-134CCF23BB67","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":"Q2265818$3F48C39C-1E11-4C14-81CF-FA2C725C04ED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"42210bafdd52b4cbc4a62733feb51d89cc3d12b1","datavalue":{"value":{"entity-type":"item","numeric-id":224640,"id":"Q224640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2265818$7E049254-2014-43DB-8669-6A5E541A10FE","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":"Q2265818$3FBA9FA6-F114-43E5-972C-6307186B94AE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3fc2155f60612489cdcb285520d228497f43e28","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90124-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q2265818$E3DDB926-9A38-4514-AD60-2BFA2A0A1DD9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"731b7fd75b0b9c46b7da2a6114c290b7ea75472f","datavalue":{"value":"W2019562812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2265818$79BF1CED-FD80-474D-8021-08CC1EE5A094","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb07ca89a63cc1d58eddbd66f8d974a65762099","datavalue":{"value":{"entity-type":"item","numeric-id":3673125,"id":"Q3673125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2265818$A12FA5FF-E59C-4814-8DC8-023C071FD9AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc01f3100301b38f61a7577d1472e11bbe79b2b","datavalue":{"value":{"entity-type":"item","numeric-id":1251076,"id":"Q1251076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2265818$7EB81E26-8148-4B95-927D-B013F257E247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d9dd414a6b3b2c58f60a1e339698f5282df1d1","datavalue":{"value":{"entity-type":"item","numeric-id":3912024,"id":"Q3912024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2265818$C22CC118-C12B-4F0E-82E6-7C9714EA1402","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":"Q2265818$4C4158DE-3975-4F55-BA99-734C62B00C59","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":"Q2265818$5527770D-DBCE-4BEE-9416-BB93A0B03346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6037e47808e7cf1e5ba087735173c7bba79de946","datavalue":{"value":{"entity-type":"item","numeric-id":1161309,"id":"Q1161309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2265818$71FBFEC4-1AFF-4246-8582-2609253B42B0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58f240438914048ece46cad1326c0f21dcc51a3b","datavalue":{"value":{"entity-type":"item","numeric-id":1575735,"id":"Q1575735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb6de6bdfbac4f9cf57f650ef76961e15c72c123","datavalue":{"value":{"amount":"+0.75182986","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":"Q2265818$4E3301B5-4E12-4706-8F0B-16F71DDC2E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb238b74db41ea4e888cff0215088d4cf9b12abe","datavalue":{"value":{"entity-type":"item","numeric-id":4822063,"id":"Q4822063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17c580cb95737c1cb22d46cc0d1633506794b9d8","datavalue":{"value":{"amount":"+0.7457622","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":"Q2265818$52EA8F6D-0ECB-4F54-9C77-684579B6B4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc69c9d6e5a527c0b2d6333f68ea677be53f86f3","datavalue":{"value":{"entity-type":"item","numeric-id":4845167,"id":"Q4845167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ad058782a08e0d8e5a2649fa79db72314ed7cb9","datavalue":{"value":{"amount":"+0.7234432","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":"Q2265818$2D987348-9EBF-4D75-99C4-A363F22A4784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72803d10de90d70bc54ee46fc74489f9c397930e","datavalue":{"value":{"entity-type":"item","numeric-id":3683168,"id":"Q3683168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71be292484f6cf7d4b3f714c8051a1a32e35af70","datavalue":{"value":{"amount":"+0.7225495","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":"Q2265818$8184E2C8-04C5-4829-B9EF-F33283401FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa5f7f41f0c40c44de18ff863a3561e1fedeb60d","datavalue":{"value":{"entity-type":"item","numeric-id":5689005,"id":"Q5689005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70248e42fde40ce38acff2edda8c865986d93388","datavalue":{"value":{"amount":"+0.7153142","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":"Q2265818$D9A97E74-A6BE-4A24-9894-675E88603685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9375463da5194ba40ed29815f62f78c7380055a","datavalue":{"value":{"entity-type":"item","numeric-id":6173114,"id":"Q6173114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed96908cace33aa48314e59a46ef17f257390d3","datavalue":{"value":{"amount":"+0.7130148","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":"Q2265818$E1B43131-0358-4421-B51C-9E975F29A1E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71423efb49ed24b262b5dd9ce1420ed02213c8fb","datavalue":{"value":{"entity-type":"item","numeric-id":1945508,"id":"Q1945508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"673b47692e0d5251ffd211f05ac0916ac03821c8","datavalue":{"value":{"amount":"+0.71248156","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":"Q2265818$D8A10ADE-4C91-4E26-8D69-F33658798104","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on undercover relation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_undercover_relation"}}}}}