{"entities":{"Q1178713":{"pageid":1189462,"ns":120,"title":"Item:Q1178713","lastrevid":66511974,"modified":"2026-04-12T10:34:38Z","type":"item","id":"Q1178713","labels":{"en":{"language":"en","value":"The complexity of computing the number of strings of given length in context-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 22298"}},"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":"Q1178713$0810D104-70CC-497A-82EF-199AB180C3FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b010cdded128114d3c2b60c302f239bf75e407da","datavalue":{"value":{"text":"The complexity of computing the number of strings of given length in context-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178713$F90E728A-D6D7-4A47-B897-FC9D42EEAC23","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a999901a54a63ad33b936c082b53b4b5c5677a4","datavalue":{"value":"0744.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$06C69811-AD48-4548-AAA7-705975D433FE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8712cb878b9d769d58dc2d3ac1be740d5e4ae2d3","datavalue":{"value":"10.1016/0304-3975(91)90023-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$E75FB37B-28AD-4899-9174-890BFE2922EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8771b95719f75a612917e1582dccec9f6e42d828","datavalue":{"value":{"entity-type":"item","numeric-id":590572,"id":"Q590572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$737CD33D-A24C-4856-A444-FA1E09DDF70B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"224a23009a193bc3927d2cbe6ef26b7ecad1c0b0","datavalue":{"value":{"entity-type":"item","numeric-id":288797,"id":"Q288797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$C1EC19D7-8C75-4262-9BAC-85133558CC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2847574c30343fdecd36c344bf1a822e45de0efc","datavalue":{"value":{"entity-type":"item","numeric-id":633809,"id":"Q633809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$9ABFDC6E-3042-4B4B-9C32-073151BC156C","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":"Q1178713$734F9A0B-DEE1-4FD2-AEAB-5D1869C7C0EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178713$D112A25E-0024-4967-BED8-A0A9A610750E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a75d3a9dc3d19d6906bab98f24be2eb358a0af20","datavalue":{"value":"For a context-free language \\(L\\), \\(f_ L(1^ n)\\) denotes the number of strings of length \\(n\\) belonging to \\(L\\). The counting function \\(f_ L\\) is used to study the inherent ambiguity of the context-free languages and to solve enumeration problems.   The paper concerns with the complexity of computing of the counting function \\(f_ L\\). The main result is proven in the second section and it claims that if \\(L\\) is an unambiguous context-free language then \\(f_ L\\) can be computed by a log-space uniform family of Boolean circuits with depth \\(O(\\log n\\log\\log n)\\) and polynomial size. The third and the fourth sections study the complexity of computing of the function \\(f_ L\\) by counting Turing machines. In the last section is defined a language of ambiguity degree two for that the counting function \\(f_ L\\) is \\(\\# P_ 1\\)-complete (\\(\\# P_ 1\\) is the class of all functions \\(f: \\{1\\}^*\\to N\\) countable in polynomial time by a counting Turing machine).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178713$DB43F786-33E9-4E78-A431-35FE5361E232","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$A92A18DD-B67F-49EC-BBB5-DA998CEE6193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$345B7DC6-5D8A-4495-B01A-C73A932A2CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$EF530CE9-7B7D-4EAD-94BB-54A1E42E6FF8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83c8fc1516863c90bbcb1cdbe2c7f117778e9b91","datavalue":{"value":"22298","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178713$B1A5A6D3-0E7B-4B21-BD00-B8C9DD6375DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8eac482325f942ac24416b01debdfa48130a4f52","datavalue":{"value":"counting function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178713$C29178DE-A978-4448-8595-A450B09B228D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178713$7E483EA4-B781-41CF-A481-469FDB933BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27e6e09513785012bac6ffe36f1fb5c5bf2b61ef","datavalue":{"value":"counting Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178713$0D4FBD44-FDDF-4F45-9E8E-0DFEC92CA047","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$75A2B725-B803-4503-B0C8-4248882A117C","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":"Q1178713$7227E18B-4F9C-4A96-972A-D807F5D134CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0961e1bf557788d0c4648b248ad3ad7446a80773","datavalue":{"value":{"entity-type":"item","numeric-id":3939260,"id":"Q3939260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$28E93915-26CE-4842-A756-3675680314C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33d0aad367cf52891c508c7e7bfb594600ba61f8","datavalue":{"value":{"entity-type":"item","numeric-id":3756526,"id":"Q3756526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$6027EF6C-1A61-4312-BC4C-98EFDE46AAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c7a78759148ce6b1abced42ef4a952f4334dd8","datavalue":{"value":{"entity-type":"item","numeric-id":794429,"id":"Q794429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$0D04E1A4-3D98-49D1-82A8-44A29C6DAD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86a79bfcfca810fb7601492bd0551fae9de8408","datavalue":{"value":{"entity-type":"item","numeric-id":4142697,"id":"Q4142697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$15CC63DD-D34E-434C-A0CE-AA352068672F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f085485e905c29559ec1f7dcaeebaba8980bca2","datavalue":{"value":{"entity-type":"item","numeric-id":5556574,"id":"Q5556574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$0F40AAFF-68D9-4F40-9B98-E17806D05654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9266185c52f53bc308d9e6b943b26d08e91281f9","datavalue":{"value":{"entity-type":"item","numeric-id":5526125,"id":"Q5526125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$9E8DC6B3-E37C-4686-8BCA-0B946DBC0383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c0bf79d428c740c926b5e2a478863e688bf48a","datavalue":{"value":{"entity-type":"item","numeric-id":2530258,"id":"Q2530258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$C248FCFA-4FD8-4081-9C61-EDD1301FC670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a006907d50546bdc051c28c96b89ad928a5269a5","datavalue":{"value":{"entity-type":"item","numeric-id":1158753,"id":"Q1158753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$14FF1A43-D402-4715-BA15-45ED39969D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$2F0541A4-D9DD-4D8A-BEC4-13B1CE28ABC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e19a7bbe89e3bc7087ddf9bca14fb529a05e318d","datavalue":{"value":{"entity-type":"item","numeric-id":2555869,"id":"Q2555869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$4477C921-6EBF-4F67-8B14-3EA2DAEAFA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e4040ef6147267f97b1df2717be3094d14f27a5","datavalue":{"value":{"entity-type":"item","numeric-id":3050453,"id":"Q3050453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$D160FC4B-2478-4043-B64B-929514A07162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0642debceda2905f287b21afe2a13ae05e6223c7","datavalue":{"value":{"entity-type":"item","numeric-id":1348529,"id":"Q1348529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$0DA702B1-4D99-4903-AF53-04C13EF9438A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14a5daa21b37759208aa92913b967f7f707992fc","datavalue":{"value":{"entity-type":"item","numeric-id":1088414,"id":"Q1088414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$5E6A5709-971F-4E20-88FC-CECFF95E6D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bcaf193795e4a1bbc7f8a3f4b3efd01642347a6","datavalue":{"value":{"entity-type":"item","numeric-id":1259601,"id":"Q1259601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$0079C282-FFD2-4783-939A-044D49A1DB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abbeb3bba30baba223f9809b105566586fcf2db8","datavalue":{"value":{"entity-type":"item","numeric-id":5583856,"id":"Q5583856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$24EDF9AB-4019-4010-891A-48A3B4E2BE1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91437bc3f5649edc6a7acb3095e2cdec844eb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":3711749,"id":"Q3711749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$7223564A-9102-4D54-B474-851D31A31109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$69061F9A-39A5-4380-8229-6E99238DA3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c7cefed39e417a6d9b231525fcb81d6bcfb79a2","datavalue":{"value":{"entity-type":"item","numeric-id":5601350,"id":"Q5601350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$807CA7D4-B70E-44B0-9740-8EE62FEF0B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eae71a3ecbfb51c64b6cb74916adde5cfba1e78","datavalue":{"value":{"entity-type":"item","numeric-id":2543982,"id":"Q2543982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$0673656C-577A-44CB-B6AB-7F596BD720CD","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":"Q1178713$5C865B98-DDE7-4885-A1C1-2A86385BCAF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0d1fb4e177bc1d0a6797a5e32e81051d24fed3","datavalue":{"value":{"entity-type":"item","numeric-id":3750999,"id":"Q3750999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$4F511C76-6899-4635-BE96-F91B482BCE15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$882F3AB5-0713-4C65-BE47-2EEDBC911E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb6290412741acf231ec58be371ffd9c5ecc534","datavalue":{"value":{"entity-type":"item","numeric-id":4155837,"id":"Q4155837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$4D622394-6852-4A09-BC4D-7D8F41DBF7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d864ecf0887e3285d5a657ecba76076407dae52","datavalue":{"value":{"entity-type":"item","numeric-id":2548172,"id":"Q2548172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$E4ED4267-84B2-4777-BF72-8ED7172235C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9340557a529a7c57bb8d8cf8fa6db1c140220a0b","datavalue":{"value":{"entity-type":"item","numeric-id":5626549,"id":"Q5626549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$EB337261-D092-47AF-83EA-5F4FA0248936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b615863cbfd4128debee77681eb7ea5577ce21","datavalue":{"value":{"entity-type":"item","numeric-id":5735559,"id":"Q5735559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$9A3FF7D3-3BBD-4AA9-B6C5-F84E38C90AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$6313876D-390E-4BA7-94CA-02629A25E532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$2C1C2B4B-71B2-4AA3-8330-20D4BF69CE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a25070aa6b2bfe19dc398e052b4e7395286998c4","datavalue":{"value":{"entity-type":"item","numeric-id":3795617,"id":"Q3795617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$6118E976-D272-45A9-AC2E-AFE6354BCBCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8624ac8b08c43bff2290ca70392ccbd3bba72141","datavalue":{"value":{"entity-type":"item","numeric-id":3762226,"id":"Q3762226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178713$5881CA16-57F2-40DE-B694-00FD673DE36E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cca5a7e7df70847449d44596d8347029ad4c4a0","datavalue":{"value":{"entity-type":"item","numeric-id":3773366,"id":"Q3773366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e469f7ba859d05dd278300fd2f4b8dc5af077b7","datavalue":{"value":{"amount":"+0.8994730114936829","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":"Q1178713$399D5452-4A45-41E1-98EA-1A62077F696B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"730b3bf249461a1dbe1cb5b249358a6e5e7c90e2","datavalue":{"value":{"entity-type":"item","numeric-id":3517096,"id":"Q3517096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7144f9914135d5766da13e2ea7162ab47af59b61","datavalue":{"value":{"amount":"+0.8154172897338867","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":"Q1178713$913A325B-9EF1-4430-B270-8C463206331B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b7b4bf3f90c723696c7ff93dd86d80af82720b","datavalue":{"value":{"entity-type":"item","numeric-id":1088414,"id":"Q1088414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1a52761b217162fce0a9ceddbcb486e678f0516","datavalue":{"value":{"amount":"+0.8053222298622131","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":"Q1178713$CCCB7494-D361-46E6-8F44-AB55EC12417F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4c3236964a5beada385d2910c9fe5635e8a6b74","datavalue":{"value":{"entity-type":"item","numeric-id":2490812,"id":"Q2490812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de7615925ed8c13e7305b0756f1d26eaf9a2d6bb","datavalue":{"value":{"amount":"+0.7946085929870605","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":"Q1178713$9EDD0E3D-CD2C-4411-8FB2-1510ECAD8765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b1ffe7ec10943c1e899b79e860f7480a1d29704","datavalue":{"value":{"entity-type":"item","numeric-id":1622992,"id":"Q1622992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce360fd0fb76c79e288f5e259d57797ec3a3c0ac","datavalue":{"value":{"amount":"+0.7931044697761536","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":"Q1178713$FAB0DF58-0105-48D6-AECA-1D62A4FAEADF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of computing the number of strings of given length in context-free languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_computing_the_number_of_strings_of_given_length_in_context-free_languages"}}}}}