{"entities":{"Q761043":{"pageid":762892,"ns":120,"title":"Item:Q761043","lastrevid":64170954,"modified":"2026-04-11T18:07:02Z","type":"item","id":"Q761043","labels":{"en":{"language":"en","value":"Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \\(\\sum ^ p_ 2\\)-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3887098"}},"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":"Q761043$3BE66942-4EF6-4E85-97D1-EE6EA4716467","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d74805e45127b059941f0773f324ce4fd04447f1","datavalue":{"value":{"text":"Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \\(\\sum ^ p_ 2\\)-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q761043$9008BFDE-C755-42DB-B337-05893F3FBF03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dfafac3a5f81f032f114f3c658c9017c5791a0a2","datavalue":{"value":"0556.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$8BA3293B-5679-427A-931D-6CB084466AC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b13ab914a2ec215a4e1688497c679190023f395","datavalue":{"value":"10.1016/0304-3975(84)90092-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$75BA3DE0-25FC-415A-BB83-5042C2738F27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f11d29d2cbdb03c4d5ff90d92cbc2f1d658ba97d","datavalue":{"value":{"entity-type":"item","numeric-id":391197,"id":"Q391197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$24513D6F-4A6E-4B2E-B164-2488038FD826","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":"Q761043$917555FD-0C08-4F58-B8E9-BC8C4A2A70E9","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":"Q761043$FEDAA251-9FD5-40D1-BAFF-93164DF253F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2145c0c6dede000a440f806388bdbd445f4382d1","datavalue":{"value":"This paper deals with the computational complexity of two fundamental decision problems for context-free grammars with 1-letter terminal alphabet, namely the membership and inequivalence problems. The main results of this paper are: (1) The membership problem is log-complete for NP, and (2) The inequivalence problem is log-complete for \\(\\sum^ p_ 2\\). In particular, the second result implies that the inequivalence problem for this restricted grammar class is in PSPACE, thereby setting an open question posed by \\textit{H. B. Hunt III}, \\textit{D. J. Rosenkrantz} and \\textit{T. G. Szymanski} [J. Comput. Syst. Sci. 12, 222-268 (1976; Zbl 0334.68044)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$DEC89019-67F2-4A3A-B3C4-EF05A11B79AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$D91ACD19-47E3-4010-9FB0-712ABA2E4849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$D4885C53-63A9-4ADD-9DCF-3C9BED90B777","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e9a5645b5b790f4488d1b18b1c0c3799762148f","datavalue":{"value":"3887098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$EE50CF9F-CE76-4D3C-A81E-676EF556D23B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f080b22ac194cf7585a56b63883129b1a17549b","datavalue":{"value":"equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$3747F78E-097C-4CB1-A3D2-1AA736790607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$491F2C18-5B35-41F4-B5EC-46918285515B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$FCD86E02-9127-4F90-8A8A-036D1A33AFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a37f1b310a3dab2e44459244c624b1e251e5b8cd","datavalue":{"value":"context-free grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$833F4DC7-B4FC-4E7D-B66C-53CDA682AB17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31e860314eeb1a93c1b93265a9c37508a478a501","datavalue":{"value":"membership","type":"string"},"datatype":"string"},"type":"statement","id":"Q761043$C92DE0A2-9477-43DE-9336-D0C6C11E36DA","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":"Q761043$8657DFE1-A3F7-4613-9330-66DD1FE44568","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f00ba72a8cfe122ea489419daa7b88f58f571d1e","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90092-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q761043$58026DD5-88B1-4D2D-8C7B-DEE3BCFDAA7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94d017fc7dee0c8266c430b81f85b8617b69b0d7","datavalue":{"value":"W2007431032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q761043$6629DB77-438A-432C-A5FD-802CEB49C2B5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2b0f4db04f9c75ea19ea5967c0becb3d0ef7a1f","datavalue":{"value":{"entity-type":"item","numeric-id":3888558,"id":"Q3888558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$DB68AEF4-A5A0-41EA-A185-00FD78E000DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fd1e28e0e6c158c9409c70c379bfcc7c9840573","datavalue":{"value":{"entity-type":"item","numeric-id":5576254,"id":"Q5576254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$E0BD4FDB-7E9F-4BA7-9FB5-BDDB82E82FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a9c390298575061fb02cd95521e7691f4fa7dd","datavalue":{"value":{"entity-type":"item","numeric-id":1229100,"id":"Q1229100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$804C8177-700E-430D-9811-B6B5710CDA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2f573592e98c5ac8ddf159206ff6c9481db65e","datavalue":{"value":{"entity-type":"item","numeric-id":3668872,"id":"Q3668872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$CBD4283D-9919-436A-9A7C-8403A6D26E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0bc9094e6e358075b2700764477392c7fd8596","datavalue":{"value":{"entity-type":"item","numeric-id":3327731,"id":"Q3327731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$792A8046-8B8C-4C27-82E2-30EA02D4C4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6306c16d86c9df313c4857802a7affd9c00f9d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1161303,"id":"Q1161303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$DD080E1E-2784-4738-91B6-0324FA68F637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5003f1b35a3d8f903232f84c855b80979eec5e4f","datavalue":{"value":{"entity-type":"item","numeric-id":3888985,"id":"Q3888985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$E5FF2610-D2D3-4D0A-8D23-EC41B2F60074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q761043$35F5C497-CA08-4552-ADE5-AD711DF12CCD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab0e37e7a6f12b919717b2aced35e921c2eaa478","datavalue":{"value":{"entity-type":"item","numeric-id":3736915,"id":"Q3736915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b44cfe2faab6274adff341a3b182ac71afbf73","datavalue":{"value":{"amount":"+0.8509847521781921","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":"Q761043$310B4F7D-114B-400A-BD05-CFC0751ACFA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02570c8b33858e2ce8de566c253f95005a6ed4be","datavalue":{"value":{"entity-type":"item","numeric-id":5246714,"id":"Q5246714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0b06ae1bdd4d0f79a41f60ca4514c48bb50c260","datavalue":{"value":{"amount":"+0.80653315782547","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":"Q761043$2BEA1853-9F57-4911-BB00-F451472530EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"283637a4ca02bfc23729ceb8922690475b470f7a","datavalue":{"value":{"entity-type":"item","numeric-id":4035344,"id":"Q4035344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c174f72d6648a89c8b9df7d182105f8eb85091c5","datavalue":{"value":{"amount":"+0.7849339246749878","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":"Q761043$E2556605-367E-49C5-AF04-86FC76094246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8794b9ba8c538c47a6165549457961f7c20cc8b1","datavalue":{"value":{"entity-type":"item","numeric-id":3025324,"id":"Q3025324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d8382c039ba58ad91265d6e26d03044a1747f04","datavalue":{"value":{"amount":"+0.7815200090408325","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":"Q761043$AA567B46-093E-47C2-ABC0-685C8A2F7F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3beb3b95133486297f3688707644b61c9e88053f","datavalue":{"value":{"entity-type":"item","numeric-id":3210903,"id":"Q3210903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6b02c9b80af787a8652884f5502427256951b9d","datavalue":{"value":{"amount":"+0.7785757780075073","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":"Q761043$A1B38100-9D0C-4DA2-B8A2-5B85683C35AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \\(\\sum ^ p 2\\)-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_the_inequivalence_of_context-free_grammars_with_1-letter_terminal_alphapet_is_%5C(%5Csum_%5E_p_2%5C)-complete"}}}}}