{"entities":{"Q1872711":{"pageid":1883453,"ns":120,"title":"Item:Q1872711","lastrevid":73831116,"modified":"2026-04-14T17:25:15Z","type":"item","id":"Q1872711","labels":{"en":{"language":"en","value":"Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1910841"}},"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":"Q1872711$E55B225F-4967-43D3-B038-7C169A3518CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb5e22a547d68113eb4b66f08398420b57b60652","datavalue":{"value":{"text":"Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1872711$C1DC135C-C42E-4A62-966E-8086F4AB5BF0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6f01c16a1ac0b5a3dceeaf1dcfd479efbbdbcb1","datavalue":{"value":"1059.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$ACDF767F-322A-492A-8516-C16DEB27E318","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f920db5aff0a8e6518a5a866c3161192fca7ec8","datavalue":{"value":{"entity-type":"item","numeric-id":383364,"id":"Q383364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$8DB4C89D-E501-4E4E-A80F-CEC4A54BA9C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$2B3EB863-CE6A-4F1C-85AF-4D808AD431D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"022e09a763cee1618c51c8e037cdf2557e0134f9","datavalue":{"value":{"entity-type":"item","numeric-id":161496,"id":"Q161496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$E2651C11-46D4-4928-B1B5-BA837D3C65F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$FF327607-A581-4736-B265-A62DEAD3E159","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2739d9d5887c2ab5a6b70df0e9f5c64b00eb7649","datavalue":{"value":{"time":"+2003-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1872711$EE81666B-3F66-4DCE-BDFE-A14505E265A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1ace01541a2c43998f49bc5140cef6b81ecbb918","datavalue":{"value":"https://semanticscholar.org/paper/b3c2089671067248430081472e527cccceeff260","type":"string"},"datatype":"url"},"type":"statement","id":"Q1872711$DFAF17D6-CF62-4978-81A9-46699F8A8C95","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$BCAF93C1-1BD2-4562-986F-1184DDD17F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$F088F68E-B0BA-46F5-833E-B5249625C57F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"48b13e747119a82daa6c87d4856e202ce9e568f7","datavalue":{"value":"1910841","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$E3B5CA45-4F12-46F4-B758-E9548141439D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872711$D0B8CC72-482F-435E-92E0-2B8BDAF3AF27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a37f1b310a3dab2e44459244c624b1e251e5b8cd","datavalue":{"value":"context-free grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872711$534C4B07-0E3D-4DD5-98CC-03782310BAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"456c672ca15cab74651e643baa7549046be81ae8","datavalue":{"value":"pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872711$E2F41F66-1ABB-463F-957C-651D7E903C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872711$55C31637-F081-44DD-ABF9-C72C6C29A344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"360ce5548a836a8df91ecff2eb34451d31610cac","datavalue":{"value":"space complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1872711$6C2C1E1C-7DAA-4666-9B13-0EEB51FE76FC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a74aceb953304131fc4c55a1b05f00cb63a8d602","datavalue":{"value":"Q61677528","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$938E481C-6339-4696-B1E8-3B2A6F9B7C91","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c007ae1867363f659c11dfe2e26b294ddb7e58e3","datavalue":{"value":{"entity-type":"item","numeric-id":33608,"id":"Q33608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$39893F4C-BEA4-4A98-8840-525BD86123C2","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":"Q1872711$F4250117-4E18-4883-A2E8-746A07FCF830","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"426d105943b10f31117570c0a53045a9ceabd0ec","datavalue":{"value":"W2057559629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$DFC6B7C7-4378-48A9-9B3E-3AB45D1C270D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f9c22b32b28aec38b3413d783efe6c67d7e1b6c","datavalue":{"value":{"entity-type":"item","numeric-id":3692869,"id":"Q3692869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$E2A6E463-F572-4553-98CC-D44FD9DE3DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a09ad45c310ccddabe10568a0ab5d8e2fa77be68","datavalue":{"value":{"entity-type":"item","numeric-id":3569021,"id":"Q3569021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$3DF2CB34-6DE2-4F2A-8E3F-7BCB454A72D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf644e8390ad5ec80700e836eed2adcf916636c","datavalue":{"value":{"entity-type":"item","numeric-id":920131,"id":"Q920131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$8B5128CA-A83C-4473-8D0C-CA035E06ACB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"531e0f5bfec384860107a076da6829ba8057ed0c","datavalue":{"value":{"entity-type":"item","numeric-id":4131653,"id":"Q4131653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$66EC7DAC-94C7-4E3E-B3EB-A0BD4988575C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39633f85c3f59cbfb465de8b6af9611f965045f2","datavalue":{"value":{"entity-type":"item","numeric-id":5840342,"id":"Q5840342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$9D459554-BE7A-4F85-968A-D7A99B37495D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972ff908209cbae1dc0a10a9462932031345a6a7","datavalue":{"value":{"entity-type":"item","numeric-id":1099644,"id":"Q1099644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$FC43211D-42A0-4DBE-80A1-E949DA07DF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ba47561f2bd8cdebbeac2403bbe522ea9faeaa2","datavalue":{"value":{"entity-type":"item","numeric-id":3774982,"id":"Q3774982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$428E4C36-D4AC-4AB0-9891-CBAACFBCB9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cea6d2ab79d3ca908a76dfbaf32a69dccd1e2412","datavalue":{"value":{"entity-type":"item","numeric-id":4037687,"id":"Q4037687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$60ACFDF4-26E5-4AF1-9AE0-519C98C93C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc5f17664ccdc92ae0309d18ea708585665856bd","datavalue":{"value":{"entity-type":"item","numeric-id":1271619,"id":"Q1271619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$893506E2-AA34-4379-937B-DF13CDDBC2AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cde51209d4a7cf2800f173ac80551646e84b5432","datavalue":{"value":{"entity-type":"item","numeric-id":4210151,"id":"Q4210151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$D4E7EBDE-32B1-4EF1-BCAA-760F4ACA8C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d5da18e900c147617e86ef7a75eeb280395a0aa","datavalue":{"value":{"entity-type":"item","numeric-id":5543072,"id":"Q5543072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$9C0991B7-E1D5-49C3-AB0D-4AA4BE1DB08E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a3937da7c4f68748dbeb886cf8ab8244d102dc5","datavalue":{"value":{"entity-type":"item","numeric-id":1165026,"id":"Q1165026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$4A76CA8A-AC87-4B05-A3A1-187A0D91B059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66856e28a8d065ae00cc1eb109ee4001e24e8421","datavalue":{"value":{"entity-type":"item","numeric-id":5582355,"id":"Q5582355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$44D1B0E5-63BB-40E3-86DC-02ED8104128E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bb26cb01dbf8dbc1346e89d38ef4b617f99f8c","datavalue":{"value":{"entity-type":"item","numeric-id":4506483,"id":"Q4506483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$4B593D21-6202-4E15-96D9-700046592986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c878969fc0647d5cfbe428295cd2bd16425fb44","datavalue":{"value":{"entity-type":"item","numeric-id":4266534,"id":"Q4266534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$3BEBED2F-5AA1-456C-BD7A-34F60F8B96E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ecab129758dec7fa4d1bf496b55bc23be81f779","datavalue":{"value":{"entity-type":"item","numeric-id":5534218,"id":"Q5534218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$F2162BD1-D93C-4C6E-AF3F-19E3C76A8378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b17ea6ba4e4429ffb05cb421d82f8ab4f37ea19a","datavalue":{"value":{"entity-type":"item","numeric-id":2719119,"id":"Q2719119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$85E57FEC-B84F-40C7-98CE-7CDFF2954ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d46d53aaa78e4e1f3286eef514e163c5ea4ffb6","datavalue":{"value":{"entity-type":"item","numeric-id":5534924,"id":"Q5534924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$8499EAA4-9799-4334-B4FC-B29F8743D715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8c91f3e531d0087256bd01284f860adad823be3","datavalue":{"value":{"entity-type":"item","numeric-id":3021944,"id":"Q3021944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$04F80299-DBE4-4EFA-9D42-3FADA5E41585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a423bed1db1f89dfd75f51e2dddb86d00ac7188b","datavalue":{"value":{"entity-type":"item","numeric-id":1816738,"id":"Q1816738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$91492908-E22B-4FA6-AC1C-CE67041A8E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47d753588d3e15901e017390d393815c34f9ede","datavalue":{"value":{"entity-type":"item","numeric-id":5636862,"id":"Q5636862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$1CBBD6A0-B162-4786-A873-3BDEE24D0899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59636d489c0bc0f5fc3f2682ef3049e5016b4f4c","datavalue":{"value":{"entity-type":"item","numeric-id":3777484,"id":"Q3777484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1872711$2D60262A-847F-43EC-AF9E-25B5A78D9860","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"e3a73652839e0d76f71665679487dabed1cc0bb9","datavalue":{"value":"journals/jcss/PighizziniSW02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$E47FA523-076C-4A6A-A251-0DE5B805A773","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35810015702c21a722e9ba159ad8e1b5402ce9ac","datavalue":{"value":"10.1006/JCSS.2002.1855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1872711$61249791-D6EE-4E54-9D1B-D2C291935866","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9422c1b5317329a36cb4e58bdd4ca63ae17a73e","datavalue":{"value":{"entity-type":"item","numeric-id":4536396,"id":"Q4536396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7dc33625064298a082ac0ba7c84188426be03b6","datavalue":{"value":{"amount":"+0.96037358045578","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":"Q1872711$ED9FBE2A-71F7-4F65-AFCC-B8B4905FC710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6abf6cea898a80b0b21b70709d2541fe76caf338","datavalue":{"value":{"entity-type":"item","numeric-id":3395134,"id":"Q3395134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"249b7eb3d285b4a745501ab741baccb9a2b159e6","datavalue":{"value":{"amount":"+0.845835268497467","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":"Q1872711$075947CD-7CDE-4E60-83CB-5C60E610F1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3b76d2e4c5b18eef2944a4147d205dd092feb78","datavalue":{"value":{"entity-type":"item","numeric-id":3602818,"id":"Q3602818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed222733ce65c45c43b3165dbb3c6d7314065eaa","datavalue":{"value":{"amount":"+0.8447779417037964","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":"Q1872711$BC87D849-6B11-4853-A492-EAA83E4A7AC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eeb435dec36f27243e72b2425ff31711c6f2f99","datavalue":{"value":{"entity-type":"item","numeric-id":5915989,"id":"Q5915989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f728505658d45417b2031737d810d691f5b60bf4","datavalue":{"value":{"amount":"+0.801166296005249","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":"Q1872711$1E7403EF-CCEE-48CC-857B-DCBE506E3A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d8d4863b351282ec09c56eb20e3eabd08ead170","datavalue":{"value":{"entity-type":"item","numeric-id":5744124,"id":"Q5744124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bf7b378d4292cb54a3110d022e0ac53411d91c9","datavalue":{"value":{"amount":"+0.8004099726676941","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":"Q1872711$EF93B772-EE6C-42CB-A377-7AD3F8D6AE19","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Unary_context-free_grammars_and_pushdown_automata,_descriptional_complexity_and_auxiliary_space_lower_bounds."}}}}}