{"entities":{"Q1112610":{"pageid":1123359,"ns":120,"title":"Item:Q1112610","lastrevid":66748047,"modified":"2026-04-12T12:34:51Z","type":"item","id":"Q1112610","labels":{"en":{"language":"en","value":"Some subclasses of context-free languages in \\(NC^ 1\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4078811"}},"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":"Q1112610$1E753716-EC71-49CA-B8BF-1320BC5B777D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5905cdee63d2d6c195aab4e9c2ff3c7b7d96c713","datavalue":{"value":{"text":"Some subclasses of context-free languages in \\(NC^ 1\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112610$E01BADB6-2CF5-4DB2-A758-7EE3C74F9250","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd6681e98d98cca620da6b532881059bcb59453d","datavalue":{"value":"0659.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$19322C61-40F4-4069-AD00-3ED5C4246161","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e34e29c7d243dac587086d82a8a906d83050938","datavalue":{"value":"10.1016/0020-0190(88)90047-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$01095375-558F-4F19-A32D-3DA9C2E14095","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0ccf6eb6c37793d5bd821ffa019f577d6c7be3b","datavalue":{"value":{"entity-type":"item","numeric-id":243823,"id":"Q243823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$BFAB4103-322B-4A57-BD90-A1002FA491F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ff69d199b2e4b3f62f192bd9e307ef835b69b5a","datavalue":{"value":{"entity-type":"item","numeric-id":185445,"id":"Q185445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$A11151F2-3AD4-4028-A7D2-0F7614B1F63D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27c77d1fbecf7b4f1eb1775741545a5ec8f2620b","datavalue":{"value":{"entity-type":"item","numeric-id":1019720,"id":"Q1019720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$F9B72A74-5D40-4A7E-943A-44766D061290","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":"Q1112610$911D616B-065D-46F3-A355-BD8170845758","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1112610$3125E8BC-C626-42F5-ACE0-8AB474645AFE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"672069dca7c75fa589d64adabaed3b35c86a23ba","datavalue":{"value":"One way to show that a problem can be efficiently computed in parallel is to find a parallel algorithm working with a polynomial number of processors in logarithmic time, i.e., to prove that the problem is in \\(NC^ 1\\) [\\textit{N. Pippenger}, On simultaneous resource bounds, 20th IEEE Symp. Fundam. Comput. Sci., 307-310 (1979)]. It was shown by \\textit{W. Ruzzo} [J. Comput. Syst. Sci. 22, 365-383 (1981; Zbl 0462.68013)] that context-free languages (cfl's) are in \\(NC^ 2\\). Since one conjectures that cfl's do not belong to \\(NC^ 1\\) (if they belong to \\(NC^ 1\\) then \\(DLOGSPACE=NLOGSPACE)\\) the authors try to find some subclasses of cfl's which are in \\(NC^ 1\\). Using alternating Turing machine as a parallel computing model it is shown that the one-sided Dyck languages, structured cfl's, bracketed cfl's, and deterministic linear cfl's are in \\(NC^ 1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$F02AFF08-E6FE-41EA-96C1-3723841AD14C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$BDF5E77A-D1EE-4019-8F67-03EBCBB63CAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$31DF3EA4-555C-4CA4-AE5A-849BE432E991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$4BF72909-0103-4F2F-AB5C-CC157A0DC833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$979E2461-DE01-47CA-B47C-5C90C4778E88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0121402e1f5bdb18ad5bde022c1814bb97b45003","datavalue":{"value":"4078811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$3BE80E8F-9455-417A-86FA-D6AF8DCD5D7F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08c32420b55550422a342b5bcbce3f4569e98de5","datavalue":{"value":"parallel computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$D314204E-6917-4DAE-AC1B-D236DDB55C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$DDB2BCB0-989D-47D0-800F-69B59CE1AB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$DC8C94D8-24FD-422E-BE3E-F2F42ECC54A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0472d1480c3b4630050728e5f7fe181f4e2cddd","datavalue":{"value":"context- free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$E7286A21-8773-4E27-AB8F-E87338B7FE0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92caf16c6ea57f9885da64f74196f15c97c0ebb4","datavalue":{"value":"alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$19437939-9B59-4608-9DCC-39CD6AA95992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6b779b537f31c4f0676f84ae8571881d2ecd0aa","datavalue":{"value":"parallel computing model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$2268C2D9-6F43-4D04-852E-F1F522069717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8825504f40c1acc573d9eb67d3704f2605d9d786","datavalue":{"value":"Dyck languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112610$422E0E15-FC62-4D48-A8E3-5AFF38351ABE","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":"Q1112610$6098F00C-6085-4334-B793-A2A1184F9009","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"927263f0d0e5210ce2b2317d0e8cb2e3b709f648","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90047-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112610$B8E356D7-A8B0-4BC2-BBE8-655764B309BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"477dad194ca62f5c9baeeec173a42455c4eac410","datavalue":{"value":"W2039393392","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112610$025D027C-0F25-4A21-B09A-030F0BC9C96B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$8457102F-8A02-4692-95E4-036F207EF0A4","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":"Q1112610$3CBE9C1B-958F-487A-B0E3-B652A8EC96DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$9B516A0B-4D98-4AD6-98C0-428DC297E711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$F88CC506-FB75-475E-B249-B344910A8760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175989e512d6162d2e23de4539fb227c102249ff","datavalue":{"value":{"entity-type":"item","numeric-id":4131647,"id":"Q4131647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$7D1B8B7B-511F-423F-9CF3-C96E524AE3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d37fc9515499cef0e7d4a680a5c07d2a0db5e8e9","datavalue":{"value":{"entity-type":"item","numeric-id":4101728,"id":"Q4101728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$591EA771-E63B-4721-AAB6-7781743669AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dc1aefb41876da5771367e0b82d23ae6d455be5","datavalue":{"value":{"entity-type":"item","numeric-id":3692896,"id":"Q3692896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$83B2F3C3-2E1F-4E4B-94A3-DF03FA57A25D","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":"Q1112610$0AC99467-6244-4858-99C2-6AE05D83A80A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1010a9c02f28743f69ed4786aa0b8973621a76a4","datavalue":{"value":{"entity-type":"item","numeric-id":5653562,"id":"Q5653562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112610$71FAACE4-24D4-4E4C-BDF4-466C1E9D3714","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7416e901fa651d50fee426c43269900bb4e7ed31","datavalue":{"value":{"entity-type":"item","numeric-id":3811706,"id":"Q3811706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d232a2e5d20f0978d23f93f0c5df49d8e7a62449","datavalue":{"value":{"amount":"+0.886044442653656","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":"Q1112610$05113342-9656-4D05-B641-4F86639980AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"367e859c2015e8afafa11400ae2a73eacf1ee5e8","datavalue":{"value":{"entity-type":"item","numeric-id":756426,"id":"Q756426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f7d78ed01f32f6e8b7197d82570e94e07fb6d52","datavalue":{"value":{"amount":"+0.8608351945877075","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":"Q1112610$62CE8B6E-2515-47BC-ADC6-E193C3D701FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a6f7822edae3bd50a312baaf5ac00c206161d91","datavalue":{"value":{"entity-type":"item","numeric-id":1124355,"id":"Q1124355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dce300864c7c3dfdf5b31d993f6e16deb03115e7","datavalue":{"value":{"amount":"+0.8263322710990906","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":"Q1112610$F782D080-49A1-44A2-A7E7-169E4C41FA90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94e1ce4f398767ff1dc3b51c26e7e73856bd7c05","datavalue":{"value":{"entity-type":"item","numeric-id":5096817,"id":"Q5096817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b5e2033f1df8d2fa1cdeccc89854b5638015311","datavalue":{"value":{"amount":"+0.7943915128707886","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":"Q1112610$225A262B-CBB8-4BD6-8A31-CC9A88CB1B2D","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":"a2b969f45c94a0ff30eb0ae94b7296d8a6010a72","datavalue":{"value":{"amount":"+0.7895891666412354","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":"Q1112610$1E7E0148-2552-445E-892E-6C043368BB9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some subclasses of context-free languages in \\(NC^ 1\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_subclasses_of_context-free_languages_in_%5C(NC%5E_1%5C)"}}}}}