{"entities":{"Q1176482":{"pageid":1187231,"ns":120,"title":"Item:Q1176482","lastrevid":69805350,"modified":"2026-04-13T09:31:06Z","type":"item","id":"Q1176482","labels":{"en":{"language":"en","value":"On the power of cooperation: A regular representation of recursively enumerable languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 12015"}},"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":"Q1176482$922B3B1A-51FB-4B32-8D62-0228432067E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cabb76c3d5da1024d45c4b2962869f15e874ab53","datavalue":{"value":{"text":"On the power of cooperation: A regular representation of recursively enumerable languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1176482$0AEC16C2-46AE-44F3-A63B-2ED2A50E0C74","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a00a07e8cde80b85edc27be633233558873ae713","datavalue":{"value":"0742.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$3DB50698-C407-4E91-ACAA-ED2C9B7D1B8D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af66e7f0286e359aa5903e03bcd9b76df41daca6","datavalue":{"value":"10.1016/0304-3975(91)90198-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$C42E7D0A-7927-46E6-A3D0-CAB5210DEA87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a28007afb406a64cc0b4ef3a3bf49da90b49296a","datavalue":{"value":{"entity-type":"item","numeric-id":387870,"id":"Q387870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$72F149E4-114B-42AA-A100-212C3158B4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"21f68ee0157c7567a978f1e208660455183553ab","datavalue":{"value":{"entity-type":"item","numeric-id":700788,"id":"Q700788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$B4E8FF5A-97F5-4058-B541-86ED91E9A87D","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":"Q1176482$F2A280B4-D590-4444-9D94-508D33D99086","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1176482$B3CE52E1-7F6D-41FA-B4F8-2197B00FFC17","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97bd2ec8db233965e5bb9604e51fbc2bf6b0b36d","datavalue":{"value":"A cooperating distributed grammar system (CDGS), as introduced by \\textit{E. Csuhaj-Varju} and \\textit{J. Dassow} [J. Inform. Process. Cybern. EIK 26, 49-63 (1990)] is a construct \\(\\gamma=(N,T,G_ 1,\\dots\\), \\(G_ n,S)\\), where \\(N\\), \\(T\\) are nonterminal and terminal vocabularies, \\(S\\in N\\) and \\(G_ i=(N_ i,T_ i,S_ i,P_ i)\\) are grammars with \\(N_ i\\subseteq N\\), \\(T_ i\\subseteq N\\cup T\\), \\(1\\leq i\\leq n\\), \\(S=S_ i\\) for some \\(i\\). The derivation starts from \\(S\\); the components of \\(\\gamma\\) work in turn, every enabled component rewrites the current sentential form as long as it can. The paper proves that every recursively enumerable language can be generated by a CDGS with two components, which are in fact conditional regular grammars, with condition strings of length at most two (a conditional rule has the form \\(w: A\\to x\\), with \\(w\\) a string and \\(A\\to x\\) a usual rewriting rule; \\(A\\to x\\) is used for rewriting only strings containing \\(w\\) as a substring). The proof is based on a characterization of recursively enumerable languages by \\textit{V. Geffert} [Theor. Comput. Sci. 62, 235-249 (1988)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176482$921B15BC-0464-4461-A33F-EB0C1A5FA56E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$D8CC04BD-89F0-4E25-B2FC-C8658371A401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$6ACC9A6A-B624-4AB1-81C1-1179A5905506","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5713e819e9a0e5ec0b83e399fc42bcd9c06fca32","datavalue":{"value":"12015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$3AEB5597-1081-4493-BF53-C89A63AC0764","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3bc6a8f5cc0559d5656f56ad8b52a35ba019dad","datavalue":{"value":"cooperating distributed grammar system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176482$F2B4F0CC-45B7-46D6-ADC4-723BFD0AD904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a7194f2bde644b9412ba0132204cc06b743f3e","datavalue":{"value":"recursively enumerable language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176482$5CB20367-F11D-4143-8F5D-CEC540311099","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":"Q1176482$BC91710F-1247-4EB1-ACEF-4A74C05CD8BE","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":"Q1176482$91FA5787-A190-4FCC-AD03-267320DC9B4F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebe5020d9546d4b04cded0ac354227eeaa45a524","datavalue":{"value":{"entity-type":"item","numeric-id":3468618,"id":"Q3468618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$6D3C4CEF-A10E-4FB0-A06D-76B674213FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9883685f8982ef7217af2959a8ae7553faf80889","datavalue":{"value":{"entity-type":"item","numeric-id":3751035,"id":"Q3751035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$13784E21-9E45-4766-85C2-726BE4E92E86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aadd908968f4f32b501eceed32996fa750a079f0","datavalue":{"value":{"entity-type":"item","numeric-id":1115633,"id":"Q1115633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$29FD52A2-13E6-4AF7-A8A1-AAD91ADEF683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f68c90bf618447f850acaab558df28a22be37f1","datavalue":{"value":{"entity-type":"item","numeric-id":5545960,"id":"Q5545960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$05699F82-8DC2-4CA0-8582-7E840BD3E6CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56a55d56820572fc5c82ca5136ab453a27b93de","datavalue":{"value":{"entity-type":"item","numeric-id":3690243,"id":"Q3690243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$D6D5175E-AE67-4E15-B325-1EBA9576BBFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aabbaa380d322784947d158eb60fa8672c2599bc","datavalue":{"value":{"entity-type":"item","numeric-id":1072714,"id":"Q1072714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$D6068866-2E06-4CCA-9290-FACAFCFCAEB3","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":"Q1176482$352C2669-6D85-4AE5-835A-C9BC68CDF0C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adbe91530be035fef056fbdd9d9e8d6f8ff21331","datavalue":{"value":{"entity-type":"item","numeric-id":4133165,"id":"Q4133165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176482$08635D17-5BFF-4F94-A9EC-31B20A87834B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d39896341f0385e52d17720d1181daca75b725d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90198-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q1176482$D0B914B3-0286-4A5F-99A0-B2986F2D611A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa11675a3ae3f5444f761248cbeef0f0a6ff7a21","datavalue":{"value":"W2072965782","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176482$EC40F367-0912-4FF1-B26E-6A4D7AA8A93E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5a4c1a209e49c7ac210eb4c461816b48b9112d2","datavalue":{"value":{"entity-type":"item","numeric-id":3526534,"id":"Q3526534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d63a3f82c58f6ad187c34dee16dab4e4a705e83","datavalue":{"value":{"amount":"+0.843780517578125","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":"Q1176482$B6CC5BF4-58E9-42B9-A7B1-8AF7EC9A895B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2410e1318e32979b7368347be84e400e45a6e27d","datavalue":{"value":{"entity-type":"item","numeric-id":3009338,"id":"Q3009338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170e3f5912b896dfa20abebfc105a5257a450339","datavalue":{"value":{"amount":"+0.8286699652671814","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":"Q1176482$9C0B34E4-2D8E-450F-A478-6981E4B05D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d19d6e58189878978084a1ea2e4a8bcca5b31396","datavalue":{"value":{"entity-type":"item","numeric-id":5711978,"id":"Q5711978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c7ea995a1212d2ab6f59fb2e718482d8bc89353","datavalue":{"value":{"amount":"+0.8212544322013855","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":"Q1176482$BD5BFF89-DA74-4159-8FC1-B198E8E1E484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b214a5f7704ac08a5f52b35cdeeacb0228863024","datavalue":{"value":{"entity-type":"item","numeric-id":4296539,"id":"Q4296539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e75a92f979eb8bf3f27d742729f075483a1faa0f","datavalue":{"value":{"amount":"+0.8211976289749146","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":"Q1176482$AB9A72C3-033A-40F7-B09D-8F700C45938B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aea2bb9774932366e6771d740165cecf685a77fd","datavalue":{"value":{"entity-type":"item","numeric-id":4939186,"id":"Q4939186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36ff3b49e9a2f28d5bb6731b2e228612d891c8da","datavalue":{"value":{"amount":"+0.8132091760635376","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":"Q1176482$E8A24494-FDA0-42D3-A641-EBBFBC5613CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the power of cooperation: A regular representation of recursively enumerable languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_power_of_cooperation:_A_regular_representation_of_recursively_enumerable_languages"}}}}}