{"entities":{"Q1198017":{"pageid":1208766,"ns":120,"title":"Item:Q1198017","lastrevid":66846930,"modified":"2026-04-12T13:15:20Z","type":"item","id":"Q1198017","labels":{"en":{"language":"en","value":"A lower bound for the nondeterministic space complexity of context-free recognition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92087"}},"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":"Q1198017$9E291A48-92D2-4BEB-83E9-A7B5A055191B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d00e92f4ec47907d348819c059fd242bcfc56b6b","datavalue":{"value":{"text":"A lower bound for the nondeterministic space complexity of context-free recognition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198017$EB217F3B-59A7-4442-B0F4-D15497AA5394","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f3b07de2e65bcfa2301fbb7cbe562ce6d389fe8","datavalue":{"value":"0780.68081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$943B6F9E-8072-4C13-964E-3170ED64E03C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d05d9e17ae44bd28ed7ee2a156518383790b9172","datavalue":{"value":"10.1016/0020-0190(92)90127-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$BB614171-853C-4542-9542-09F5E2635ECD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3336a40cc821600c2cc57c5ef4dc532be5780cea","datavalue":{"value":{"entity-type":"item","numeric-id":442278,"id":"Q442278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$0911B78F-105F-4EDC-8983-438D576D6878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f2bc7106f436b3e95136cb7027e49039db559e","datavalue":{"value":{"entity-type":"item","numeric-id":270030,"id":"Q270030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$5FF476AD-9948-463D-BC73-F030B94D1472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f012196ada22b97d9d00d44b6a51141308e0402","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$8A9C9D4D-F0FB-40C6-8BAF-6D790DA3DC64","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":"Q1198017$3F690330-3945-4EC6-BE0F-E0C1E4BBC93D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198017$741B5DBC-DE7D-4767-AF44-1CA9543BD682","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$0165F36B-BC9A-4030-BA68-815936DC8331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$EA6299BF-88E3-42BE-8E02-EDC6D7E2308B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f444bf16df4b5bbde39e9e1425fed0fea7639c3e","datavalue":{"value":"92087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$3A5A25C2-CBCD-4769-8893-98D0146FB286","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198017$6DD468A2-7BDD-4752-AD47-A96A09D8D6D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198017$18A005E1-FCD2-4A59-9620-8CDEFBF70575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b191b27e1685b6f1fa22a1f64383bba5917cee0c","datavalue":{"value":"nondeterministic space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198017$8726D79D-B54A-4FD4-A660-357ED4A3F151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d75d448735778f46c4e9667e177539a844422b26","datavalue":{"value":"context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198017$AB1D9C58-3A9D-4E3A-9E7B-BB2B79760B5C","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":"Q1198017$9736DC93-95EC-465F-AD68-157C2EE41D69","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6c9f60d59d03f74d07d7e9b8bc3ab838c64afc2","datavalue":{"value":{"entity-type":"item","numeric-id":1251077,"id":"Q1251077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$4D8E264C-57DC-4E08-B711-FCD9ED7BA69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666aa0dc538558ea52de4ff40acb0092637b3693","datavalue":{"value":{"entity-type":"item","numeric-id":4144808,"id":"Q4144808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$6604FA55-ECE0-49B0-9838-450323569AFB","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":"Q1198017$A1991AC9-049C-429D-915C-267E64B35AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$22180BE9-863C-4B35-B4AF-3DD9821093D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"597cab6a01e7e515c86bb670e6c1b95d0011eb31","datavalue":{"value":{"entity-type":"item","numeric-id":5537615,"id":"Q5537615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$D555183F-4DC9-43EA-8DCC-ADA04B64C80B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186efa9cbcaad91d0d4ad1f36de56ca7d39bfe2e","datavalue":{"value":{"entity-type":"item","numeric-id":1099620,"id":"Q1099620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198017$DD5CF866-D068-4BE5-85C2-94968FBD15E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a42aab64a7a39b6346e6d720d165dba3719dd839","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90127-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198017$BCA864AB-E614-4FCB-B4DE-76063C4C5E1A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"975d3b7b8302f5a407e80cc55b62d688960a2f79","datavalue":{"value":"W2044579324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198017$7BA3575C-E606-4B09-8DA9-9703A9FBB27B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d9ffca5dda6b523aa55899cbcabae81e7d10e70","datavalue":{"value":{"entity-type":"item","numeric-id":3742752,"id":"Q3742752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3c4460fa8735620b41b252981af56bec796e5ad","datavalue":{"value":{"amount":"+0.92200994","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":"Q1198017$7E7157D2-539E-4F3B-B5CE-A3DF06902061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eb56207854d632fda92ab2567c8dd9c806d13bd","datavalue":{"value":{"entity-type":"item","numeric-id":5168415,"id":"Q5168415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67fb71026e74f45a08be35c2933496bc54e353e9","datavalue":{"value":{"amount":"+0.8977777","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":"Q1198017$105AF93E-4F3A-4628-BA51-6DC4F8CAA06A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"576ee2501f9a72543814267656898097b986fd1a","datavalue":{"value":{"entity-type":"item","numeric-id":1193884,"id":"Q1193884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a64eb970c926606f5660ceafafa88ad760c8a8a","datavalue":{"value":{"amount":"+0.8795563","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":"Q1198017$7F97B879-15B2-4B74-B268-7B1B819BCE5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64e0679d103ba1439198b1df3df84fc8151b961f","datavalue":{"value":{"entity-type":"item","numeric-id":293326,"id":"Q293326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6336daaf9416c2072eaa52513200659ee9d90c34","datavalue":{"value":{"amount":"+0.86212003","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":"Q1198017$CFF4E5DF-08F8-496F-B037-2430FEA35FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b6800538ec3171eb1e11561229da09cd5c18198","datavalue":{"value":{"entity-type":"item","numeric-id":1128670,"id":"Q1128670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80b9fe803919deb92018b134e4d1a16ff9456396","datavalue":{"value":{"amount":"+0.85467446","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":"Q1198017$AA641EF3-ADD4-497F-9FC7-DE6F1A835F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1321e2bf633defa40bb4d5b9575c205f438894fa","datavalue":{"value":{"entity-type":"item","numeric-id":3742751,"id":"Q3742751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"350401be3c53621dbbab2a9958dcb553eb948845","datavalue":{"value":{"amount":"+0.8536413","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":"Q1198017$A42124A8-2DA8-486E-B1ED-4925C78E4507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49036c5f40618a6d0e85346bfca2caad1810ccc5","datavalue":{"value":{"entity-type":"item","numeric-id":1096400,"id":"Q1096400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd5f130df09f20d8a29460bb7903521b43e1acd5","datavalue":{"value":{"amount":"+0.8532373","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":"Q1198017$82ADF4B3-0694-4B33-8462-C372EAFFFE2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de01e93f37d9679e5bcd242a3b8c48f47a788363","datavalue":{"value":{"entity-type":"item","numeric-id":1337147,"id":"Q1337147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93592506ea534d7cf6dbaaaee3e553d0a1bc1775","datavalue":{"value":{"amount":"+0.8520473","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":"Q1198017$865A06CE-832F-4E43-BCEF-57A3362754D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"327dca9d6f8ae94ca8a09bbbd95fdc9f90912811","datavalue":{"value":{"entity-type":"item","numeric-id":1944159,"id":"Q1944159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"076f5c1c8c95ae250087214f4ff2ce3189570081","datavalue":{"value":{"amount":"+0.849001","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":"Q1198017$1B4A81EE-40A7-46DC-A64F-EB4ABFBC4D59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for the nondeterministic space complexity of context-free recognition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_the_nondeterministic_space_complexity_of_context-free_recognition"}}}}}